×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.
では, 20×20 のマス目ではいくつのルートがあるか.
ソースコード1つめ
#include <iostream>
using namespace std;
int Combination(int n, int m) {
long long int a = 1;
for(int i = n; i > n - m; i--) {
a *= i;
}
long long int b = 1;
for(int i = 1; i <= m; i++) {
b *= i;
}
return a / b;
}
int main()
{
cout << Combination(40, 20) << endl;
}オーバーフローには気を付けましょう。long long int型にしてもオーバーフローを起こしました。
aの数が大きすぎたそうです。
ソースコード2つ目
#include <iostream>
using namespace std;
long long int Combination(int n, int r) {
if(r == 0)
return 1;
else if(n == r)
return 1;
else
return Combination(n - 1, r - 1) + Combination(n - 1, r);
}
int main() {
long long int ans = Combination(40, 20);
cout << ans << endl;
}てことで二つ目の解法を考えました。再帰関数でやってみたところCombination(35, 20)までは
すぐに答えは出ましたが、それから数を大きくしてCombination(40, 20)でやったら計算量が多すぎて時間がとてもかかりました。
もう少し計算量を抑える方法を考えたいと思います。
コメント