編集履歴

回答編集履歴

ミスの修正

2020/04/27 19:34

投稿

スコア2045

test CHANGED Viewed

@@ -138,7 +138,7 @@
   /*
-    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
+    もしa[i]を合計値に入れて目的の値になったならば、真を返す。
   */

返答していなかった質問への返答

2020/04/27 19:34

投稿

namnium1125

スコア2045

test CHANGED Viewed

@@ -84,408 +84,426 @@
 ★何をもってdfs(i+1,sum)の値が決まるのかがこの式から読めません。
+まず動くソースコードを。コメント、つけ直してみました(大して変わってないかも)
+○1, ○2, ○3, ○4はソースコード以下の説明と対応しています。
+wandbox: [https://wandbox.org/permlink/AMrTofmWNM2RKDpA](https://wandbox.org/permlink/AMrTofmWNM2RKDpA)
+```cpp
+#include <iostream>
+const int MAX_N = 20;
+int *a;
+int n, k;
+bool dfs(int i, int sum) {
+  /*
+    この再帰関数の深さがn(今回は4)であれば、最終的に合計値(sum)が目的の値(k...今回なら13)
+    になっているかを返して終わり。
+  */
+  if (i == n) return sum == k; // ○1
+  /*
+    まだ深さが4ではないときに以下は実行される。
+    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
+  */
+  if (dfs(i + 1, sum)) return true; // ○2
+  /*
+    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
+  */
+  if (dfs(i + 1, sum + a[i])) return true; // ○3
+  /*
+    a[i]を入れようが入れまいが、もう合計値にすることは不可能であるからfalseを返す。
+  */
+  return false; // ○4
+}
+void solve() {
+  if (dfs(0, 0)) printf("Yes\n");
+  else printf("No\n");
+}
+int main(void) {
+  n = 4;
+  int b[MAX_N] = {1, 2, 4, 7};
+  a = b;
+  k = 13;
+  solve(); // Yes
+}
+```
+`i` の役割は配列の何番目の話をしているかで、 `sum` の役割は再帰関数がうまく働くようにするための蓄積値といったところです。
+この関数は次のように動きます。( [https://wandbox.org/permlink/VikAMasmuqES69RS](https://wandbox.org/permlink/VikAMasmuqES69RS) で確認できます。以下の説明文めちゃくちゃ長いですが、実際に動きを追ったほうがわかりやすいので書いてみました。)
+---
+`dfs(0, 0)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(1, 0)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(2, 0)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(3, 0)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(4, 0)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `0 == 13` は偽なので、 `dfs(4, 0)` は `false` を返す。
+↓
+○3 `dfs(3, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[3](=7)` が足された
+`dfs(4, 7)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `7 == 13` は偽なので、 `dfs(4, 7)` は `false` を返す。
+↓
+○4 `dfs(3, 0)` の中に戻る。 `dfs(3, 0)` は `false` を返す。
+↓
+○3 `dfs(2, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[2](=4)` が足された
+`dfs(3, 4)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(4, 4)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `4 == 13` は偽なので、 `dfs(4, 4)` は `false` を返す。
+↓
+○3 `dfs(3, 4)` の中に戻る。○2 が実行されなかったので、次に `sum(=4)` に `a[3](=7)` が足された
+`dfs(4, 11)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `11 == 13` は偽なので、 `dfs(4, 11)` は `false` を返す。
+↓
+○4 `dfs(3, 4)` の中に戻る。 `dfs(3, 4)` は `false` を返す。
+↓
+○4 `dfs(2, 0)` の中に戻る。 `dfs(2, 0)` は `false` を返す。
+↓
+○3 `dfs(1, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[1](=2)` が足された
+`dfs(2, 2)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(3, 2)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(4, 2)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `2 == 13` は偽なので、 `dfs(4, 2)` は `false` を返す。
+↓
+○3 `dfs(3, 2)` の中に戻る。○2 が実行されなかったので、次に `sum(=2)` に `a[3](=7)` が足された
+`dfs(4, 9)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `9 == 13` は偽なので、 `dfs(4, 9)` は `false` を返す。
+↓
+○4 `dfs(3, 2)` の中に戻る。 `dfs(3, 2)` は `false` を返す。
+↓
+○3 `dfs(2, 2)` の中に戻る。○2 が実行されなかったので、次に `sum(=2)` に `a[2](=4)` が足された
+`dfs(3, 6)`が呼ばれる。
+↓
+○1 i ≠ nであるから、まだ値は返さない。
+○2 `dfs(4, 6)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `6 == 13` は偽なので、 `dfs(4, 6)` は `false` を返す。
+↓
+○3 `dfs(3, 6)` の中に戻る。○2 が実行されなかったので、次に `sum(=6)` に `a[3](=7)` が足された
+`dfs(4, 13)`が呼ばれる。
+↓
+○1 i = nであるから、`sum == k` の式の評価値を返す。 `13 == 13` は真なので、 `dfs(4, 13)` は `true` を返す。
+↓
+○3のif文以降が実行される。 `dfs(3, 6)` は `true` を返す。
+↓
+○3のif文以降が実行される。 `dfs(2, 2)` は `true` を返す。
+↓
+○3のif文以降が実行される。 `dfs(1, 0)` は `true` を返す。
+↓
+○2のif文以降が実行される。 `dfs(0, 0)` は `true` を返す。
+---
+この説明は蟻本p34の解説絵と同じです。
 ★なぜ0,0なんですか？
-まず動くソースコードを。コメント、つけ直してみました(大して変わってないかも)
-○1, ○2, ○3, ○4はソースコード以下の説明と対応しています。
-wandbox: [https://wandbox.org/permlink/AMrTofmWNM2RKDpA](https://wandbox.org/permlink/AMrTofmWNM2RKDpA)
-```cpp
-#include <iostream>
-const int MAX_N = 20;
-int *a;
-int n, k;
-bool dfs(int i, int sum) {
-  /*
-    この再帰関数の深さがn(今回は4)であれば、最終的に合計値(sum)が目的の値(k...今回なら13)
-    になっているかを返して終わり。
-  */
-  if (i == n) return sum == k; // ○1
-  /*
-    まだ深さが4ではないときに以下は実行される。
-    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
-  */
-  if (dfs(i + 1, sum)) return true; // ○2
-  /*
-    もしa[i]を合計値に入れずに目的の値になったならば、真を返す。
-  */
-  if (dfs(i + 1, sum + a[i])) return true; // ○3
-  /*
-    a[i]を入れようが入れまいが、もう合計値にすることは不可能であるからfalseを返す。
-  */
-  return false; // ○4
-}
-void solve() {
-  if (dfs(0, 0)) printf("Yes\n");
-  else printf("No\n");
-}
-int main(void) {
-  n = 4;
-  int b[MAX_N] = {1, 2, 4, 7};
-  a = b;
-  k = 13;
-  solve(); // Yes
-}
-```
-`i` の役割は配列の何番目の話をしているかで、 `sum` の役割は再帰関数がうまく働くようにするための蓄積値といったところです。
-この関数は次のように動きます。( [https://wandbox.org/permlink/VikAMasmuqES69RS](https://wandbox.org/permlink/VikAMasmuqES69RS) で確認できます。以下の説明文めちゃくちゃ長いですが、実際に動きを追ったほうがわかりやすいので書いてみました。)
----
-`dfs(0, 0)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(1, 0)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(2, 0)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(3, 0)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(4, 0)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `0 == 13` は偽なので、 `dfs(4, 0)` は `false` を返す。
-↓
-○3 `dfs(3, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[3](=7)` が足された
-`dfs(4, 7)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `7 == 13` は偽なので、 `dfs(4, 7)` は `false` を返す。
-↓
-○4 `dfs(3, 0)` の中に戻る。 `dfs(3, 0)` は `false` を返す。
-↓
-○3 `dfs(2, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[2](=4)` が足された
-`dfs(3, 4)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(4, 4)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `4 == 13` は偽なので、 `dfs(4, 4)` は `false` を返す。
-↓
-○3 `dfs(3, 4)` の中に戻る。○2 が実行されなかったので、次に `sum(=4)` に `a[3](=7)` が足された
-`dfs(4, 11)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `11 == 13` は偽なので、 `dfs(4, 11)` は `false` を返す。
-↓
-○4 `dfs(3, 4)` の中に戻る。 `dfs(3, 4)` は `false` を返す。
-↓
-○4 `dfs(2, 0)` の中に戻る。 `dfs(2, 0)` は `false` を返す。
-↓
-○3 `dfs(1, 0)` の中に戻る。○2 が実行されなかったので、次に `sum(=0)` に `a[1](=2)` が足された
-`dfs(2, 2)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(3, 2)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(4, 2)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `2 == 13` は偽なので、 `dfs(4, 2)` は `false` を返す。
-↓
-○3 `dfs(3, 2)` の中に戻る。○2 が実行されなかったので、次に `sum(=2)` に `a[3](=7)` が足された
-`dfs(4, 9)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `9 == 13` は偽なので、 `dfs(4, 9)` は `false` を返す。
-↓
-○4 `dfs(3, 2)` の中に戻る。 `dfs(3, 2)` は `false` を返す。
-↓
-○3 `dfs(2, 2)` の中に戻る。○2 が実行されなかったので、次に `sum(=2)` に `a[2](=4)` が足された
-`dfs(3, 6)`が呼ばれる。
-↓
-○1 i ≠ nであるから、まだ値は返さない。
-○2 `dfs(4, 6)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `6 == 13` は偽なので、 `dfs(4, 6)` は `false` を返す。
-↓
-○3 `dfs(3, 6)` の中に戻る。○2 が実行されなかったので、次に `sum(=6)` に `a[3](=7)` が足された
-`dfs(4, 13)`が呼ばれる。
-↓
-○1 i = nであるから、`sum == k` の式の評価値を返す。 `13 == 13` は真なので、 `dfs(4, 13)` は `true` を返す。
-↓
-○3のif文以降が実行される。 `dfs(3, 6)` は `true` を返す。
-↓
-○3のif文以降が実行される。 `dfs(2, 2)` は `true` を返す。
-↓
-○3のif文以降が実行される。 `dfs(1, 0)` は `true` を返す。
-↓
-○2のif文以降が実行される。 `dfs(0, 0)` は `true` を返す。
----
-この説明は蟻本p34の解説絵と同じです。遷移についてまだよくわからない部分があれば返信ください。
+dfs関数の再帰の仕組みを理解すれば自ずとわかるかと思います。
+i = 0なのは、配列の0番目から部分和を確認する必要があるためです。これは明白だと思います。(i = 4であればi = 0, 1, 2, 3は無視される...明らかにそれは望んだ操作ではない)
+sum = 0なのは、再帰関数がうまく働くようにするには最初の値を0にする必要があるからというのがわかると思います。この変数は、部分和が目的値になっているかを確認するために使われています。
+遷移について等、まだよくわからない部分があれば返信ください。m(_ _)m

ミスの修正

2020/04/27 19:12

投稿

namnium1125

スコア2045

test CHANGED Viewed

@@ -28,7 +28,7 @@
-`i`に1が入っていれば、上から順に `2`、 `4`、`1` 、`2`、 `1` の値に置き換わります。
+`i`に1が入っていれば、上から順に `2`、 `4`、`1` 、`1`、 `2` の値に置き換わります。

リンクをクリックできるように修正

2020/04/27 19:07

投稿

namnium1125

スコア2045

test CHANGED Viewed

@@ -94,7 +94,7 @@
-wandbox: https://wandbox.org/permlink/AMrTofmWNM2RKDpA
+wandbox: [https://wandbox.org/permlink/AMrTofmWNM2RKDpA](https://wandbox.org/permlink/AMrTofmWNM2RKDpA)
@@ -194,7 +194,7 @@
-この関数は次のように動きます。( https://wandbox.org/permlink/VikAMasmuqES69RS で確認できます。以下の説明文めちゃくちゃ長いですが、実際に動きを追ったほうがわかりやすいので書いてみました。)
+この関数は次のように動きます。( [https://wandbox.org/permlink/VikAMasmuqES69RS](https://wandbox.org/permlink/VikAMasmuqES69RS) で確認できます。以下の説明文めちゃくちゃ長いですが、実際に動きを追ったほうがわかりやすいので書いてみました。)

勘違いを起こしそうな解説の修正

2020/04/27 19:02

投稿

namnium1125

スコア2045

test CHANGED Viewed

@@ -18,6 +18,8 @@
 2 * 2
+i
 i++
 ++i
@@ -26,7 +28,7 @@
-上から順に `2`、 `4`、 `i+1`、 `i` の値に置き換わります。
+`i`に1が入っていれば、上から順に `2`、 `4`、`1` 、`2`、 `1` の値に置き換わります。
@@ -34,7 +36,7 @@
-if文の引数として渡される際も、この「評価」が行われています。ですから、以下のような書き方が可能です。
+if文の引数として渡される式に対しても、この「評価」が行われています。変数がくると変数も評価され値が置き換わります。よって以下のような書き方が可能です。
@@ -48,11 +50,11 @@
-  bool hoge = 1 == 2;
+  bool hoge = 1 == 2; // hogeにfalseが代入される
-  if (hoge) {
+  if (hoge) { // hogeの評価値はfalseなのでelse以降を実行
     printf("同じ\n");