我正在做一个计算彩票的概率的程序.
规格选择47中的5个数字和27个中的1个
规格选择47中的5个数字和27个中的1个
所以我做了以下：
#include <iostream>
long int choose(unsigned n,unsigned k);
long int factorial(unsigned n);
int main(){
using namespace std;
long int regularProb,megaProb;
regularProb = choose(47,5);
megaProb = choose(27,1);
cout << "The probability of the correct number is 1 out of " << (regularProb * megaProb) << endl;
return 0;
}
long int choose(unsigned n,unsigned k){
return factorial(n) / (factorial(k) * factorial(n-k));
}
long int factorial(unsigned n){
long int result = 1;
for (int i=2;i<=n;i++) result *= i;
return result;
}
但是程序不行.程序计算30秒,然后给我进程4退出代码-1,073,741,676我必须将所有的长整型变为长双倍,但是失去精度.是因为long int对于大价值来说太短了吗？虽然我以为long int现在是64位？我的编译器是g win32(64位主机).
解决方法
长时间是64位还是不依赖于型号.
Windows uses a 32-bit
long.如果需要确保它是64位,请使用
int64_t from <stdint.h>.
但是即使长达64位,它仍然太小,无法进行阶乘(47).
47! == 2.58623242e+59 2^64 == 1.84467441e+19
虽然47C5比这个小.
你不应该使用nCr == n！/(r！(n-r)！)直接进行计算,因为它容易溢出.取而代之的是n！/(n-r)！到get：
47 * 46 * 45 * 44 * 43 C = ---------------------- 47 5 5 * 4 * 3 * 2 * 1
这可以由32位整数进行管理.
BTW,为@咖啡的问题：双精度只有53位,其中47！需要154位. 47！和42！以双倍代表
47! = (0b10100100110011011110001010000100011110111001100100100 << 145) ± (1 << 144) 42! = (0b11110000010101100000011101010010010001101100101001000 << 117) ± (1 << 116)
所以47！ /(42！×5！)的可能范围将是
0b101110110011111110011 = 1533939 53 bits
v
max = 0b101110110011111110011.000000000000000000000000000000001001111...
val = 0b101110110011111110010.111111111111111111111111111111111010100...
min = 0b101110110011111110010.111111111111111111111111111111101011010...
这足以得到确切的值47C5.
