Problem 15
2×2の格子の左上をスタートし、右下へ行くルート（後戻りはなし）は6つある。
20×20の格子では何通りのルートがあるだろう。
http://projecteuler.net/index.php?section=problems&id=15
40ステップのうち、20ステップが右で、20ステップが下なら、ちょうど右下に辿り着きます。40ステップのどこに右をいれてどこに下にいれるか、すなわち20ステップある右をどのステップに選ぶかでルートが決まります。だから、40C20になります。
高校の数学の問題集に出てきそうな問題ですが、恐らくこれは、40C20をいかに計算するかという問題なのだと思います。
そういう意味で、Pythonはこの問題を解くのにふさわしくない言語といえます。Cの定義どおりに、
from math import factorialprint factorial(40) / (factorial(20) * factorial(20))
こう書けてしまいます（factorialは階乗）。ちなみに、
40! = 815915283247897734345611269596115894272000000000
となります。Pythonではこのような長い整数でも扱えてしまいます。
これがC/C++だとこうはいきません。そこで、階乗の計算に漸化式を使いましょう。
nCk = nCk-1 (n - k + 1) / k
64ビット整数が使えれば、C++だとこうなります。
#includelong long C(int n, int k) {
if(k == 0)
return 1;
else
return C(n, k - 1) * (n - k + 1) / k;
}int main() {
std::cout << C(40, 20) << std::endl;
}
Pythonなら1行で書けます。
print reduce(lambda c, k: c * (40 - k) / (k + 1), range(20), 1)
しかし、64ビット整数が使えずにオーバーフローしてしまうときはどうでしょう。この問題は64ビットの範囲に収まりますが、それを超えた場合はどうしましょう。
そういうときは、配列を使って長い整数を扱えるようにしましょう。簡単のために配列の1つの要素で1桁を表すことにします。また、このような方法では乗算・除算は難しく加算・減算は容易にコーディングできます。そのために、パスカルの三角形を使いましょう。これなら加算だけで済みます。
| 1 | |||||||||
| 1 | 1 | ||||||||
| 1 | 2 | 1 | |||||||
| 1 | 3 | 3 | 1 | ||||||
| 1 | 4 | 6 | 4 | 1 | |||||
#include
#includeusing namespace std;
typedef vector
longint; const int N = 40;
const int M = N / 2;
const int L = 10;void print(const longint& a) {
for(int k = a.size() - 1; k >= 0; k--)
cout << a[k];
cout << endl;
}longint add(const longint& a, const longint& b) {
bool long_a = a.size() > b.size();
longint c = long_a ? a : b;
const longint& x = long_a ? b : a;
int carry = 0;
for(int k = 0; k < (int)c.size(); k++) {
if(k < (int)x.size())
c[k] += x[k] + carry;
else
c[k] += carry;
carry = c[k] / L;
c[k] %= L;
}
if(carry == 1)
c.push_back(1);
return c;
}int main() {
longint a[N+1];
a[0].push_back(1);
for(int k = 1; k <= N; k++) {
for(int l = k - 1; l >= 1; l--)
a[l] = add(a[l-1], a[l]);
a[k] = a[0];
}
print(a[M]);
}
