확률 계산 C++ Bernoulli 평가판

Question

프로그램은 사용자에게 동전을 뒤집을 횟수 (n; 시도 횟수)를 묻습니다.

성공은 머리로 간주됩니다.

완벽하게 프로그램은 0과 1 사이의 난수를 만듭니다. 0은 머리와 성공으로 간주됩니다.

그러면 프로그램은 머리의 x 양을 얻는 예상 값을 출력한다고 가정합니다. 예를 들어 동전이 "큰"숫자와 함께이 일을 할 때 공식

nCk * p^k * (1-p)^(n-k) 
Expected 0 heads with n flips: xxx 
Expected 1 heads with n flips: xxx 
... 
Expected n heads with n flips: xxx 

을 사용하여 다음과 같은 확률 무엇인지 4 번 뒤집힌 경우, 숫자는 이상한 값으로 나올. 입력에 15 또는 20이 입력되면 발생합니다. 나는 xxx가되어야하는 값에 대해 0과 음수 값을 얻었습니다.

디버깅을 통해 nCk가 음수로 나오고 상위 값으로 올바르게 표시되지 않고 문제가 있다는 것을 알았습니다. 내 조합이 공식을 사용

long fact(int x) 
{ 
    int e; // local counter 
    factor = 1; 
    for (e = x; e != 0; e--) 
    { 
     factor = factor * e; 
    } 
    return factor; 
} 

어떤 생각 :

여기

double combo = fact(n)/fact(r)/fact(n-r); 

내 사실 기능에 대한 psuedocode입니까? 내 추측은 내 계승 또는 콤보 함수가 최대 값이나 뭔가를 초과하고 있습니다.

Answer 1

factor의 선언 방법을 언급하지 않았습니다. 나는 당신이 정수 오버 플로우를 얻고 있다고 생각한다. 나는 당신이 두 배를 사용하는 것이 좋습니다. 왜냐하면 예상 값과 확률을 계산하기 때문에 정밀도가 중요하지 않기 때문입니다.

사실 기능을 변경하십시오.

double fact(double x) 
{ 
    int e; // local counter 
    double factor = 1; 
    for (e = x; e != 0; e--) 
    { 
     factor = factor * e; 
    } 
    return factor; 
} 

편집 : 는 또한, NCK를 계산하는 방법이 계승 3 시간을 계산 할 필요가 없습니다. 이 값은 다음과 같이 계산할 수 있습니다.

if k > n/2, k = n-k. 

     n(n-1)(n-2)...(n-k+1) 
nCk = ----------------------- 
      factorial(k) 

Answer 2

최대 값을 초과했습니다. 요인이 너무 빨리 커지므로 올바른 유형의 숫자가 필요합니다. 즉, 필요한 유형에 따라 유형이 달라집니다.

Long은 부호있는 정수이며 2^31을 전달하자마자 음수가됩니다 (2의 보수 계산을 사용함).

부호없는 long을 사용하면 조금 시간이 걸릴 것이지만, 계승에서는 가치가 없을 것입니다. 컴파일러가 long long을 지원하면 "unsigned long long"을 시도하십시오. 그건 보통 (컴파일러와 CPU에 달려 있습니다) 사용하는 비트 수를 두 배로 늘릴 것입니다.

두 번 사용하도록 전환 할 수도 있습니다. 문제는 숫자가 올라감에 따라 정확도가 떨어질 것입니다. double은 부동 소수점 숫자이므로 유효 자릿수는 고정 숫자입니다. 근사치를 사용하면 근사값을 얻을 수 있지만 정확한 값이 필요한 경우 작동하지 않습니다.

이러한 해결 방법으로 해결할 수없는 것이 있다면 검색 할 수있는 "무한 정밀도"수학 패키지를 사용해야 할 수 있습니다.C 또는 C++를 사용하고 있는지 말하지 않았습니다. 이것은 숫자처럼 작동하는 클래스를 제공하고 표준 산술 연산자를 사용하기 때문에 C++로 훨씬 더 즐겁습니다.