計算大組合

你會如何計算一個組合，如（100,000選擇50,000）？計算大組合

我迄今嘗試過三種不同的方法，但由於顯而易見的原因每個人都有失敗：

1）動態編程 - 數組的大小隻是變得如此可笑的是賽格故障

unsigned long long int grid[p+1][q+1]; 

//Initialise x boundary conditions 
for (long int i = 0; i < q; ++i) { 
    grid[p][i] = 1; 
} 

//Initialise y boundary conditions 
for (long int i = 0; i < p; ++i) { 
    grid[i][q] = 1; 
} 


for (long int i = p - 1; i >= 0; --i) { 
    for (long int j = q - 1; j >= 0; --j) { 
    grid[i][j] = grid[i+1][j] + grid[i][j+1]; 
    } 
}

2）蠻力 - 顯然計算甚至100！是不現實的

unsigned long long int factorial(long int n) 
{ 
    return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n; 
}

3）乘式 - 我無法儲存他們只是大

const int gridSize = 100000; //say 100,000 
unsigned long long int paths = 1; 

for (int i = 0; i < gridSize; i++) { 
    paths *= (2 * gridSize) - i; 
    paths /= i + 1; 
} 

// code from (http://www.mathblog.dk/project-euler-15/)

如果有幫助的情況下這樣做的目的是爲了解決「的值對於大型輸入，有多少路徑通過m×n網格「問題。也許我錯過了攻擊這個問題的辦法？

來源

2014-01-18 Matt Stokes