質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.48%

二項係数 トップダウン

受付中

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 809

score 6

前提・実現したいこと

動的計画法を使用した再帰呼び出しで関数定義した時のプログラムについて下記の
出力結果を得られるようにしたいのですが自分なりに大枠は作れた気がしていますが細かな繋ぎ方
などがよく分かりません。特に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]

#include <stdio.h>
#include <stdlib.h>

long int C_count;
long int C(int n, int m);
int none;
// 二項係数 nCm を計算して返す

int main(int argc, char *argv[]){

// n番目(n>=0)のフィボナッチ数を返す

//ここから
int n = atoi(argv[1]);
int m = atoi(argv[2]);
int c = atoi(argv[2]);
printf("C(%d,%d)=%d[%d times]",n,m,c);
//ここまでも自信ありません

    return 0;
}

long int C_(int n, int m,
            long int *c[]){
  C_count++;
  if( c[n][m]!=none ) return c[n][m];
  if( m==0 ) return c[n][m]= 1;
  if( m==n ) return c[n][m]= 1;
  return c[n][m]= C_(n-1,m,c)+C_(n-1,m-1,c);
}

追記

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • y_waiwai

    2020/02/01 21:41

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

    キャンセル

  • r65b

    2020/02/01 21:48

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

    キャンセル

  • y_waiwai

    2020/02/01 22:04

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

    キャンセル

回答 2

0

printf("C(%d,%d)=%d[%d times]",n,m,c);

フォーマット文字列では4つ指定してますが、引数は3つしかありませんぜ

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/02/01 23:06

    C(3,0)=0[3 times]となり、やはりダメでした。
    実現したい事を追記させて頂きました。

    キャンセル

  • 2020/02/01 23:08 編集

    どういう結果が出ればいいんでしょうか
    そのコードではC_関数を全く呼んでないので、その結果にしかなりようにないですが

    キャンセル

  • 2020/02/01 23:17 編集

    コマンドラインに
    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]


    long int C_;とか書き込めばよいですかね??

    キャンセル

0

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の意味が不明です。

/* comb.c */
#include <stdio.h>
#include <stdlib.h>

long int C_count;
long int C(int n, int m);

int main(int argc, char *argv[]) {
    long int n = atoi(argv[1]);

    for ( long int m = 0; m <= n; ++m ) {
      C_count = 0; /* 呼び出し回数を0に */
      int result = C(n,m);
      printf("C(%ld,%ld)=%ld[%ld times]\n",n,m,result, C_count);
    }
    return 0;
}

long int C(int n, int m){
    ++C_count; /* ここで呼び出し回数を+1 */
    if( m==0 ) return 1;
    if( m==n ) return 1;
    return C(n-1,m)+C(n-1,m-1);
}

入力値は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] ではなかろうかと。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る