• 締切済み

組み合わせ

n個の集合からp個を取る組み合わせの総数を出力するプログラムなんですが nCp=n!/p!(n-p)!という式を使い #include<stdio.h> int kaijo(int m); int comb(int n,int p); int main(void) { int i,j; printf("n="); scanf("%d",&i); printf("p="); scanf("%d",&j); printf("comb(%d,%d)=%d\n",i,j,comb(i,j)); } int kaijo(int m) { if(m>0) return(m*kaijo(m-1)); else return 1; } int comb(int n,int p) { if(n>0) return((n*kaijo(n-1))/(p*kaijo(p-1)*(n-p)*kaijo(n-p-1))); else return 1; } と書いてみたのですがこれではnが大きいとＣ言語のint型で扱える最大値を超えてしまい正しい結果が出力されません。 　そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたいのですがどう改良したらよいのでしょうか？ おそらくnCp=n*(n-1)*・・・*(n-p+1)/p!という式を使うのですがよく分かりません。よろしくお願いします。

みんなの回答

  • BLUEPIXY
  • ベストアンサー率50% (3003/5914)
回答No.5

効率は良くないですが、 //nCr=n-1Cr-1 + n-1Cr,nC0=nCn=1,nC1=n;より unsigned comb(unsigned n, unsigned r){ if(r==0 || r==n) return(1); if(r==1) return(n); return (comb(n-1,r-1)+comb(n-1,r)); } 途中の計算結果を再利用するようにすると効率はよくなります。

  • jacta
  • ベストアンサー率26% (845/3158)
回答No.4

あらかじめ計算して、結果を配列に格納しておくのが一番確実です。

  • Interest
  • ベストアンサー率31% (207/659)
回答No.3

> そこでint型を使ったままでnやpが大きい場合でもある程度出力できるようにしたい 「ある程度」とはどの程度ですか？それによってやり方が変わります。プログラムを設計するときは、最初に仕様を決めましょう。 それから、int は処理系依存ですので、16bitの処理系と32bitの処理系では扱える値の範囲が異なりますので注意が必要です。

  • migoreng
  • ベストアンサー率42% (6/14)
回答No.2

もっと大きい n の値を扱う必要がある場合は、n! に関するスターリングの公式を使う方法もあります。この公式は、n! は、(n の n乗) と (e の -n乗)の積にほぼ等しいというもの(ただし e = 2.718... は自然対数の底)で、n が十分大きいときに成り立ちます。 詳しくは、 - http://szksrv.isc.chubu.ac.jp/stirling/stirling.html や、 - http://mathworld.wolfram.com/StirlingsApproximation.html を参照してください。

  • migoreng
  • ベストアンサー率42% (6/14)
回答No.1

