プログラミング問題集（問１〜問５）

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

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

ただし、

* n &le; 50
* 1 &le; m &le; 10<sup>4</sup>
* 1 &le; k<sub>i</sub> &le; 10<sup>3</sup> 

とする。

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

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

## 例1-1

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

```python
False
```

## 例1-2

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

```python
True
```

## 例1-3

```python
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]
```

```python
True
```

## 例1-4

```python
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]
```

```python
False
```

## 例1-5

```python
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]
```

```python
True
```

## 例1-6

```python
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]
```

```python
False
```

## 参考：例の作り方

```python
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<sub>i</sub> とする。その中から３本を取り出し、できるだけ周長の長い三角形を作りたい。そのような三角形が存在するときは、最長の周長を出力し、存在しないときは 0 を出力する関数を作成しなさい。

ただし、

* 3 &le; n &le; 100
* 1 &le; a<sub>i</sub> &le; 10<sup>3</sup>

とする。

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


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

## 例2-1

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

```python
127.65
```

## 例2-2

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

```python
0
```

## 例2-3

```python
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]
```

```python
2927.8
```


## 例2-4

```python
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]
```

```python
2932.89
```

## 参考：例の作り方

```python
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<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub> を入力した時、その中からいくつか選び、その和が m にできれば True を、できなければ False を返す関数を作りなさい。

ただし、

* 1 &le; n &le; 20
* -10<sup>4</sup> &le; a<sub>i</sub> &le; 10<sup>4</sup>
* -10<sup>4</sup> &le; m &le; 10<sup>4</sup>

とする。

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


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

## 例3-1

```python
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
```

```python
True
```

## 例3-2

```python
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
```

```python
True
```

## 例3-3

```python
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
```

```python
True
```

## 例3-4

```python
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
```

```python
False
```

## 参考：例の作り方

```python
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 &le; 100

とする。

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


> 【ヒント】 <font color="#ffffff">「幅優先探索」を使う典型的な問題です。</font>

## 例4-1

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

```python
13
```

## 例4-2

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

```python
False
```

## 例4-3

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

```python
38
```

## 例4-4

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

```python
23
```

## 参考：例の作り方

```python
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<sub>1</sub> 枚、100円玉が n<sub>2</sub> 枚、5０円玉が n<sub>3</sub> 枚、1０円玉が n<sub>4</sub> 枚、5円玉が n<sub>5</sub> 枚、1円玉が n<sub>6</sub> 枚あります。できるだけ少ない枚数の硬貨で、お釣りなしで x 円を支払いたいとき、必要な硬貨の枚数を返す関数を作りなさい。そのような支払い方ができない場合は False を返してください。

ただし、

* 0 &le; n<sub>1</sub> &le; 10
* 0 &le; n<sub>2</sub> &le; 10
* 0 &le; n<sub>3</sub> &le; 10
* 0 &le; n<sub>4</sub> &le; 10
* 0 &le; n<sub>5</sub> &le; 10
* 0 &le; n<sub>6</sub> &le; 10
* 0 &le; x &le; 10<sup>4</sup>

とする。

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


> 【ヒント】 <font color="#ffffff">「貪欲法」を使う典型的な問題です。</font>

## 例5-1

```python
x =  1672
```

```python
9
```

## 例5-2

```python
x =  5549
```

```python
24
```

## 例5-3

```python
x =  3067
```

```python
11
```

## 例5-4

```python
x =  8802
```

```python
False
```

## 例5-5

```python
x =  -124
```

```python
False
```

## 参考：例の作り方

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