2

我正在尝试计算HHHHHHTTTTTT100 万次翻转中字符串的出现次数。对于硬币翻转，我使用了一个简单的 std::rand() % 2。下面的代码。在数学上，预期的答案是

(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;
}
4

1 回答 1

6

假设我们只是在寻找硬币翻转字符串HT。我们开始期待正面。如果第一次抛硬币是正面，那很好，我们继续期待反面。现在，如果第二次抛硬币正面朝上会发生什么？这不符合我们的预期，所以我们应该重新开始，但我们可以认为这是我们全新序列的第一次翻转！也就是说，我们的下一个状态应该是期待尾巴。

但这不是您的代码当前正在执行的操作。你回到开始并再次期待第三枚硬币的正面。第二枚硬币基本上会为你消失在以太中。结果，您无法HT在HHT.

如图所示，您的搜索使用红色状态转换而不是绿色状态转换：

在此处输入图像描述

推断出来，您目前需要连续 6 个正面，然后是 6 个反面。但是第 7 个正面会恢复到开始，并且您开始再次期待 6 个正面，而不是也允许 7 个以上的正面。由于第 7 次翻转有一半时间出现正面，你最终会错过一半的积极事件。

于 2016-07-31T22:36:15.003 回答