組合せ

質問

2個の整数m,n(m≧n)をキーボートから受け取って、m個の相異なる物の中からn個取り出す組合せの数を計算するプログラムを作っているんですが、下のプログラムだと、13の階乗でオーバーフローしてしまいました。combination関数を使わずに、13の階乗を計算したいのですが…。

13!/(k!(13-k)!)で、13!でオーバーフローなので、13!/k!=(k+1)×…×13を計算すればいいのは分かるのですが、どういう関数を定義すればいいのかわかりません。
ヒントやアドバイス頂けると、助かります。
よろしくお願いします。

#include <stdio.h>
void main(void)
{long m,n;
long fact(long);

while(scanf("%ld,%ld",&m,&n)!=EOF)
printf("comb(%ld,%ld)=%ld\n",m,n,
fact(m)/(fact(n)*fact(m-n)));
}
long fact(long k)
{long i,f;
f=1;
for (i=1;i<=k;i=i+1)
f=f*i;
return(f);
}

回答No.3

php504 · ベストアンサー

combination関数を使わずといのは再帰関数を使わないでということでしょうか
n!か(m - n)!の大きい方で約分する関数を作りました
/* mCn を計算する関数 */
int combi(int m, int n) {
int i, numerator, denominator;
if (m < n || n <= 0 || m <= 0) {
return 0;
}
numerator = 1;
denominator = 1;
if (m > n / 2) {
// 分子　n!部分は計算しない
for (i = m; i >= (n + 1); i--) {
numerator *= i;
}
// 分母　(m - n)!のみ計算
for (i = m - n; i > 0; i--) {
denominator *= i;
}
}
else {
// 分子　(m - n)!部分は計算しない
for (i = m; i >= (m - n + 1); i--) {
numerator *= i;
}
// 分母　n!のみ計算
for (i = n; i > 0; i--) {
denominator *= i;
}
}
return (numerator / denominator);
}

お礼

回答ありがとうございます。
丁寧なアドバイス、ありがとうございます。
参考にさせて頂きます！

回答No.7

yama5140

（暇な年寄りが我流で、半日かけて・・）

＞１３の階乗でオーバーフローしてしまいました。

　そうなんですよね。windows 電卓だって、29! までできるのに・・。
　そこで、１つの変数に入れるのではなく、

　★１０進数４桁ごとに配列に入れる方法で、階乗を《表示するだけの》プログラムを投稿します（↓パクリ）。

　http://bal4u.dip.jp/algo/factorial.txt

　★また、nＣr で、分母と分子それぞれ、階乗する数を（掛け合わせる前に）素因数分解して、
　　分母と分子の各素因数の使用共通数を「掛けない」という「手」で nＣr を求めるプログラムを作ってみました。

　　99Ｃ88 ( r < n < 100 )まで求まり？ますが、いかんせん検算できません（残念）。

　　http://www.ccad.sist.chukyo-u.ac.jp/~mito/syllabi/proba/enum/index.htm

　　↑ここで、順列・組み合わせをお復習いしつつ、いくつかは検証したんですが・・。

　　実行例 >hoge 20 13
----------------------------------------
#include <stdio.h>
#include <stdlib.h>

#define　KAI　0　// 階乗
#define　JUN　1　// 順列

#define　BUNSI　0　// 分子
#define　BUMBO　1　// 分母

int　igSoinSu[100], igSoinsuCnt[2][100] = { { 0 } };

