プログラミング問題集（問１６〜問２０）


# 問１６：連立一次方程式（ガウスの消去法）

連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ガウスの消去法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をガウスの消去法で解くプログラムを作成しなさい。ただし、Sympy, Numpy.ligalg, Scipy.ligalg は使わないこと（答え合わせに使うのは良い）。また、参考に用いた書籍またはウェブサイトがある場合はそれを明記すること。

$3 x_1 + 2 x_2 + 7 x_3 + x_4 = 8$
$x_1 + 5 x_2 + x_3 - x_4 = 5$
$4 x_1 + x_2 + 3 x_3 - 2 x_4 = 7$
$x_1 + 6 x_2 + 4 x_3 + 3 x_4 = 13$



# 問１７：連立一次方程式（ヤコブ法）→すみません、解けませんので問題取り消します

連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ヤコブ法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をヤコブ法で解くプログラムを作成しなさい。ただし、Sympy, Numpy.ligalg, Scipy.ligalg は使わないこと（答え合わせに使うのは良い）。参考に用いた書籍またはウェブサイトがある場合はそれを明記すること。

$3 x_1 + 2 x_2 + 7 x_3 + x_4 = 8$
$x_1 + 5 x_2 + x_3 - x_4 = 5$
$4 x_1 + x_2 + 3 x_3 - 2 x_4 = 7$
$x_1 + 6 x_2 + 4 x_3 + 3 x_4 = 13$

# 問１８：ナップサック問題

重さが $W_i$、価値が $V_i$ である $n$ 個のアイテムがあります。これらの中から、重さの和が $x$ を超えない範囲内でアイテムを選んだときの、価値の和の最大値を求めなさい。

ただし、同じアイテムは１個しか選べないものとし、

* 1 &le; $n$ &le; 100
* 1 &le; $W_i$ &le; 100
* 1 &le; $V_i$ &le; 100
* 10n &le; $x$ &le; 100n

とする。

> 【ヒント】  <font color="#ffffff">「動的計画法」で解ける問題として典型的なものです。「再帰」を使って解けます。単純な探索では、同じ計算を繰り返して無駄な時間を使ってしまいます。これを避けるため、計算結果を格納する２次元配列を作って記憶することで、２度目以降の計算を省略するようにしてみましょう。</font>

## 例18-1

```python
n =  5
x =  175
W =  [95, 56, 65, 54, 32]
V =  [79, 9, 57, 55, 27]
```

```python
139
```

## 例18-2

```python
n =  10
x =  492
W =  [53, 64, 82, 93, 76, 67, 10, 6, 82, 91]
V =  [80, 16, 30, 68, 31, 19, 50, 64, 20, 96]
```

```python
438
```

## 例18-3

```python
n =  20
x =  1371
W =  [30, 31, 100, 83, 52, 97, 34, 70, 96, 13, 70, 89, 79, 51, 31, 93, 73, 10, 77, 31]
V =  [31, 58, 49, 75, 1, 57, 8, 1, 35, 22, 82, 28, 61, 46, 68, 10, 32, 84, 19, 16]
```

```python
783
```

## 例18-4

```python
n =  40
x =  2250
W =  [96, 64, 21, 86, 49, 72, 4, 90, 91, 91, 43, 95, 89, 23, 38, 58, 29, 43, 27, 3, 47, 29, 5, 90, 46, 100, 94, 56, 49, 62, 46, 51, 41, 28, 47, 61, 28, 100, 91, 80]
V =  [74, 83, 57, 64, 63, 58, 100, 59, 66, 66, 85, 55, 86, 25, 41, 64, 26, 1, 87, 88, 73, 98, 57, 63, 31, 69, 21, 79, 96, 13, 2, 50, 89, 10, 11, 93, 45, 31, 15, 67]
```

```python
2260
```

## 例18-5

