c言語のmまたはnが13以上となる場合に正しい解を求めることができない、なぜなら、13の階乗は6,2

締切済

質問者：lbi_m
質問日時：2017/07/03 23:03
回答数：2件

c言語のmまたはnが13以上となる場合に正しい解を求めることができない、なぜなら、13の階乗は6,227,020,800であり、この値はint型変数で扱うことのできる範囲をこえてしまっているからである。以下のプログラムを改良しなるべく大きなmやnの値でも正しく解を求めることができるプログラムをおしえてください。しかし、変数はあくまでint型を用い、floatやdouble型は使用しない方法でお願いします
int add( int a, int b )
{
int i;
int d = ( b>0 ? 1 : -1 );
int n = ( b>0 ? b : -b );
for( i=0; i<n; ++i )
{ a += d; }

return a;
}

int mul( int a, int b )
{
int i;
int r = 0;
int n = ( b>0 ? b : -b );
for( i=0; i<n; ++i )
{ r = add( r, a ); }

return ( b>0 ? r : -r );
}

int fn( int kitten )
{
return ( kitten>1 ? mul( kitten, fn(kitten-1) ) : 1 );
}

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (2件)

最新から表示
回答順に表示

No.1

回答者： kmee
回答日時：2017/07/04 00:16

log_2(13!)≒32.54なので、 intが33bit以上ある処理系を使えば解決。

intが64bitなら、20!まで正しく求められます。

C言語の規格では、 intのビット幅は決まっていません。
あなたが使っているものが、たまたま int=32bitなだけです。

これって、関数fn が、階乗を求める関数ですよね?
ということは、int型を返す関数fn では、どんなに中で正しく計算できても、 fn()は 32bitまでしか正しく返すことはできません。
つまり、intをやめない限り、 fn(13) は正しく求められません。

どこにも m ,n が出てきていませんが、もしかして順列 (nPm) または組合せ(nCm) を求めるために、階乗を使っているのでしょうか?
それなら、階乗を使った公式ではなく、別の計算方法を使います。

nPm なら n・(n-1)・…・'(n-m+1) を計算する。
nCm なら、分子と分母に分けて、オーバーフローしないように掛けて、約分して既約分数にしてを繰り返す。

それでも、組合せの性質上、nは大して大きくできませんが。