その式を使うのであれば、 int comb(int n, int p); を、 int comb(int n, int p) { 　　int w = 1; 　　int m; 　　for ( m = n; m > n - p; m-- ) 　　{ 　　　　w *= m; 　　} 　　return w / kaijo( p ); } にしてみたらどうでしょうか。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • パスカルのピラミッドを作りたいのですが...

    */ 入力した段数のパスカルの三角形をつくる */ #include <stdio.h> /*---nCr値を返す---*/ int comb(int n,int r) { if (r == 0 || r == n) return (1); else if (r == 1) return (n); else return (comb(n - 1,r-1) + comb(n - 1,r)); } int main(void) { int ln; int i,j; do{ printf(" 段数を入力して下さい："); scanf("%d",&ln); }while (ln < 1); if (r == 0 || r == n) return (1); else if (r == 1) return (n); else return (comb(n - 1,r-1) + comb(n - 1,r)); } int main(void) { int ln; int i,j; do{ printf(" 段数を入力して下さい："); scanf("%d",&ln); }while (ln < 1); for (i = 0; i < ln; i++){ for(j = 0;j < ln - i;j++) putchar(' '); for(j = 0; j < i; j++){ printf("%d",comb(i,j)); printf(" "); } putchar('\n'); } return (0); } と作ったら、うまく 1 1 1 1 2 1 1 3 3 1 とは表示されず、 1 1 2 1 3 3 1 4 6 4 となってしまいます。 どこを直せばよいのでしょうか。教えて下さるとうれしいです。 よろしくお願い致します。

  • パスカルの三角形についてのCプログラムの解説をお願いします！

    プログラミング初心者です。 先日『ｎが入力されたときに、ｎ段のパスカルの三角形を出力するプログラムを作成しなさい』という課題が出ました。 まだ理解しきれていないところが多いもので、手元にある資料をマネて、とりあえず動いてくれるように書いてみました。 今消化不良をおこしているのは以下の２点です。 １　一部理解できない箇所がある →解説をいただきたい ２　出力される三角形が、パスカルの三角形ではなくただの『ｄ』の三角形になってしまう →どこが間違っているのかご指摘いただきたい 以下が書いたプログラムです。 #include<stdio.h> int comb(int n, int r) { if (r==0 || r==n) return 1; elese return comb(n - 1, r - 1) + comb(n - 1, r); } main() { int n,i,j; printf("n?"); scanf("%d",&n); for (i=0; i<=n, i++) { for(j=0; j<=i, j++) { printf("d%",comb(i,j)); } printf("\n"); } } ちなみに理解できていない（自分自身で説明できない）箇所は main関数の前、 if (r==0 || r==n) return 1; elese return comb(n - 1, r - 1) + comb(n - 1, r); の二行です。お恥ずかしい話、記号の意味もよくわかってません； どなたかご指導お願いします！！（＞＜）

  • nCrはどうあらわせばい？？

    キーボードから二つの正の整数n，r を入力し，組み合わせの数nCr を計算して画面表示するプログラムを作成せよ．ただし，組み合わせの数を計算する関数のプロトタイプをint combination( int, int )とし，my_scanf()をキーボードから二つの正の整数n，r を入力する関数，kaijo() を階乗を求めるプログラムとする． という問題なんですが #include <stdio.h> int my_scanf(void){ int n; do{ scanf("%d",&n); }while(n <= 0); return n; } int kaijo(int m){ int i,x = m; for(i=1;i<m;i++){ x *= i; } return x; } int combination( int m, int w){ int ncr; ncr = m/w; return ncr; } int main (void){ int pos,sum_n,sum_r,answer; printf("n = "); pos = my_scanf(); sum_n = kaijo(pos); printf("r = "); pos = my_scanf(); sum_r = kaijo(pos); answer = combination(sum_n,sum_r); printf("nCr = %d",answer); return(0); } 結果的にはｎ！／ｒ！を求めるプログラムに・・・・。 combination関数内を書き直せばいいのでしょうか？

  • CからVB

    以下のプログラムはC言語で作成されています。 これをVBで作成したいです。 教えてください。 #include <stdio.h> #include <stdlib.h> double *alloc(int r,int n,int m); void input(double *p,int r,int n,int m); void sumup(double *p,int r,int n,int m); int main(void){ int r, n, m; double *p; // 行列サイズ入力 printf("input r n m "); scanf("%d %d %d",&r,&n,&m); // 行列領域取得 p = alloc(r,n,m); // 行列要素入力 input(p,r,n,m); // 行列の和 sumup(p,r,n,m); //終了，行列領域解放 free(p); return 0; } double *alloc(int r,int n,int m){ double *p; printf("MATRIX[r=%d][n=%d][m=%d]\n\n",r,n,m); p = (double*)malloc(sizeof(double)*r*n*m); if( p == NULL){ printf("error! malloc failed.\n"); exit(-1); } return p; } void input(double *p,int r, int n,int m) { int i,j,k; for(i = 0; i < r; i++){ for(j = 0;j < n; j++){ for(k = 0; k < m; k++){ printf("input MATRIX[%d][%d][%d]= ",i,j,k); scanf("%lf",&p[i*(n*m)+j*m+k]); } } } printf("\n"); } // 行列の和 void sumup(double *p,int r,int n,int m){ int i, j, k; // 0.0, not 0!!! double sum = 0.0; printf("sum of %d matrices:\n",r); for(j = 0; j< n; j++){ for(k = 0;k < m; k++){ sum=0; for(i = 0;i < r;i++){ sum += p[i*(n*m)+j*m+k]; } printf("\n%2f",sum); } } printf("\n"); }

  • 組み合わせ

    aに100、bに20や2を入力すると プログラムが停止します。 計算できるように御指摘お願いします。 以下のプログラムです。 #include<stdio.h> int factrical(int n){ if(n>0){ /*printf("%d\n",n);*/ return (n*factrical(n-1)); } else{ return(1);} } int combination(int n ,int r){ return(factrical(n)/(factrical(n-r)*factrical(r))); } int main (void){ int a,b,c; printf("二つの数を入力してください。\n"); do{ printf("大きい方の数を入力してください。\n"); scanf("%d",&a); scanf("%d",&b); }while(a<b); c=combination(a,b); printf("%d",c); return(0);}

  • c言語の再帰で(関数呼び出し)+1がわからない

    再帰がどのように処理されているのか理解するために、再帰の時に +1 してみたところ 0! = 1 1! = 2 2! = 5 3! = 16 4! = 65 5! = 326 6! = 1957 7! = 13700 8! = 109601 9! = 986410 10! = 9864101 となりました。 普通の階乗の値を求めた最後に +1され、それが戻されると思ったのですが違いました。 これはどういう処理がされているのでしょうか？ #include <stdio.h> int kaijo(int); int main() { int i; for (i = 0; i < 11; i++) printf("%d! = %d\n", i, kaijo(i)); return 0; } int kaijo(int n) { if (n == 0) return 1; else return n * kaijo(n - 1) + 1; }

  • C言語のwhile文はネストできますか?

    「*」を使用して、n列、m行の四角を表示させるプログラムを考えました。 --------------------------------------------------------------------------------------------- #include<stdio.h> int main(void) { int i=0,j=0,n,m; printf("n入力:"); scanf("%d",&n); printf("\nm入力:"); scanf("%d",&m); printf("\n"); while(i<m){ while(j<n){ printf("*"); j++; } printf("\n"); i++; } return 0; } --------------------------------------------------------------------------------------------- しかし、1行分しか表示されません。 n=2、m=2の場合 ----------------- n入力: m入力: ** ----------------- としか表示されません。 whileのネストが悪いのでしょうか? それとも、初歩的なミスがあるのでしょうか?

  • C言語でmからnまでの合計を求めるプログラム

    これで動かないのですが、何が違っているのか、教えていただけますか。 #include <stdio.h> int main(void) { int m, n, sum, i, w ; printf("ｍからｎまでの合計を求めます\n\n"); printf("m >> "); scanf(" %d", &m); printf("n >> "); scanf(" %d", &n); sum=0; if(m>n){ w=m; m=n; n=w; } sum=0; i=m; while(i<=n){ sum=sum+i; i=i+1; } printf("%d から %d の合計 = %d\n",m,n,sum); return 0; }

  • ｎ個からｍ個を取り出すプログラムでわかりません。

    #include<stdio.h> int main() { int n; int m; int i; int kumi; int san; printf("n:"); scanf("%d",&n); printf("m:"); scanf("%d",&m); for(kumi=1,i=n;i>n-m+1;i--){ kumi=kumi*i; } for(san=1,i=1;i<=m;i++){ san=san*i; } printf("%d個の中から%d個を取り出す組み合わせは%dとおり\n",n,m,kumi/san); return 0; } 組合わせの値がおかしいです。

  • c言語のプログラムで行列の積を計算する

    指定された行・列数（それぞれ10以下とする）の行列 X, Y の積 Z = X × Y を求めるプログラムを作成せよ．行列の要素はすべて整数とする． このプログラムで行と列の成分を入力するときに、1列になってしまうのですがどうしたらちゃんと入力できますか？ int main(void) { double A[10][10]; double B[10][10]; int i,j,m,n,p,k; printf("行列xの行数は？:"); scanf("%d",&m); printf("行列xの列数(行列yの行数)は？:"); scanf("%d",&n); printf("行列yの列数は？:"); scanf("%d",&p); printf("行列xを入力してください。\n"); for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { scanf("%d", &A[i][j]); } } printf("行列yを入力してください。\n"); for (i = 0; i < n; i++) { for (j = 0; j < p; j++) { scanf("%d", &B[i][j]); } }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する