C + +에서 동전 던지기 실험 std :: rand()를 사용하여 잘못된 결과를 내기

Question

문자열 HHHHHHTTTTTT의 발생 횟수를 1 백만 플립으로 계산하려고합니다. 코인 플립의 경우 간단한 std :: rand() % 2를 사용하고 있습니다. 아래 코드를 참조하십시오. I는 확률 교과서에서이 결과를 가지고/2^12 = 244

- 수학적으로 예상되는 응답은

(12 + 1 10^6)이다. 하지만 내 코드는 그 반 정도, 즉 약 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; 
} 

Answer 1

의 우리 그냥 동전 던지기 문자열 HT 찾고있는 척하자. 머리를 기대하기 시작합니다. 첫번째 코인 플립이 머리라면, 우리는 꼬리를 기대하고 있습니다. 이제 두 번째 동전 플립이 머리 위로 올 경우 어떻게됩니까? 이것은 우리의 예상과 일치하지 않으므로 부터 시작해야하지만부터 시작해야합니다. 그러면 우리는 이것이 우리의 새로운 시퀀스의 첫 번째 플립이라고 생각할 수 있습니다! 즉, 다음 상태 인 은이 꼬리를 예상해야합니다.

하지만 현재 코드에서 수행중인 작업이 아닙니다. 당신은 처음으로 돌아가서 3 번째 동전에 대해 다시 머리를 기대합니다. 두 번째 동전은 기본적으로 에테르로 사라집니다. 따라서 HHT에 HT을 찾지 못했습니다.

는 그림으로, 검색 대신 녹색 하나의 빨간색 상태 전이를 사용

밖으로 외삽, 당신은 현재 6 개 꼬리에 이어 연속 6 개 헤드합니다. 그러나 일곱 번째 머리가 처음으로 되돌아 가고, 7 개 이상의 머리도 허용하는 대신에 다시 6 개의 머리를 기대하기 시작합니다. 7 번째 플립이 반으로 나 가면서 긍정적 인 사건의 절반을 놓치게됩니다.