問１：和が m になる取り出し方

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

ただし、

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

とする。

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

【ヒント】４重ループを作って総当たり検索をしましょう。ひとつでも存在が見つかればループから脱出してOK。

例1-1

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

False

例1-2

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

True

例1-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

例1-4

n = 20
m =  395
k =  [94, 143, 107, 262, 478, 446, 443, 373, 431, 36, 281, 476, 153, 23, 203, 279, 429, 476, 281, 475]

False

例1-5

n = 50
m =  3538
k =  [62, 770, 584, 150, 228, 872, 978, 735, 667, 620, 921, 254, 280, 811, 468, 541, 846, 586, 385, 151, 185, 522, 745, 941, 170, 885, 19, 246, 331, 383, 616, 436, 626, 320, 42, 572, 978, 42, 973, 648, 978, 926, 510, 918, 180, 517, 352, 724, 827, 424]

True

例1-6

n = 50
m =  5264
k =  [629, 873, 624, 235, 721, 979, 966, 370, 48, 817, 687, 766, 554, 966, 673, 134, 858, 876, 167, 838, 858, 576, 6, 417, 218, 120, 142, 800, 113, 912, 424, 548, 655, 134, 744, 587, 481, 284, 197, 542, 559, 16, 367, 241, 32, 268, 545, 930, 162, 978]

False

参考：例の作り方

import random
n = 50
m = random.randint(1, 10000)
k = [random.randint(1, 1000) for _ in range(n)]

print("m = ", m)
print("k = ", k)

問２：三角形は作れるか？

様々な長さの n 本の棒がある。棒 i の長さは a_i とする。その中から３本を取り出し、できるだけ周長の長い三角形を作りたい。そのような三角形が存在するときは、最長の周長を出力し、存在しないときは 0 を出力する関数を作成しなさい。

ただし、

3 ≤ n ≤ 100
1 ≤ a_i ≤ 10³

とする。

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

【ヒント】３重ループで全探索しながら、最大値を見つけるたびに更新していく。

例2-1

n =  5
a =  [28.54, 13.36, 54.82, 13.91, 44.29]

127.65

例2-2

n =  4
a =  [24.73, 53.4, 0.25, 97.89]

例2-3

n =  19
a =  [493.13, 615.02, 340.68, 462.98, 988.55, 572.16, 572.91, 963.01, 12.07, 95.51, 733.24, 810.39, 105.99, 574.57, 945.38, 937.82, 976.24, 245.43, 260.06]

2927.8

例2-4

n =  93
a =  [5.12, 37.92, 423.29, 512.46, 801.74, 391.6, 149.55, 430.43, 310.78, 562.61, 11.39, 662.88, 872.17, 501.71, 187.24, 575.35, 512.01, 367.66, 196.64, 679.75, 174.56, 276.71, 737.98, 221.59, 734.84, 53.9, 125.24, 261.69, 780.83, 376.43, 985.84, 240.3, 256.35, 324.72, 964.01, 279.76, 13.02, 15.32, 307.18, 465.25, 291.69, 713.49, 125.53, 765.65, 38.57, 567.78, 402.4, 131.54, 288.23, 705.4, 351.75, 818.57, 176.69, 473.8, 598.14, 711.17, 576.65, 198.87, 52.31, 588.76, 722.02, 710.96, 119.23, 846.55, 595.7, 80.1, 307.05, 750.6, 485.46, 787.75, 474.98, 428.54, 369.85, 740.59, 262.23, 983.04, 808.89, 916.89, 753.5, 7.45, 716.17, 632.46, 217.93, 376.37, 15.16, 27.05, 321.26, 815.79, 514.78, 333.77, 394.86, 963.88, 824.96]

2932.89

参考：例の作り方

import random

n = random.randint(3, 100)
a = [round(random.random() * 1000, 2) for _ in range(n)]

print("n = ", n)
print("a = ", a)

問３：部分和問題

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

ただし、

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

とする。

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

【ヒント】問１と似てますが、いくつ選択するかが決まっていないという点で、違います。「深さ優先探索」を使う解法が知られています。

例3-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

例3-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-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

例3-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

参考：例の作り方

import random
n = 20
a = [random.randint(-10000, 10000) for _ in range(n)]
m = random.randint(-10000, 10000)

