【C言語 再帰呼び出し】 表示方法と硬貨の支払いについて

Question

C言語で再帰呼び出し使ってプログラムをつくりたいのですが、
難解でどうすればいいのか四苦八苦しています。
どなたかアドバイスを頂けないでしょうか？

問題

200円を1円、5円、10円、50円、100円の5種類の硬貨を使って、何通りの支払い方法があるかを求めるプログラムを再帰呼び出しを使って作る。関数change(int n, int k)を定義（n 円をk 円以下の硬貨で支払う支払い方の数を返す関数）し、main()関数では、支払う金額を1円から200円まで1円きざみで繰り返して「1円 = 1通り」、、「200円 = ???通り」のように、200行の出力を得られるようにする。

現状として1円から200円まで1円きざみで繰り返すことはできたのですが、
「1円 = 1通り」、、「200円 = ???通り」と表す時に、下記のようになってしまいます。
1円＝1通りのように横並びに書くにはどうすればいいのでしょうか。

1円=
2円=
3円=
4円=
.
.
.
196円=
197円=
198円=
199円=
200円=
0通り

また、何通りか表す時に0になってしまうのですが、
どう組み合わせを変更したら良いものか全く手が出ず困っています。

サンプルプログラムしかりアドバイスしかり、
ご助力願えないでしょうか。
どうかよろしくお願いします。

現状

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

// カウンタ変数
int i, count;
//支払い方法の数を数える関数(n:200円をk:100円以下の硬貨で)
int change(int n, int k){

    int count;
    for(int i = 1; i <= 200; i++){
      count = i;
      printf("%d円=\n",count);
    }

  //change(n, 1) は，1円玉だけしか使えないので1通り
  if (count == 1) {
    return 1;
  } else if(count == 5) { //change(n, 5) は，change(n, 1) + change(n −5, 5)
    return change(n, 1) + change(n - 5, 5);
  } else if(count == 10) { //change(n, 10) は，change(n, 5)+change(n−10, 10)
    return change(n, 5)+change(n - 10, 10);
  } else if(count == 50) { //change(n, 50) は，change(n, 10)+change(n−50, 50)
    return change(n, 10)+change(n - 50, 50);
  } else if(count == 100) { //change(n, 100) は，change(n, 50)+change(n−100, 100)
    return change(n, 50)+change(n - 100, 100);
  } else{
    return 0;
    }
  }


int main(){
  int way;
  way = change(200, 100);
  printf("%d通り\n", way);
  exit(0);
}

試したこと

横に並べようと思い、以下のようにしてみたのですが、上手くいきませんでした。

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

//支払い方法の数を数える関数(n:200円をk:100円以下の硬貨で)
int change(int n, int k){

  //change(n, 1) は，1円玉だけしか使えないので1通り
  if (k == 1) {
    return 1;
  } else if(k == 5) { //change(n, 5) は，change(n, 1) + change(n −5, 5)
    return change(n, 1) + change(n - 5, 5);
  } else if(k == 10) { //change(n, 10) は，change(n, 5)+change(n−10, 10)
    return change(n, 5)+change(n - 10, 10);
  } else if(k == 50) { //change(n, 50) は，change(n, 10)+change(n−50, 50)
    return change(n, 10)+change(n - 50, 50);
  } else if(k == 100) { //change(n, 100) は，change(n, 50)+change(n−100, 100)
    return change(n, 50)+change(n - 100, 100);
  } else{
    return 0;
    }
  }


int main(){
  int i, count, way;
  way = change(200, 100);
  for(int i = 1; i <= 200; i++){
    count = i;
    printf("%s円=\n","%d通り\n", count, way);
  }
  exit(0);
}

上記のエラー

test6.c:29:37: warning: data argument not used by format string [-Wformat-extra-args]
    printf("%s円=\n","%d通り\n", count, way);
           ~~~~~~~~~             ^
1 warning generated.

Comments

[dodox86]

まず、問題への解答の前提として『「main()関数では、支払う金額を1円から200円まで1円きざみで繰り返して「1円 = 1通り」...』とあるのですから、main関数の形態は「試したこと」で示したようなものでないといけないと思います。「現状」のものは無条件で不可なはずです。
「上記のエラー」とありますが、コンパイルエラーなのではなく、警告（Warning）です。printf()関数の書式制御文字列に対して与えられた引数(count, way)が合っていないと報告しています。printf()関数の使い方を再度ちゃんと確認しましょう。

[jimbe]

複数の問題に同時に対処するのは、良いことではありません。
まずは別のプログラム (test6a.c とか ) として、 "x円, 0 通り" と x=1～200 分出すプログラムを作成して練習?したほうが良いかもしれません。

[jimbe]

再帰が難しければ、再帰を用いない change 関数を作ってから再帰化するという手順もあると思います

