回答編集履歴
4
確認サイトを追記
answer
CHANGED
|
@@ -8,6 +8,7 @@
|
|
|
8
8
|
これは「まずは足して10になる組み合わせを全て列挙」とは逆の発想で
|
|
9
9
|
「１～残ポイント数ずつひいていって０ポイントになるまで次の値を求めていく」という考え方をします。
|
|
10
10
|
たとえば以下のようなコードになります。
|
|
11
|
+
[Online Python Tutor](http://www.pythontutor.com/)などで実際に動かして動作を追ってみてください。
|
|
11
12
|
```Python
|
|
12
13
|
import math
|
|
13
14
|
|
3
修正
answer
CHANGED
|
@@ -1,7 +1,8 @@
|
|
|
1
|
-
まず、Aの初期値が正値の場合、例示された漸化式なら常に１ポイントずつ利用していくのが解となります（切り捨て操作が入るけど結果に影響ないだろう）
|
|
1
|
+
~~まず、Aの初期値が正値の場合、例示された漸化式なら常に１ポイントずつ利用していくのが解となります（切り捨て操作が入るけど結果に影響ないだろう）~~
|
|
2
|
+
すみません。初期値A=70などでは切り捨て影響して最適解ではなくなりますね。 2018/11/08 08:52修正
|
|
2
3
|
理由は説明できませんが、複利で効いてくるローンなどの利率計算と同じと考えてよいと思います。
|
|
3
4
|
|
|
4
|
-
しかしもし漸化式がもっと複雑だったり単調増加しないものであれば、ご推察のとおり全探索をする必要がでてきます。
|
|
5
|
+
~~しかしもし漸化式がもっと複雑だったり単調増加しないものであれば、~~ご推察のとおり全探索をする必要がでてきます。
|
|
5
6
|
その場合、ちょっと紙に書いて数え上げれば分かる通り、2^(N-1)通りの組み合わせが存在します。ここでN＝ポイント数です。
|
|
6
7
|
この組み合わせの素朴な探索方法、すなわち解き方としては[深さ優先探索](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)というアルゴリズムが適しています。
|
|
7
8
|
これは「まずは足して10になる組み合わせを全て列挙」とは逆の発想で
|
2
場合の数の修正
answer
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
理由は説明できませんが、複利で効いてくるローンなどの利率計算と同じと考えてよいと思います。
|
|
3
3
|
|
|
4
4
|
しかしもし漸化式がもっと複雑だったり単調増加しないものであれば、ご推察のとおり全探索をする必要がでてきます。
|
|
5
|
-
その場合、ちょっと紙に書いて数え上げれば分かる通り、2^N通りの組み合わせが存在します。ここでN＝ポイント数です。
|
|
5
|
+
その場合、ちょっと紙に書いて数え上げれば分かる通り、2^(N-1)通りの組み合わせが存在します。ここでN＝ポイント数です。
|
|
6
6
|
この組み合わせの素朴な探索方法、すなわち解き方としては[深さ優先探索](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)というアルゴリズムが適しています。
|
|
7
7
|
これは「まずは足して10になる組み合わせを全て列挙」とは逆の発想で
|
|
8
8
|
「１～残ポイント数ずつひいていって０ポイントになるまで次の値を求めていく」という考え方をします。
|
1
追記
answer
CHANGED
|
@@ -4,6 +4,8 @@
|
|
|
4
4
|
しかしもし漸化式がもっと複雑だったり単調増加しないものであれば、ご推察のとおり全探索をする必要がでてきます。
|
|
5
5
|
その場合、ちょっと紙に書いて数え上げれば分かる通り、2^N通りの組み合わせが存在します。ここでN＝ポイント数です。
|
|
6
6
|
この組み合わせの素朴な探索方法、すなわち解き方としては[深さ優先探索](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)というアルゴリズムが適しています。
|
|
7
|
+
これは「まずは足して10になる組み合わせを全て列挙」とは逆の発想で
|
|
8
|
+
「１～残ポイント数ずつひいていって０ポイントになるまで次の値を求めていく」という考え方をします。
|
|
7
9
|
たとえば以下のようなコードになります。
|
|
8
10
|
```Python
|
|
9
11
|
import math
|