print("n = ", n)
print("a = ", a)
print("m = ", m)

問４：迷路の最短経路

大きさが X * Y （XYともに整数）の迷路が与えられます。迷路はスタート「S」とゴール「G」、通路「_」と壁「#」からできており、１ターンあたり、隣接する上下左右４マスの通路のいずれかに移動できます。スタートからゴールまで移動可能な場合は、必要な最小のターン数を返し、不可能な場合は False を返す関数を作りなさい。

ただし、

X, Y ≤ 100

とする。

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

【ヒント】「幅優先探索」を使う典型的な問題です。

例4-1

string_maze = \
    '__##_S______\n' \
    '##_##____##_\n' \
    '______#_____\n' \
    '#_#_#______#\n' \
    '__#______#_#\n' \
    '#______#___#\n' \
    '_#_##______#\n' \
    '___###__#__G\n' \
    '_###_____##_\n' \
    '_#__#_______\n'

例4-2

string_maze = \
    '__S#__#___##\n' \
    '_____#___###\n' \
    '__##__#__###\n' \
    '_#__##___#_#\n' \
    '_###_##____#\n' \
    '_____#_###__\n' \
    '________#_#_\n' \
    '#______#_#_#\n' \
    '#___#___#___\n' \
    '________#G__\n'

False

例4-3

string_maze = \
    'S_#_##__###_\n' \
    '#___#__#__##\n' \
    '_##_______#_\n' \
    '___##__#_##_\n' \
    '___#__#_#___\n' \
    '#____#____#_\n' \
    '__#_##G####_\n' \
    '_____##___#_\n' \
    '____##__#___\n' \
    '#_#____##_#_\n' \

例4-4

string_maze = \
    '##___###_#_#\n' \
    '#___S###_#_#\n' \
    '##_#________\n' \
    '___#__##_#__\n' \
    '____##______\n' \
    '_#____#__##_\n' \
    '#___#_#____#\n' \
    '___________#\n' \
    '_#__#____#_#\n' \
    '#____#___###\n' \
    '__#_#_#_#___\n' \
    '#__##_#_#_#G\n' \
    '#__##_____##\n' \
    '#__#____#___\n' \
    '#__#_#__##_#\n' \

参考：例の作り方

import random

def generate_random_maze(X, Y):
    t = ("#", "_", "_")
    maze = []
    for y in range(Y):
        maze.append([random.choice(t) for x in range(X)])
    sx = random.choice(range(X))
    sy = random.choice(range(Y))
    gx = random.choice(range(X))
    gy = random.choice(range(Y))
    while (gx - sx) < X / 2:
        sx = random.choice(range(X))
        gx = random.choice(range(X))
    while (gy - sy) < Y / 2:
        sy = random.choice(range(Y))
        gy = random.choice(range(Y))        
    maze[sy][sx] = 'S'
    maze[gy][gx]= 'G'
    return maze

def stringize_maze(maze):
    str = ""
    for maz in maze:
        str += "".join(maz) + "\n"
    return str

string_maze = stringize_maze(generate_random_maze(12, 10))
print(string_maze)

問５：できるだけ少ない枚数の硬貨で支払いたい

財布の中に500円玉が n₁ 枚、100円玉が n₂ 枚、5０円玉が n₃ 枚、1０円玉が n₄ 枚、5円玉が n₅ 枚、1円玉が n₆ 枚あります。できるだけ少ない枚数の硬貨で、お釣りなしで x 円を支払いたいとき、必要な硬貨の枚数を返す関数を作りなさい。そのような支払い方ができない場合は False を返してください。

ただし、

0 ≤ n₁ ≤ 10
0 ≤ n₂ ≤ 10
0 ≤ n₃ ≤ 10
0 ≤ n₄ ≤ 10
0 ≤ n₅ ≤ 10
0 ≤ n₆ ≤ 10
0 ≤ x ≤ 10⁴

とする。

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

【ヒント】「貪欲法」を使う典型的な問題です。

例5-1

x =  1672

例5-2

x =  5549

例5-3

x =  3067

例5-4

x =  8802

False

例5-5

x =  -124

False

参考：例の作り方

import random
x = random.randint(0, 10000)