問１：和が m になる取り出し方
自然数 k1, k2, ..., kn が書かれた n 枚の紙片が袋に入っている。この袋から紙片を取り出し、数字を見て袋に戻すことを４回行う。その４つの数字の和が m になる取り出し方が存在するかどうか計算し、存在すれば True、 存在しなければ False と出力する関数を作成しなさい。
ただし、
- n ≤ 50
- 1 ≤ m ≤ 104
- 1 ≤ ki ≤ 103
とする。
また、データ数が増加するに伴い計算時間がどう変化するか計測して確認しなさい。
【ヒント】 ４重ループを作って総当たり検索をしましょう。ひとつでも存在が見つかればループから脱出して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 の長さは ai とする。その中から３本を取り出し、できるだけ周長の長い三角形を作りたい。そのような三角形が存在するときは、最長の周長を出力し、存在しないときは 0 を出力する関数を作成しなさい。
ただし、
- 3 ≤ n ≤ 100
- 1 ≤ ai ≤ 103
とする。
また、データ数が増加するに伴い計算時間がどう変化するか計測して確認しなさい。
【ヒント】 ３重ループで全探索しながら、最大値を見つけるたびに更新していく。
例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]
0
例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 個の整数 a1, a2, ..., an を入力した時、その中からいくつか選び、その和が m にできれば True を、できなければ False を返す関数を作りなさい。
ただし、
- 1 ≤ n ≤ 20
- -104 ≤ ai ≤ 104
- -104 ≤ m ≤ 104
とする。
また、データ数が増加するに伴い計算時間がどう変化するか計測して確認しなさい。
【ヒント】 問１と似てますが、いくつ選択するかが決まっていないという点で、違います。「深さ優先探索」を使う解法が知られています。
例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'
13
例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' \
38
例4-4
string_maze = \
'##___###_#_#\n' \
'#___S###_#_#\n' \
'##_#________\n' \
'___#__##_#__\n' \
'____##______\n' \
'_#____#__##_\n' \
'#___#_#____#\n' \
'___________#\n' \
'_#__#____#_#\n' \
'#____#___###\n' \
'__#_#_#_#___\n' \
'#__##_#_#_#G\n' \
'#__##_____##\n' \
'#__#____#___\n' \
'#__#_#__##_#\n' \
23
参考：例の作り方
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円玉が n1 枚、100円玉が n2 枚、5０円玉が n3 枚、1０円玉が n4 枚、5円玉が n5 枚、1円玉が n6 枚あります。できるだけ少ない枚数の硬貨で、お釣りなしで x 円を支払いたいとき、必要な硬貨の枚数を返す関数を作りなさい。そのような支払い方ができない場合は False を返してください。
ただし、
- 0 ≤ n1 ≤ 10
- 0 ≤ n2 ≤ 10
- 0 ≤ n3 ≤ 10
- 0 ≤ n4 ≤ 10
- 0 ≤ n5 ≤ 10
- 0 ≤ n6 ≤ 10
- 0 ≤ x ≤ 104
とする。
また、データ数が増加するに伴い計算時間がどう変化するか計測して確認しなさい。
【ヒント】 「貪欲法」を使う典型的な問題です。
例5-1
x = 1672
9
例5-2
x = 5549
24
例5-3
x = 3067
11
例5-4
x = 8802
False
例5-5
x = -124
False
参考：例の作り方
import random
x = random.randint(0, 10000)