```python
n =  80
x =  2685
W =  [7, 32, 92, 96, 96, 77, 49, 84, 80, 22, 14, 87, 4, 61, 27, 90, 23, 98, 59, 80, 25, 45, 14, 46, 41, 72, 86, 40, 27, 97, 96, 52, 86, 85, 55, 48, 92, 69, 57, 89, 2, 63, 20, 80, 98, 85, 31, 86, 65, 87, 94, 27, 95, 43, 27, 24, 65, 9, 81, 53, 36, 43, 14, 98, 85, 9, 66, 45, 49, 10, 68, 19, 5, 61, 53, 76, 75, 75, 55, 36]
V =  [71, 6, 45, 90, 41, 89, 5, 57, 19, 78, 79, 100, 9, 45, 84, 41, 90, 18, 100, 34, 60, 6, 7, 82, 64, 40, 17, 44, 85, 94, 33, 90, 36, 50, 46, 66, 6, 57, 36, 4, 15, 50, 23, 94, 99, 26, 33, 95, 16, 45, 6, 93, 37, 89, 13, 52, 4, 92, 86, 10, 41, 12, 85, 43, 98, 92, 57, 38, 75, 61, 66, 1, 74, 61, 91, 33, 35, 96, 13, 17]
```

```python
3594
```

## 例18-6

```python
n =  100
x =  1913
W =  [17, 22, 91, 12, 12, 76, 56, 86, 63, 42, 26, 15, 8, 11, 99, 60, 30, 90, 35, 92, 10, 49, 39, 58, 60, 80, 28, 9, 47, 43, 87, 55, 54, 46, 33, 50, 67, 52, 2, 51, 6, 50, 1, 83, 64, 58, 47, 63, 99, 6, 65, 17, 11, 99, 94, 23, 75, 8, 87, 44, 40, 53, 60, 69, 2, 74, 73, 44, 77, 21, 30, 51, 50, 63, 64, 21, 72, 6, 28, 19, 78, 38, 71, 68, 84, 92, 60, 34, 63, 17, 86, 22, 79, 48, 98, 40, 39, 41, 72, 30]
V =  [47, 44, 4, 11, 94, 44, 20, 2, 61, 59, 31, 20, 87, 18, 16, 79, 2, 2, 58, 31, 67, 35, 19, 39, 30, 15, 63, 31, 70, 13, 35, 50, 20, 18, 6, 8, 49, 13, 44, 60, 65, 5, 51, 15, 84, 74, 50, 34, 35, 91, 97, 18, 54, 27, 3, 29, 86, 44, 74, 94, 85, 75, 92, 66, 83, 34, 63, 74, 8, 62, 25, 68, 45, 59, 28, 54, 75, 98, 8, 35, 98, 42, 22, 51, 48, 43, 29, 73, 68, 41, 78, 62, 61, 4, 44, 91, 10, 35, 22, 51]
```

```python
3388
```

## 参考：例の作り方

```python
import random
n = 10
x = random.randint(n * 10, n * 100)
W = [random.randint(1, 100) for _ in range(n)]
V = [random.randint(1, 100) for _ in range(n)]
```


# 問１９：最長共通部分列

長さ $n$ の文字列 $s$ と、長さ $m$ の文字列 $t$ を入力としたとき、その２つの文字列の最長共通部分列の長さを求める関数を作りなさい。

ただし、

* 1 &le; $n$ &le; 10<sup>4</sup>
* 1 &le; $m$ &le; 10<sup>4</sup>

とする。

> 【ヒント】 <font color="#ffffff">これも「動的計画法」で解けます。またこの解法は、生命情報学（バイオインフォマティクス」という分野で日常的に用いられる配列相同性検索の基礎となるものです。</font>

## 例19-1

```python
s = "pencil"
t = "penguin"
```

```python
4
```

## 例19-2

```python
s = "dreamingly"
t = "dreadfully"
```

```python
6
```

## 例19-3

```python
s = "This is a pen. This is an apple."
t = "pen-pineapple-apple-pen"
```

```python
10
```

## 例19-4

```python
s = "There is more to life than increasing its speed. "\
      "(by Mahatma Gandhi)"

t = "There is always light behind the clouds. "\
      "(by Louisa May Alcott)"
```

