Help us understand the problem. What is going on with this article?

プログラミング問題集(問1〜問5)

問1:和が m になる取り出し方

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

ただし、

  • n ≤ 50
  • 1 ≤ m ≤ 104
  • 1 ≤ ki ≤ 103

とする。

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

【ヒント】 4重ループを作って総当たり検索をしましょう。ひとつでも存在が見つかればループから脱出して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)

解答例

問2:三角形は作れるか?

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

ただし、

  • 3 ≤ n ≤ 100
  • 1 ≤ ai ≤ 103

とする。

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

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

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

解答例

問3:部分和問題

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

ただし、

  • 1 ≤ n ≤ 20
  • -104 ≤ ai ≤ 104
  • -104 ≤ m ≤ 104

とする。

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

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

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

解答例

問4:迷路の最短経路

大きさが X * Y (XYともに整数)の迷路が与えられます。迷路はスタート「S」とゴール「G」、通路「_」と壁「#」からできており、1ターンあたり、隣接する上下左右4マスの通路のいずれかに移動できます。スタートからゴールまで移動可能な場合は、必要な最小のターン数を返し、不可能な場合は 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)

解答例

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

財布の中に500円玉が n1 枚、100円玉が n2 枚、50円玉が n3 枚、10円玉が 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)

解答例

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away