二項係数トップダウン

前提・実現したいこと

動的計画法を使用した再帰呼び出しで関数定義した時のプログラムについて下記の
出力結果を得られるようにしたいのですが自分なりに大枠は作れた気がしていますが細かな繋ぎ方
などがよく分かりません。特にint n = atoi(argv[1]);の所から正しいのか教えて頂きたく

コマンドライン
3 0 3
出力
C(3,0)=1 [2 times]
C(3,1)=3 [6 times]
C(3,2)=3 [6 times]
C(3,3)=1 [2 times]

c
1#include <stdio.h>
2#include <stdlib.h>
3
4long int C_count;
5long int C(int n, int m);
6int none;
7// 二項係数 nCm を計算して返す
8
9int main(int argc, char *argv[]){
10
11// n番目(n>=0)のフィボナッチ数を返す
12
13//ここから
14int n = atoi(argv[1]);
15int m = atoi(argv[2]);
16int c = atoi(argv[2]);
17printf("C(%d,%d)=%d[%d times]",n,m,c);
18//ここまでも自信ありません
19
20    return 0;
21}
22
23long int C_(int n, int m,
24            long int *c[]){
25  C_count++;
26  if( c[n][m]!=none ) return c[n][m];
27  if( m==0 ) return c[n][m]= 1;
28  if( m==n ) return c[n][m]= 1;
29  return c[n][m]= C_(n-1,m,c)+C_(n-1,m-1,c);
30}

###追記
組合せの数（2項係数）を計算する関数 long int C(int n, int m)を
動的計画法を適用した再帰呼出しで関数定義した場合に、与えられた非負整数 n、m を引数とする呼出し C(n,m) 対して関数 C が呼び出される回数を数え、2項係数の値とその呼出し回数を標準出力に書き出すプログラムを作ろうとしています。

y_waiwai

2020/02/01 12:41

提示のコードでは何が問題なんでしょうか。

r65b

2020/02/01 12:48

コメントありがとうございます。自分の出力は下記のようになっています。 C(3,0)=0[965152864 times] =の後の0と[]の中が何故かおかしな結果になってしまい、欲しい結果が出ません。

y_waiwai

2020/02/01 13:04

いや、３つしか入れてないやん。。欲しい結果というのを追記しましょう

行動規範の内容に同意します

回答2件

C(3,0)=1 [2 times]

C(3,1)=3 [6 times]
C(3,2)=3 [6 times]
C(3,3)=1 [2 times]

これはつまり入力値 n に対し
C(n,t) : t = 0～n
の結果とcall回数を出力しているのでしょうか。

であるなら、コマンドラインから与える3つのうち2つは要らないことになります。
nはともかく、mとcの意味が不明です。

C
1/* comb.c */
2#include <stdio.h>
3#include <stdlib.h>
4
5long int C_count;
6long int C(int n, int m);
7
8int main(int argc, char *argv[]) {
9    long int n = atoi(argv[1]);
10
11    for ( long int m = 0; m <= n; ++m ) {
12      C_count = 0; /* 呼び出し回数を0に */
13      int result = C(n,m);
14      printf("C(%ld,%ld)=%ld[%ld times]\n",n,m,result, C_count);
15    }
16    return 0;
17}
18
19long int C(int n, int m){
20    ++C_count; /* ここで呼び出し回数を+1 */
21    if( m==0 ) return 1;
22    if( m==n ) return 1;
23    return C(n-1,m)+C(n-1,m-1);
24}

入力値はnひとつだけの上記コードで以下の結果を得ました。

D:\work>cl comb.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.24.28314 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

comb.c
Microsoft (R) Incremental Linker Version 14.24.28314.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:comb.exe
comb.obj

D:\work>comb 3
C(3,0)=1[1 times]
C(3,1)=3[5 times]
C(3,2)=3[5 times]
C(3,3)=1[1 times]

C(n,m) が nCm を求めているのなら、C(3,0) は m=0 なのでただちに結果1 が求まります。
なので [2 times] ではなく [1 times] ではなかろうかと。

投稿2020/02/02 00:44

編集2020/02/02 01:10