質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.05%

部分和問題のif文の中身が何をしているのかわからない

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 2,058
退会済みユーザー

退会済みユーザー

部分和問題のif文の中身が何をしているのかわからないです。
http://y0m0r.hateblo.jp/entry/20121203/1354549288
を参考に部分和問題を書いたら

# coding=utf-8
# 部分和問題
# 深さ優先検索

# 整数がn個与えられる。その中からいくつか選び、その環をちょうどkにすることができるかどうかを判定する

def solve(integer_list, target_sum,  i=0, sum=0):
    if i == len(integer_list):
        return sum == target_sum
    if (solve(integer_list, target_sum, i + 1, sum)):
        return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
        return True
    return False

# n個の整数
integer_list = [1,3,5,12,7]
# k
target_sum = 11

print(solve(integer_list, target_sum))
# => True


のようになったのですが、
この

    if (solve(integer_list, target_sum, i + 1, sum)):
        return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
        return True


の中のif文の条件が何をしているのかわかりません。

if (solve(integer_list, target_sum, i + 1, sum)):
if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):


は何の機能なのでしょうか?

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

再帰処理ですね。
solveの引数は、次のように解釈するといいかと思います。

  • integer_list
    文字通り、整数のリスト。途中変更されることはない。([1,3,5,12,7])
  • target_sum
    文字通り、対象となる和。途中変更されることはない。(11)
  • i
    どこまでリストを見たか記憶している変数。
  • sum
    これまでの和。

さらに、それぞれのif文は、次を意味します。

  • if i = len(integer_list): 終了条件
    リストの全てをチェックした場合、現段階の合計がtarget_sumと等しければTrueを返す。
    異なる場合はFalseを返す。
  • if (solve(integer_list, target_sum, i + 1, sum)):
    今着目している数値(integer_list[i])を足さずに、次の数値に着目する。
  • if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
    今着目している数値(integer_list[i])を足して、次の数値に着目する。

これらを把握したうえで、プログラムの処理を追ってみましょう。
solve([1,3,5,12,7], 11, 0, 0)が呼ばれると、次の二パターンに分割して問題を解決します。

  1. 0番目の数値をsumに足す場合
    次のようにsolveを呼び出し、判断を次のsolveに委託します。solve([1,3,5,12,7], 11, 1, 1)
  2. 0番目の数値をsumに足さない場合
    次のようにsolveを呼び出し、判断を次のsolveに委託します。solve([1,3,5,12,7], 11, 1, 0)

... どんどん二分割されていきます ...

これをある程度続けていくと、いつかリストの最後まで見ることになります。
その時の条件が、i == len(integer_list)です。
例えばsolve([1,3,5,12,7], 11, 5, 11)が呼ばれると、終了条件に達します。

リスト長がこの場合5ですから、2の5乗で32パターンに分割されますが、
それぞれが必ず終了条件に達し、結論がTrue/Falseで返されます。


私も初めて再帰処理を見たとき、狐に化かされたような気がしました。
面倒でも、ひとつひとつ紙に書いてみると、感覚がつかめるかもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/15 21:01

    ありがとうございます。
    if (solve(integer_list, target_sum, i + 1, sum)):
    return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
    return True
    で2つのif文の sum の値の保存はどこで行われているのでしょうか? i + 1でiがどんどん増えていく理由はわかるのですが。

    キャンセル

  • 2017/07/15 21:04

    また、2つのif文のreturn True で一度2つのif文が呼ばれればsolveメソッドはTrueを返すと思ったのですが、それは違うのでしょうか?(なら必ずこのメソッドはTrueを返すような気がしたのですが...)

    キャンセル

  • 2017/07/15 21:17

    sumの値は保存されません。毎度毎度引数として渡されます。
    実際に紙に書いてみると、sumの値を変数に保存しなくても済む感覚が掴めるかと思います。

    キャンセル

  • 2017/07/15 21:20 編集

    > 2つのif文のreturn trueで...
    ちょっと待ってください。Trueが返されるのは、if文の条件が真のときのみです。
    そういう意味で、『判断を次のsolveに委託します』という表現を使いました。

    全てのif文の条件がFalseとなったとき、solve関数最終行に到達し、solveはFalseを返します。

    キャンセル

0

単純に自身を呼び出しているだけです。
最終的にiとinteger_listの長さが同じになるのでbool値がreturnされます。結果として条件文の判定として使われています。

再帰関数について調べてみると良いです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.05%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る