QA@IT

再帰呼び出しのアルゴリズム

5523 PV

C言語のアルゴリズムの勉強をしているのですが、
以下の問題を再帰呼び出しを使って解こうとしたところ、どうもうまくいかなくて困っています。
どこが問題なのか、わかる方お願いします!

/*

*/

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

#define MAX 15
#define kind 4

int coins[5] = {10, 50, 100, 500};
int cnt = 0;//組み合わせの数

int calc(int much, int add, int cur, int sum){
  if(cur > MAX){
    return 0;
  }else if(sum==much){
    return 1;
  }else if(coins[add]==0){
    for(int i=0; i<add-1; i++){
      cnt = cnt + calc(much, i, cur+1, sum+coins[add-1]);
    }
  }else{
    for(int i=0; i<add; i++){
      cnt = cnt + calc(much, i, cur+1, sum+coins[add-1]);
    }
  }
}

int main(int argc, char *argv[]){
  int much;
  printf("両替する金額を指定してください>");
  scanf("%d",&much);
  calc(much, kind+1, 0, 0);
  printf("両替の組み合わせは%d通りあります。\n",cnt);
  return 0;
}

----------以下問題文(※出典 https://codeiq.jp/magazine/2014/08/15094/)-------------
<問題>
最近は電車もバスも電子マネーが当たり前。
でも、いまだに現金で払う人も意外と多いもの。
今回はバスに設置されている両替機を考えます。
この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています。
(バスの運賃は現金の場合は10円単位になっているため、1円玉、5円玉は取り扱っていません)
両替する際に、使われない硬貨はあっても構いませんが、
バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。
例えば、10円玉を100枚、という両替はできません。
このとき、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
なお、硬貨の順番は区別しないものとします。

------以下模範解答(Ruby)(※出典 http://www.shoeisha.co.jp/book/download/9784798142456/detail)---------

@cnt = 0
def change(target, coins, usable)
  coin = coins.shift
  if coins.size == 0 then
    @cnt += 1 if target / coin <= usable
  else
    (0..target/coin).each{|i|
      change(target - coin * i, coins.clone, usable - i)
    }
  end
end
change(1000, [500, 100, 50, 10], 15)
puts @cnt


-----追記-------
コメントでもご指摘をいただいた点について

問題にもある通り1000円を両替していくプログラムを作ったつもりなのですが、計算結果が11通りになってしまいます。
(ちなみに答えは20です)
おそらく再帰の方法とcntの取り方に問題があるのだとは思うのですが。

  • どううまくいかないのか、何が期待と違うのかも添えた方がいいと思います。 -
  • ご指摘ありがとうございます。追記させていただきました。 -
  • 出典が明記されていませんが、同じ問題があるようです。https://codeiq.jp/magazine/2014/08/15094/。書籍化もされているようです。http://codezine.jp/article/detail/8975
    -
  • それに挑戦したけれど、自分のコードが完成させられなかったのでどうすれば完成させられるか、といった質問なのだと思います。模範の rubyのコードとも解き方は全然違いますので。 -
  • 回答に追記しましたが、11件もreturnしていないことによるものの様です。 -
  • 模範解答もここで読めるようです。http://codezine.jp/article/detail/8985。mikawataruさんのコードは別に問題ないと思うのですが、問題文と模範解答は他の著作物からの転載に当たるのでは?こういう場合たぶん「引用」ならいいと思いますが、引用なら引用のルールに従うべきかと思います。引用部分の区別とか出典の明示など色々あります。

    -
  • ご指摘ありがとうございます。
    引用元の明記を忘れておりました。修正いたします。
    -
  • 了解です。僕の修正案も回答しておきました。
    -

回答

グローバル変数使っているのが違和感ありますが、
その引数を取る関数でも「20通り」を算出する事はできます。

とりあえず一番気になる点

  • なにもreturnしないルートがある。 else if(coins[add]==0){ 以降はreturnしていません。なにかしらint値を返してください

たしかに11と出るんですけど、returnを追加すると 結果は 0になりますね。

追記

以下を追加して確認しましたが、このreturn 1は一度も呼ばれません。
現状だと最大でも160円までの sumしか計算されておらず、
else if(coins[add]==0){ をなくしたとしても 660円が最大です。
(なので1件も求められていない事になります。11とでるのはreturnしていないことによる副作用でしょう。)

if (sum == much){
    printf("%d %d\n", much, sum);
    return 1;
}

なので最後に書いたのを基に考え直してみるとよいかと思います。

  • 追記ここまで -

コードについて

コードでの実現方法はいろいろなので説明が難しいんですが、
とりあえず私が書き直したコード(まだ公開しません)では
現状の番兵を使うやり方は思いつかなかった(できないと言い切れるほど本格的な検討もしていない)ので、
coinsは int coins[4] = { 10, 50, 100, 500 }; でやりました(今はint coins[5])。

その場合、多分番兵のチェックもやっていません(}else if(coins[add]==0){ のブロック)。
最初の呼び出しもcalc(much, kind + 1, 0, 0); ではなく、calc(much, kind, 0, 0);

残ったif文のfor文は使いましたが条件も変わっています。

returnするのではなく、rubyの模範同様、if(sum==much) のところで cnt++; して、
calc自体はvoid calc(int much ~にしています。

さしあたり今のコードで頑張ってみるならまずは

calc(much, kind+1, 0, 0);
cnt = cnt + calc(much, i, cur+1, sum+coins[add-1]);
cnt = cnt + calc(much, i, cur+1, sum+coins[add-1]);

の各呼び出しで与えている値の意味が変わっていないか。それらをどう利用しているか、を整理してみるといいでしょう。

あとは手動で計算できる、 100円とint coins[3] = {10, 50}; のバージョンで考えてみるとかですかね。


追記 2015/12/22

公開する程の物でもないですが、「(まだ公開しません)」と書いてしまっていたので公開します。
ついでに最大枚数も引数で受け付けるようにしています。

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

#define MAX 15
#define kind 4

int coins[kind] = { 10, 50, 100, 500 };

int calc(int coins[], size_t len, int much, int max_coin_count, int sum, int coin_count){
    if (coin_count > max_coin_count || sum > much){
        return 0;
    }
    if (sum == much){
        return 1;
    }

    int cnt = 0;
    for (size_t i = len; i > 0; i--){
        cnt += calc(coins, i, much, max_coin_count, sum + coins[i - 1], coin_count + 1);
    }
    return cnt;
}

int main(int argc, char *argv[]){
    int much;
    printf("両替する金額を指定してください>");
    scanf("%d", &much);
    int cnt = calc(coins, sizeof(coins) / sizeof(coins[0]), much, MAX, 0, 0);
    printf("両替の組み合わせは%d通りあります。\n", cnt);

    return 0;
}

12/23
ループを使わない場合の解き方も載せておきます。
ちなみにrubyの解き方だと、10円未満を指定した時に 1通り と返りますね(無粋ですが気づいてしまったので一応)。

#include <stdio.h>

int calc(int coins[], int nth, int remaining, int max_coins){
    if (max_coins < 0){
        return 0;
    }
    if (remaining == 0){
        return 1;
    }
    if (remaining < 0){
        return 0;  // オーバーした
    }
    if (nth <= 0 && remaining > 0){
        // nth == 0 でも普通に呼ばれる分には問題ない。
        return 0;  // 検討するコインがもうないが残高がある。
    }

    return 
         calc(coins, nth - 1, remaining, max_coins)                   // 同じ金額で残りのコインだけで問題を解く
       + calc(coins, nth, remaining - coins[nth - 1], max_coins - 1); // 現在のコイン分減らして、同じ問題を解く
}

int main(int argc, char *argv[]){
    int much;
    const int MAX = 15;
    int coins[4] = { 10, 50, 100, 500 };
    printf("両替する金額を指定してください>");
    scanf("%d", &much);
    int cnt = calc(coins, sizeof(coins) / sizeof(coins[0]), much, MAX);
    printf("両替の組み合わせは%d通りあります。\n", cnt);

    return 0;
}

編集 履歴 (4)
  • ありがとうございます。
    おかげでfor文の条件でのミスにも気づき、解決することができました。
    -

修正案です。

  • グローバル変数cntをやめて単純にcalcの戻り値を足したものを返却しています。
  • 金額がぴったり合わない場合も再帰を停止させます(sum > muchの場合)。
  • 配列要素数(硬貨の種類の数)はdefineせずsizeofで求めています。
  • 番兵は複雑になるので使うのをやめました。
  • calc再帰呼び出しの引数が間違っていると(第2引数がiだと)結果が0になったりするので修正しています。
#include <stdio.h>

#define MAX 15

int coins[4] = {10, 50, 100, 500};

int calc(int much, int add, int cur, int sum){
  if(cur > MAX || sum > much){
    return 0;
  }else if(sum==much){
    return 1;
  }else{
    int ret = 0;
    for(int i=0; i < add; i++){
      ret += calc(much, i+1, cur+1, sum+coins[i]);
    }
    return ret;
  }
}

int main(int argc, char *argv[]){
  int much;
  printf("両替する金額を指定してください>");
  scanf("%d",&much);
  int cnt = calc(much, sizeof(coins)/sizeof(int), 0, 0);
  printf("両替の組み合わせは%d通りあります。\n",cnt);
  return 0;
}

追記

答えが合っているかどうか見るため、組み合わせ数だけでなく、内訳を表示するようにしてみました。

実行結果

両替する金額を指定してください>1000
10円玉:  0    50円玉: 10    100円玉:  5    500円玉:  0
10円玉:  0    50円玉:  8    100円玉:  6    500円玉:  0
10円玉:  0    50円玉:  6    100円玉:  7    500円玉:  0
10円玉:  0    50円玉:  4    100円玉:  8    500円玉:  0
10円玉:  5    50円玉:  1    100円玉:  9    500円玉:  0
10円玉:  0    50円玉:  2    100円玉:  9    500円玉:  0
10円玉:  0    50円玉:  0    100円玉: 10    500円玉:  0
10円玉:  5    50円玉:  9    100円玉:  0    500円玉:  1
10円玉:  0    50円玉: 10    100円玉:  0    500円玉:  1
10円玉:  5    50円玉:  7    100円玉:  1    500円玉:  1
10円玉:  0    50円玉:  8    100円玉:  1    500円玉:  1
10円玉:  5    50円玉:  5    100円玉:  2    500円玉:  1
10円玉:  0    50円玉:  6    100円玉:  2    500円玉:  1
10円玉:  5    50円玉:  3    100円玉:  3    500円玉:  1
10円玉:  0    50円玉:  4    100円玉:  3    500円玉:  1
10円玉: 10    50円玉:  0    100円玉:  4    500円玉:  1
10円玉:  5    50円玉:  1    100円玉:  4    500円玉:  1
10円玉:  0    50円玉:  2    100円玉:  4    500円玉:  1
10円玉:  0    50円玉:  0    100円玉:  5    500円玉:  1
10円玉:  0    50円玉:  0    100円玉:  0    500円玉:  2
両替の組み合わせは20通りあります。
編集 履歴 (2)
  • 実行結果(デバッグメッセージ付き)を追記しました。
    -
  • 丁寧なご回答ありがとうございます! -
ウォッチ

この質問への回答やコメントをメールでお知らせします。