回答編集履歴
2
文章一部修正
test
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
200円を払う組合せとは、100円＊２枚から1円*200枚までカウントしてよい
|
|
1
|
+
200円を払う組合せとは、100円＊２枚から1円*200枚までカウントしてよいですね？私が作ってみたコードが正しければ200円を払う組合せは1000通りを超えました。
|
|
2
2
|
|
|
3
3
|
再帰は、**部分が全体の相似（自己相似）になる**ような場合に有効です。
|
|
4
4
|
私はこんな風に考えてみました。例えば200円を100円以下のコインで払う場合、即ちchange(200, 100) は
|
|
@@ -8,15 +8,15 @@
|
|
|
8
8
|
|
|
9
9
|
以上の合計です。つまり
|
|
10
10
|
- change(200, 100) = change(200, 50) + change(100, 50) + change(0, 50)
|
|
11
|
-
です。change(0, 50) は要するに1（一通り）です。そこをプログラムにどう表すかは工夫次第。
|
|
11
|
+
です。change(0, 50) は要するに1（一通り）です。そこをプログラムにどう表すかは工夫次第で、再帰呼出しの終了条件と関係します。
|
|
12
12
|
さらに、例えば上記にある change(100, 50) は、50円が0～2枚に対してそれぞれ change(100, 10) と change(50, 10) と change(0, 10) を足した数・・・という具合いに
|
|
13
|
-
change(n, k) とは、**k円コインを使う複数のパターンに対し、それぞれ残りの金額をより小さなコインの組合せで数えさせる（再帰する）ことで求められる**と考えられます。ここの再帰する
|
|
13
|
+
change(n, k) とは、**k円コインを使う複数のパターンに対し、それぞれ残りの金額をより小さなコインの組合せで数えさせる（再帰する）ことで求められる**と考えられます。ここの再帰する箇所は、自分より小さな自己相似形を呼ぶ形になっているというわけです。具体的に列挙すると
|
|
14
14
|
- 100円以下を使って払う組合せは、50円以下を使って払う組合わせから求められる
|
|
15
15
|
- 50円以下を使って払う組合せは、10円以下を使って払う組合わせから求められる
|
|
16
16
|
- 10円以下を使って払う組合せは、5円以下を使って払う組合わせから求められる
|
|
17
17
|
- 5円以下を使って払う組合せは、1円を使って払う組合わせ（＝＝１）
|
|
18
18
|
|
|
19
|
-
となりますので、再帰呼出しは４～５段になりそうです
|
|
19
|
+
となりますので、再帰呼出しは４～５段になりそうです。ただし実際に書くのは**自分が自分を呼出す一段階だけを一般化し、再帰の終了条件を加えて、コード化**します。
|
|
20
20
|
文章だけで書くと正しく伝わりそうにないので、コードの核心を示します（完成形ではない）。
|
|
21
21
|
|
|
22
22
|
```C
|
|
@@ -37,4 +37,4 @@
|
|
|
37
37
|
return ans;
|
|
38
38
|
}
|
|
39
39
|
```
|
|
40
|
-
上のコードには再帰の終了条件がありません
|
|
40
|
+
上のコードには再帰の終了条件がありません、change(?, 1) 即ち1円だけの組合わせは一通りしかないことなどが終了条件になるでしょう。
|
1
間違いを含めていくつか修正
test
CHANGED
|
@@ -1,16 +1,16 @@
|
|
|
1
|
-
200円を払う組合せとは、
|
|
1
|
+
200円を払う組合せとは、100円＊２枚から1円*200枚までカウントしてよいんですよね？私が作ってみたコードが正しければ200円を払う組合せは1000通りを超えました。
|
|
2
2
|
|
|
3
3
|
再帰は、**部分が全体の相似（自己相似）になる**ような場合に有効です。
|
|
4
4
|
私はこんな風に考えてみました。例えば200円を100円以下のコインで払う場合、即ちchange(200, 100) は
|
|
5
|
-
-
|
|
5
|
+
- 100円を一枚も使わず、200円を50円以下のコインで払う組合せの数、即ち change(200, 50)の値
|
|
6
|
-
-
|
|
6
|
+
- 100円を一枚使い、残り100円を50円以下のコインで払う組合せの数、即ち change(100, 50)の値
|
|
7
|
-
-
|
|
7
|
+
- 100円を二枚使い、残り0円を50円以下のコインで払う組合わせの数、即ち１
|
|
8
8
|
|
|
9
9
|
以上の合計です。つまり
|
|
10
10
|
- change(200, 100) = change(200, 50) + change(100, 50) + change(0, 50)
|
|
11
11
|
です。change(0, 50) は要するに1（一通り）です。そこをプログラムにどう表すかは工夫次第。
|
|
12
12
|
さらに、例えば上記にある change(100, 50) は、50円が0～2枚に対してそれぞれ change(100, 10) と change(50, 10) と change(0, 10) を足した数・・・という具合いに
|
|
13
|
-
change(n, k) とは、**k円コインを使う複数のパターンに対し、それぞれ残りの金額をより小さなコインの組合せで数えさせる（再帰する）ことで求められる**と考えられます。ここの再帰する個所
|
|
13
|
+
change(n, k) とは、**k円コインを使う複数のパターンに対し、それぞれ残りの金額をより小さなコインの組合せで数えさせる（再帰する）ことで求められる**と考えられます。ここの再帰する個所は、自分より小さな自己相似形を呼ぶ形になっているというわけです。具体的に列挙すると
|
|
14
14
|
- 100円以下を使って払う組合せは、50円以下を使って払う組合わせから求められる
|
|
15
15
|
- 50円以下を使って払う組合せは、10円以下を使って払う組合わせから求められる
|
|
16
16
|
- 10円以下を使って払う組合せは、5円以下を使って払う組合わせから求められる
|
|
@@ -20,7 +20,7 @@
|
|
|
20
20
|
文章だけで書くと正しく伝わりそうにないので、コードの核心を示します（完成形ではない）。
|
|
21
21
|
|
|
22
22
|
```C
|
|
23
|
-
// change()
|
|
23
|
+
// change(n, k) n円を k円コイン以下で払う組合せの数を返す
|
|
24
24
|
int change(int n, int k)
|
|
25
25
|
{
|
|
26
26
|
// 終了条件をどうするか？
|
|
@@ -29,9 +29,9 @@
|
|
|
29
29
|
int max = n / k; // k 円コインが使える最大枚数
|
|
30
30
|
int ans = 0; // n 円を k 円以下のコインで払う組合せ数
|
|
31
31
|
|
|
32
|
-
// k 円コインは 0～max枚
|
|
32
|
+
// k 円コインは 0～max枚使える。
|
|
33
|
-
// それぞれ残りの金額を、より小さなコインの組合せで数えさせる（ここで再帰）。
|
|
34
33
|
for (int i = 0; i <= max; i++) {
|
|
34
|
+
// それぞれ残りの金額を、より小さなコインの組合せで数えさせる（ここで再帰）。
|
|
35
35
|
ans += change(n - k * i, knext); // 残りを knext 円以下のコインで払う組合せ数
|
|
36
36
|
}
|
|
37
37
|
return ans;
|