プロジェクトオイラー Problem15

C++

×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある.

p_15.gif

では, 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)でやったら計算量が多すぎて時間がとてもかかりました。

もう少し計算量を抑える方法を考えたいと思います。

コメント

タイトルとURLをコピーしました