QA@IT
«質問へ戻る

6
本文
 
 ```
 
-----------以下問題文(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)-------------
+----------以下問題文(※出典 https://codeiq.jp/magazine/2014/08/15094/)-------------
 <問題>
 最近は電車もバスも電子マネーが当たり前。
 でも、いまだに現金で払う人も意外と多いもの。
 なお、硬貨の順番は区別しないものとします。
 
 
-------以下模範解答(Ruby)(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)---------
+------以下模範解答(Ruby)(※出典 http://www.shoeisha.co.jp/book/download/9784798142456/detail)---------
 ```Ruby
 @cnt = 0
 def change(target, coins, usable)

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

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の取り方に問題があるのだとは思うのですが。

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

```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)---------
```Ruby
@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の取り方に問題があるのだとは思うのですが。

6
本文
 以下の問題を再帰呼び出しを使って解こうとしたところ、どうもうまくいかなくて困っています。
 どこが問題なのか、わかる方お願いします!
 
-<問題>
-最近は電車もバスも電子マネーが当たり前。
-でも、いまだに現金で払う人も意外と多いもの。
-今回はバスに設置されている両替機を考えます。
-この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています。
-(バスの運賃は現金の場合は10円単位になっているため、1円玉、5円玉は取り扱っていません)
-両替する際に、使われない硬貨はあっても構いませんが、
-バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。
-例えば、10円玉を100枚、という両替はできません。
-このとき、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
-なお、硬貨の順番は区別しないものとします。
-
 ```c
 /*
 
 
 ```
 
-------以下模範解答(Ruby)---------
+----------以下問題文(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)-------------
+<問題>
+最近は電車もバスも電子マネーが当たり前。
+でも、いまだに現金で払う人も意外と多いもの。
+今回はバスに設置されている両替機を考えます。
+この機械では、10円玉、50円玉、100円玉、500円玉の組み合わせに両替することができ、いずれの硬貨も十分な枚数がセットされています。
+(バスの運賃は現金の場合は10円単位になっているため、1円玉、5円玉は取り扱っていません)
+両替する際に、使われない硬貨はあっても構いませんが、
+バスの中でたくさんの小銭が出ると困るため、最大で15枚になるように両替します。
+例えば、10円玉を100枚、という両替はできません。
+このとき、1000円札を入れたときに出てくる硬貨の組み合わせは何通りあるかを求めてください。
+なお、硬貨の順番は区別しないものとします。
+
+
+------以下模範解答(Ruby)(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)---------
 ```Ruby
 @cnt = 0
 def change(target, coins, usable)
 puts @cnt
 
 ```
-
+-------------------------------------------------------------------------------
 
 -----追記-------
 コメントでもご指摘をいただいた点について

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

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;
}

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

------以下模範解答(Ruby)(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)---------

@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の取り方に問題があるのだとは思うのですが。

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

```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;
}

```

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


------以下模範解答(Ruby)(※出典 プログラマ脳を鍛える数学パズル 増井敏克 著)---------
```Ruby
@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の取り方に問題があるのだとは思うのですが。

6
本文
 puts @cnt
 
 ```
+
+
+-----追記-------
+コメントでもご指摘をいただいた点について
+
+問題にもある通り1000円を両替していくプログラムを作ったつもりなのですが、計算結果が11通りになってしまいます。
+(ちなみに答えは20です)
+おそらく再帰の方法とcntの取り方に問題があるのだとは思うのですが。

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

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

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

/*

*/

#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;
}

------以下模範解答(Ruby)---------

@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の取り方に問題があるのだとは思うのですが。

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

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

```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;
}

```

------以下模範解答(Ruby)---------
```Ruby
@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の取り方に問題があるのだとは思うのですが。

質問を投稿

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

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

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

/*

*/

#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;
}

------以下模範解答(Ruby)---------

@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

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

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

```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;
}

```

------以下模範解答(Ruby)---------
```Ruby
@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

```