代表的なアルゴリズム

ここから先いくつかの課題では、代表的なアルゴリズムについて学べる課題に取り組んでいただきます。

多重ループを用いた総当たり探索

次の２つのコードを動かして、挙動の違いを確認してみてください。

X = [0, 1, 2, 3, 4]
Y = [5, 6, 7, 8, 9]

for x in X:
    for y in Y:
        print(x, y)

X = [0, 1, 2, 3, 4]
Y = [5, 6, 7, 8, 9]

for x, y in zip(X, Y):
    print(x, y)

課題３０：和が m になる取り出し方

自然数 k₁, k₂, ..., k_n が書かれた n 枚の紙片が袋に入っています。この袋から紙片を取り出し、数字を見て袋に戻すことを４回行います。その４つの数字の和が m になる取り出し方が存在するかどうか計算し、存在すれば True、 存在しなければ False と出力する関数を作成してください。

ただし、

• n ≤ 50
• 1 ≤ m ≤ 10⁴
• 1 ≤ k_i ≤ 10³

とします。

• 例1

n = 10
m =  36
k =  [13, 39, 63, 70, 18, 87, 46, 99, 68, 47]

False

• 例2

n = 10
m =  66
k =  [60, 45, 73, 100, 57, 82, 2, 85, 43, 8]

True

• 例3

n = 20
m =  496
k =  [240, 471, 143, 482, 231, 127, 482, 145, 195, 336, 31, 83, 450, 376, 108, 133, 118, 340, 400, 170]

True

課題提出方法

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

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

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

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

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

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