2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。
では、20 × 20 のマス目ではいくつのルートがあるか。
単純なコンビネーションの計算である。
ここでのポイントは２つ
- 約分することで、演算精度を向上させた
- 乗算と除算を別々に行なうことで、演算精度を向上させた
2については、まだしっくり来ていないが、
まいっか
//2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある
//では、20 × 20 のマス目ではいくつのルートがあるか。
#include<iostream>
#define NUM 20
using namespace std;
//---------------------------------------------------------------------->
//コンビネーション
//---------------------------------------------------------------------->
long long int combi( long long int n , long long int r ){
long long int child[256];
long long int mom[256];
double ans=1;
for(int i = r ; i > 0 ; i--){
child[ i ] = n - i + 1;
mom[ i ] = i;
}//next i
//約分
//約分しないと、1の位に誤差発生
for( int i = 1 ; i <= r ; i++){
for( int j = 1 ; j <= r ; j++ ){
if ( mom[ j ] != 1 ){
if(child[ i ] % mom[ j ] == 0 ){
child[i] /= mom[ j ];
mom[ j ] = 1;
}//end if
}//end if
}//next j
}//next i
for( int i = r ; i > 0 ; i--){
//掛け算とわり算を同時に行なうと、誤差発生。
ans *= child[ i ];
ans /= mom[ i ];
//cout << "\t child:\t" <<child[i]<<"\t mom:\t"<<mom[i]<< "\t ans:\t"<<ans<<"\n";
}
return (long long int)ans;
}
//---------------------------------------------------------------------->
//メイン
//---------------------------------------------------------------------->
int main( void ){
long long int ans;
ans = combi( NUM * 2 , NUM );
cout << ans;
getchar();
return 0;
}