```python
31
```

## 例19-5

```python
s = "If you want to be successful, it's just this simple: "\
      "Know what you are doing, love what you are doing, "\
      "and believe in what you are doing. "\
      "(by Will Rogers)"

t = "Success is not the key to happiness. "\
      "Happiness is the key to success. "\
      "If you love what you are doing, "\
      "you will be successful. "\
      "(by Louisa May Alcott)"
```

```python
71
```


# 問２０：個数制限なしナップサック問題

重さが $W_i$、価値が $V_i$ である $n$ 個のアイテムがあります。これらの中から、重さの和が $x$ を超えない範囲内でアイテムを選んだときの、価値の和の最大値を求めなさい。

ただし、同じアイテムをいくつでも選べるものとし、

* 1 &le; $n$ &le; 100
* 1 &le; $W_i$ &le; 100
* 1 &le; $V_i$ &le; 100
* 1 &le; $x$ &le; 10<sup>4</sup>

とする。

> 【ヒント】 <font color="#ffffff">「同じアイテムをいくつでも選べる」というだけで、問６よりも格段に難しくなります。「同じアイテムをいくつでも」をループとして表現してしまうと、計算量が大きくなりすぎるため避けたいところです。重さの上限が x という条件においてアイテム i を k 個選ぶという状況を、重さの上限が x - W<sub>i</sub> という条件においてアイテム i を k - 1 個選ぶという状況と比較して考えます。</font>

## 例20-1

```python
n = 3
W = [3, 4, 2]
V = [4, 5, 3]
x = 7
```

```python
10
```

## 例20-2

```python
n =  10
x =  867
W =  [28, 92, 30, 1, 40, 33, 96, 30, 38, 86]
V =  [6, 77, 53, 91, 47, 33, 28, 28, 78, 36]
```

```python
78897
```

## 例20-3

```python
n =  20
x =  1272
W =  [10, 87, 38, 74, 19, 93, 34, 24, 63, 12, 31, 99, 45, 4, 22, 81, 50, 75, 36, 20]
V =  [1, 96, 33, 97, 58, 31, 68, 60, 23, 60, 27, 7, 24, 70, 60, 73, 11, 88, 87, 71]
```

```python
22260
```

## 例20-4

```python
n =  40
x =  3309
W =  [20, 5, 85, 84, 10, 15, 80, 24, 48, 96, 33, 18, 22, 58, 62, 24, 12, 73, 76, 9, 53, 7, 47, 82, 69, 82, 57, 33, 60, 10, 84, 16, 97, 9, 57, 92, 22, 1, 70, 26]
V =  [83, 17, 72, 71, 40, 16, 94, 78, 41, 43, 38, 21, 3, 35, 58, 59, 63, 75, 5, 64, 75, 30, 48, 45, 69, 7, 25, 37, 80, 70, 93, 68, 41, 34, 60, 39, 8, 86, 64, 27]
```

```python
284574
```

## 例20-5

```python
n =  40
x =  1747
W =  [60, 76, 2, 14, 89, 88, 83, 27, 55, 10, 53, 58, 60, 45, 90, 73, 32, 54, 90, 97, 28, 54, 10, 70, 73, 61, 5, 14, 35, 65, 57, 12, 9, 85, 98, 51, 49, 13, 98, 16]
V =  [23, 25, 14, 1, 39, 18, 16, 81, 67, 75, 14, 23, 95, 58, 47, 99, 33, 100, 9, 19, 57, 52, 36, 16, 30, 83, 99, 61, 97, 74, 16, 27, 70, 81, 84, 13, 28, 14, 12, 27]
```

```python
34565
```

## 参考：例の作り方
```python 
import random
n = 40
x = random.randint(n * 10, n * 100)
W = [random.randint(1, 100) for _ in range(n)]
V = [random.randint(1, 100) for _ in range(n)]

print("n = ", n)
print("x = ", x)
print("W = ", W)
print("V = ", V)
```