Answer 1

1円＝1通りのように横並びに書くにはどうすればいいのでしょうか。

printf を次のように main に書けばよいでしょう。

#include <stdio.h>

int change(int n, int k)
{
	return n/5 * (n/5) * 1013 / 1600 + 1;
}

int main(void)
{
	for (int n = 1; n <= 200; n++)
		printf("%d円 = %d通り\n", n, change(n, 100));
}

change は嘘のコードなので、自分で考えてください。

追記
嘘のコードは気持ちが悪いので、ちゃんと動くコードを示します。

int change(int n, int k)
{
	return n < 0 ? 0 : k == 1 ? 1 :
		change(n-k, k) + change(n, k==5 ? 1 : k==10 ? 5 : k==50 ? 10 : 50);
}

これは模範解答ではありません。
?: の三項演算子を使わないほうが分かりやすくなり、
質問のコードに近いものになるでしょう。

でも、printf("abc\n"); printf("def\n"); を
printf("abc\n", "def\n") としてもなぜ横に並ばないか
が分からないようではどうしようもないですね。

Comments

[rubato6809]

私の回答の不足分を補っていただき、ありがとうございます。

[rubato6809]

200円の組み合わせ数が同じになったので安心できました。

Answer 2

まず横に表示することについて。
コンパイルでワーニングが出るのは、書式が間違っているからです。
printf("%s円=\n","%d通り\n", count, way);
↓
printf("%s円=\n%d通り\n", count, way);
としたら、ワーニングは消えるでしょう。
ちなみに、"%s円 は "%d円 でしょう。
次に、
printf("%d円=%d通り\n", count, way);
とすれば、＝の後改行されなくなります。
それでも次の表示がかぶってしまう場合は、
printf()のあとに
fflush(stdout);
を追加します。
これで、バッファに残っていた未表示の文字列が表示されます。
試してみてください。

Answer 3

200円を払う組合せとは、100円＊２枚から1円*200枚までカウントしてよいですね？私が作ってみたコードが正しければ200円を払う組合せは1000通りを超えました。

再帰は、部分が全体の相似（自己相似）になるような場合に有効です。
私はこんな風に考えてみました。例えば200円を100円以下のコインで払う場合、即ちchange(200, 100) は

• 100円を一枚も使わず、200円を50円以下のコインで払う組合せの数、即ち change(200, 50)の値
• 100円を一枚使い、残り100円を50円以下のコインで払う組合せの数、即ち change(100, 50)の値
• 100円を二枚使い、残り0円を50円以下のコインで払う組合わせの数、即ち１

以上の合計です。つまり

• change(200, 100) = change(200, 50) + change(100, 50) + change(0, 50)

です。change(0, 50) は要するに1（一通り）です。そこをプログラムにどう表すかは工夫次第で、再帰呼出しの終了条件と関係します。
さらに、例えば上記にある change(100, 50) は、50円が0～2枚に対してそれぞれ change(100, 10) と change(50, 10) と change(0, 10) を足した数・・・という具合いに
change(n, k) とは、k円コインを使う複数のパターンに対し、それぞれ残りの金額をより小さなコインの組合せで数えさせる（再帰する）ことで求められると考えられます。ここの再帰する箇所は、自分より小さな自己相似形を呼ぶ形になっているというわけです。具体的に列挙すると

• 100円以下を使って払う組合せは、50円以下を使って払う組合わせから求められる
• 50円以下を使って払う組合せは、10円以下を使って払う組合わせから求められる
• 10円以下を使って払う組合せは、5円以下を使って払う組合わせから求められる
• 5円以下を使って払う組合せは、1円を使って払う組合わせ（＝＝１）

となりますので、再帰呼出しは４～５段になりそうです。ただし実際に書くのは自分が自分を呼出す一段階だけを一般化し、再帰の終了条件を加えて、コード化します。
文章だけで書くと正しく伝わりそうにないので、コードの核心を示します（完成形ではない）。

// change(n, k)  n円を k円コイン以下で払う組合せの数を返す
int change(int n, int k)
{
    // 終了条件をどうするか？

    int knext = smallerCoin(k);  // 次の小さなコイン（100の次は50、50の次は10...）
    int max = n / k;             // k 円コインが使える最大枚数
    int ans = 0;                 // n 円を k 円以下のコインで払う組合せ数

    // k 円コインは 0～max枚使える。
    for (int i = 0; i <= max; i++) {
        // それぞれ残りの金額を、より小さなコインの組合せで数えさせる（ここで再帰）。
        ans += change(n - k * i, knext);  // 残りを knext 円以下のコインで払う組合せ数
    }
    return ans;
}

上のコードには再帰の終了条件がありません、change(?, 1) 即ち1円だけの組合わせは一通りしかないことなどが終了条件になるでしょう。