“牛牛”算法

Question

牛和牛是一种流行的游戏名为“大师”，在一张纸上，每个球员都写了一个4位数的秘密数字。数字一定都不一样。然后，反过来，球员试图猜测他们的对手的号码，谁给出的比赛数。如果匹配的数字在它们正确的位置上，它们就是“多头”，如果在不同的位置上，它们就是“牛”。

维基百科页面

一种方法是生成可能是答案的所有可能的数字的列表，然后通过只保留那些能给出最后猜测如何得分的等分的数字来修剪列表。下一个猜测可以是剪枝列表中的任意数字。

要么程序猜对了，要么猜不出要猜的数字，这表明评分有问题。

这是C++中n位数字的实现，猎人(所有可能的数字列表)是一个vector of string，它的功能是从两个数字中计数奶牛：

for(int h=0; Hunters.size() > 1; h++){
    askBullsCows(h);
    string guess = Hunters.at(0);
    for(int i=Hunters.size()-1; i >= 0; i--){
        int pl = 0, fl = 0;
        for (unsigned int ix = 0; ix < Hunters.size(); ix++){
            if(Hunters[i].at(ix) == guess.at(ix))    pl++;
        }
        Cows(i, guess, fl);
        if((pl != P.p) || (fl != P.f)){
           Hunters.erase(cazadores.begin()+i);}
    }
}

现在，猎人( vector)拥有超过150.000 strings，这是一个又一个删除string太贵了，这是不可能的答案。

Answer 1

1. 使用char[n]而不是字符串来存储每个单独的解决方案。
2. 只把合格的解决方案复制到一个全新的vector上(正如Ben所说)，而不是删除。

假设是n<=10。因此，您需要的内存小于73 So (即两次10*10!)。顺序内存访问(#2)和避免指针取消引用(#1)意味着现代DDR内存的高性能。

更新:一些关于随机或甚至非随机的注释，但非顺序的DDR记忆读.例如，地址0x8000 0x8100 0x8200 0x8300的四个8字节读取将比0x9000 0x9008 0x90100x9018的四个8字节读取慢，因为在后一种情况下，最后一次读取的所有数据(即0x9008 0x9010 0x9018)已经在处理器32字节缓存行中(另外，有些处理器中有64字节缓存行)。每个内存读取(例如，8字节读取)将整个32字节高速缓存行从内存转移到处理器缓存。

其次，即使是最好的优化器也不能减少非顺序记忆访问延迟(即计算内存地址与到达处理器的内存地址内容之间的时间)。

Answer 2

不要使用vector<string>，而是使用一个常数大小的vector<bool> ( 10000元素)。元素0表示应答0000，等等，直到9999。最初将所有设置为true，但不包括多次包含相同数字的数字，并在消除特定选项后将位翻转到false。

一个vector<bool>有一个专门的实现(很多抱怨的来源)，它紧紧地封装比特，所以它只需要10000位，即大约1.2个kB。更重要的是，“删除”是在固定时间内完成的。

Answer 3

首先，注释您的变量名是可怕的，这使得阅读代码非常困难。

其中：

for(int h=0; Hunters.size() > 1; h++){

• h应该代表什么？
• 为什么h不是条件的一部分?，因为h不是循环的一部分，所以您应该从循环构造中删除它，这就变成了一段时间。

你真的想在这里复制字符串吗？

    string guess = Hunters.at(0);

    // make it a const reference
    // You are not altering the gurss and you don't need a copy.
    string const& guess = Hunters.at(0);

真奇怪你为什么决定数数。

似乎不需要它，计数是更自然和更容易推理，所以你应该喜欢它时，你可以。

    for(int i=Hunters.size()-1; i >= 0; i--){

请在一行中声明一个变量。

        int pl = 0, fl = 0;

给这些变量取有意义的名字，这样我们就能看到发生了什么。我不知道这两者与公牛/牛/猎人的位置/其他东西的大小有什么关系。没有这个上下文，代码几乎是无法解密的。一些应该是显而易见的东西一目了然，只需5分钟的挠头才能理解。

这里出了点问题：

        for (unsigned int ix = 0; ix < Hunters.size(); ix++){
            if(Hunters[i].at(ix) == guess.at(ix))    pl++;
        }

变量ix的范围超过数组的大小。但是，它被用作attar的单个成员的索引(幸运的是，您使用at()来生成适当的异常)。也许如果你给他们取了个合理的名字，那就更容易辨认了。

好的。从退伍军人身上抹去是很昂贵的。尤其是像你说的那么大。

if((pl != P.p) || (fl != P.f)){
       Hunters.erase(cazadores.begin()+i);}

但是在数组上没有固有的排序，所以这样做成本更低(但是您需要倒转上面的循环，这样它就可以向上而不是向下)。

 if (testToKeep())
 {
       ++hunterIndex;  // Move to the next element.
                       // OK: That name is a bit long for a loop variable.
                       //     But its intent is clear. `huntIdx` would do.
 }
 else
 {
     hunters[hunterIndex].swap(hunters[hunters.size()-1]);
     hunters.resize(hunters.size()-1);

     // Note: We do not increment the loop here
     //       This is because we have a new value to test
     //       at the current location and the size of the array
     //       has decreased thus effectively moving us one closer
     //       to the end.
 }

我可以原谅把'{‘放在错误的线上，因为大约有30%的开发人员喜欢这样做(其他30%的开发人员更喜欢排队、打开和关闭，最后的40%不关心(只要您一致))。

if((pl != P.p) || (fl != P.f)){
       Hunters.erase(cazadores.begin()+i);}

但请将结束支撑“}”放在下面。绝对没有必要进行这种疯狂的尝试，以节省空间和使代码不可读。而且，这将使其与代码的其余部分保持一致(这更重要)。