総当たり探索を使わない

総当たり探索は簡単な方法ですが、それで解こうとすると計算時間がかかりすぎて無理、という場合が多く起こります。それを避けるための方法が多くあります。次の課題は、スタックまたはキューを使うと解けます。

• 分からない人は、Pythonデータ解析お百度参り１５：スタックとキューを復習してみてください。

再帰呼び出しでも似たようなコードは書けますが、データが大きすぎると使えないようです。

• 分からない人は、Pythonデータ解析お百度参り１６：再帰呼び出しを復習して見てください。

課題３２：部分和問題

n 個の整数 a₁, a₂, ..., a_n を入力した時、その中からいくつか選び、その和が m にできれば True を、できなければ False を返す関数を作ってください。

ただし、

• 1 ≤ n ≤ 20
• -10⁴ ≤ a_i ≤ 10⁴
• -10⁴ ≤ m ≤ 10⁴

とします。

また、データ数が増加するに伴い計算時間がどう変化するか計測して確認しなさい。

• 例1

n =  20
a =  [-36, 52, 24, 64, 16, -10, -44, 93, -37, -86, 100, 55, 77, -11, -62, 16, -14, -2, -57, 47]
m =  -83

True

• 例2

n =  20
a =  [31, -42, -45, 2, 39, -11, 62, -20, 8, 19, -78, -38, 12, 47, -6, 36, 24, -8, -16, -31]
m =  0

True

• 例3

n =  20
a =  [-1945, 4145, -2296, -2054, -3499, 3623, -9739, 9542, -9035, 3569, -3484, -455, 3324, -8746, -6922, -656, 8126, 3515, 4931, 4203]
m =  -5329

True

• 例4

n =  20
a =  [-7711, -4112, -1207, -2950, -4434, 2544, -5463, -1524, -8374, -9426, -1934, -2191, -8625, 7108, -7383, 4248, -930, 1616, -8065, -7854]
m =  -2009

False

課題提出方法

• 基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。

• 課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。

• ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。

• 質問・感想・要望などございましたらぜひ書き込んでください。

• もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。

• 課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。

• 次の課題に進む
• 前の課題に戻る