在C++中使用std :: rand（）给出错误结果的硬币翻转实验

问题描述：

我试图计算一百万次翻转中字符串HHHHHHTTTTTT出现的次数。对于硬币翻转，我使用了一个简单的std :: rand（）％2.下面的代码。在数学上，预期的答案是在C++中使用std :: rand（）给出错误结果的硬币翻转实验

（10^6 - 12 + 1）/ 2^12 = 244

我从概率教科书这个结果。但是，我的代码一直只能得到大约一半的数据，即122左右。这是使用std :: rand（）作为硬币翻转算法的问题，还是我的代码中存在一个错误？

#include <iostream> 
#include <cstdlib> 
#include <vector> 
#include <ctime> 

using std::vector; 

bool coin_flip(){ 
    return std::rand() % 2; 
} 

int count_string(int n, const vector<bool>& s){ 
    int k=0, res=0; 
    for(int i=0; i<n; i++){ 
    if(coin_flip()==s[k]){ 
     k++; 
     if(k==s.size()){ 
     res++; 
     k=0; 
     } 
    }else{ 
     k=0; 
    } 
    } 
    return res; 
} 

int main(){ 
    std::srand(std::time(0)); 

    vector<bool> v(12); 
    const int a[12] = {1,1,1,1,1,1,0,0,0,0,0,0}; 
    for(int i=0; i<12; i++){ 
    v[i] = a[i]; 
    } 

    std::cout << count_string(1000000, v) << '\n'; 
    return 0; 
}

单元测试你的'count_string'，即在修改后的'coun_flip'中生成序列'HHHHHHHTTTTTT'，为什么当答案是'1'时你会得到'0'？（注意在开始处附加的“H”） – BeyelerStudios

对，搜索算法被破坏。 'std :: rand'没有问题。要正确执行预期结果的任意序列，正确的方法是从搜索字符串构建[NFA]（https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton），将其转换为[DFA]（ https://en.wikipedia.org/wiki/Deterministic_finite_automaton），使用随机生成的输入执行DFA，然后验证是否已达到结束状态。 –

完成的天真方法：使用存储硬币翻转的搜索字符串大小的循环缓冲区。 – BeyelerStudios

答

让我们假装我们只是在寻找投币翻转字符串HT。我们开始期待领导。如果第一枚硬币翻转过来，那么我们就继续前进，以期望尾巴。现在，如果第二个硬币翻转出现，会发生什么？这不符合我们的预期，所以我们应该从开始，但是我们可以认为这是我们全新序列的第一次翻转！也就是说，我们的下一个状态应该是期待的尾巴。

但这不是你的代码目前正在做的。你回到起点，回到第三枚硬币的头上。第二枚硬币基本上会为你消失。因此，您无法在HHT中找到HT。

形象地，你的搜索使用红色状态转变，而不是绿色的：

推断出，你现在要在第6名头，接着6尾。但是第七个头回到开头，你又开始期待6个头，而不是允许7个头。由于第七次翻牌出现一半的时候，你最终错过了一半的积极事件。

在C++中使用std :: rand（）给出错误结果的硬币翻转实验

相关推荐