int　SoinsuBunkai( int k, int iSw, int iMax )
{
　int　i;

　for( i = 2; i <= iMax; i++ ){

　　if( igSoinSu[i] ){　// 素因数で

　　　if( k == i ){　// 素因数そのもの

　　　　igSoinsuCnt[iSw][i]++;　// 使用数増加

　　　　return( 1 );
　　　}
　　　if( ! ( k % i ) ){　// 素因数で約せるか

　　　　igSoinsuCnt[iSw][i]++;　// 使用数増加

　　　　k /= i;

　　　　SoinsuBunkai( k, iSw, iMax );　// 再帰

　　　　return( k );
　　　}
　　}
　}
　return( 0 );
}
int　Get4Keta( int *iKai4, int iNNN, int iRRR, int iSw )
{
　int　k, j, iEnd = 0, iUp, iLoopEnd = 2;
　int　*ipLeft, *ipMigi;
　long　lWork;

　if( JUN == iSw )　iLoopEnd = iNNN - iRRR + 1;

　*iKai4 = 1;

　for( k = iNNN; k >= iLoopEnd; k-- ){

　　iUp = 0;　// 桁上がり用

　　ipLeft = iKai4;

　　for( j = 0; j <= iEnd; j++ ){

　　　lWork = *ipLeft;
　　　lWork = lWork * k + iUp;
　　　*ipLeft++ = lWork % 10000;
　　　iUp = lWork / 10000;
　　}
　　if( iUp ){　// 桁上がり

　　　*ipLeft = iUp;
　　　iEnd++;　// 後方？へ
　　}
　}
　for( ipLeft = iKai4, ipMigi = iKai4 + iEnd; ipLeft < ipMigi; ipLeft++, ipMigi-- ){　// 尾頭入れ換え

　　iUp = *ipLeft;
　　*ipLeft = *ipMigi;
　　*ipMigi = iUp;
　}
　return( 1 + iEnd );
}
long　Get_nCr( int iNNN, int iRRR )
{
　int　k, i, iSa;
　long　lWork_B = 1, lWork_S = 1;

　for( k = iRRR; k >= 2; k-- ){　// 分母の一部 r!

　　SoinsuBunkai( k, BUMBO, iRRR );
　}
　for( k = ( iNNN - iRRR ); k >= 2; k-- ){　// 分母の一部 ( n - r )!

　　SoinsuBunkai( k, BUMBO, ( iNNN - iRRR ) );
　}
　for( k = iNNN; k >= 2; k-- ){　// 分子 n!

　　SoinsuBunkai( k, BUNSI, iNNN );
　}
　for( k = 2; k <= iNNN; k++ ){　// 分母と分子の使用数の違いのみ掛け合わせ

　　if( igSoinsuCnt[BUMBO][k] == igSoinsuCnt[BUNSI][k] )　continue;

　　iSa = igSoinsuCnt[BUMBO][k] - igSoinsuCnt[BUNSI][k];

　　if( iSa > 0 )　for( i = 0; i < iSa; i++ )　lWork_B *= (long)k;　// 不要？
　　if( iSa < 0 )　for( i = 0; i > iSa; i-- )　lWork_S *= (long)k;
　}
　if( lWork_S < 0 ){

　　printf( "r を n に近づけて下さい( r < n < 100 )\n" );

　　exit( 0 );
　}
　return( lWork_S / lWork_B );
}
void　SoinsuSet( void )
{
　int　i, j;

　igSoinSu[0] = 0;
　igSoinSu[1] = 0;

　for( i = 2; i < 100; i++ ){

　　igSoinSu[i] = 1;　// 素因数

　　for( j = 2; j <= ( i / 2 ); j++ ){

　　　if( ! ( i % j ) ){　// でない

　　　　igSoinSu[i] = 0;

　　　　break;
　　　}
　　}
　}
}
void　main( int argc, char *argv[] )
{
　int　n, iEnd_K, iEnd_J, iNNN, iRRR;
　int　iJun4[1000] = { 0 };　// １０進４桁格納
　int　iKai4[1000] = { 0 };
　long　lKekka;

　SoinsuSet();

　if( 3 != argc )　exit( 0 );

　iNNN = atoi( argv[1] );　// nCr の n
　iRRR = atoi( argv[2] );　// nCr の r

　iEnd_K = Get4Keta( iKai4, iRRR, 0, KAI );　// r!
　iEnd_J = Get4Keta( iJun4, iNNN, iRRR, JUN );　// nPr

　printf( "%d! = %d", iRRR, iKai4[0] );

　for( n = 1; n < iEnd_K; n++ ){

　　printf( "%04d", iKai4[n] );
　}
　printf( "\n" );

　printf( "%dＰ%d = %d", iNNN, iRRR, iJun4[0] );

　for( n = 1; n < iEnd_J; n++ ){

　　printf( "%04d", iJun4[n] );
　}
　printf( "\n" );

　lKekka = Get_nCr( iNNN, iRRR );　// nCr

　printf( "%dＣ%d = %ld\n", iNNN, iRRR, lKekka );
}
注：インデントに全角空白を用いています。タブに一括変換して下さい。

お礼

回答、ありがとうございます。
参考にさせて頂きます！

回答No.6

Tacosan

#2 についてもうちょっというと, comb(n, k) = n! / (k! (n-k)!) をそのまま計算すると, 分子の n! でオーバーフローすることが必ず問題になります. で, 少し考えると「n! / k! = n (n-1) ... (k+1) を計算して (n-k)! で割る」というところにたどり着きますが, これでもやっぱり n! / k! で破綻する (最終結果はオーバーフローしないにもかかわらず計算途中でオーバーフローする) ことがあります.
これを避ける単純な方法が「comb(n, 0) = 1 から comb(n, 1), comb(n, 2), ... と計算していく」というもので, そのためには comb(n, k) から comb(n, k+1) を計算できる必要があります.
この線でがんばれば「結果がオーバーフローしない限り正しく計算できる」ようにもできるはず.

お礼

アドバイスありがとうございます。
頑張ってみます！
参考にさせて頂きます！

回答No.5

Tacosan

えっと,
if (n > m-n) n = m-n;
とさいしょに一発入れておくだけでいいんじゃないでしょうか＞#3.

回答No.4

php504

訂正
if (m > n / 2) {
↓
if (n > m / 2) {

回答No.2

Tacosan

comb(n, k) と comb(n, k+1) の関係を考える.

回答No.1

επιστημη（@episteme）

分母と分子から同じ数を取り除いて約分します。

お礼

回答ありがとうございます。
参考にさせて頂きます。