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

プログラミング問題集(問16〜問20)

問16:連立一次方程式(ガウスの消去法)

連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ガウスの消去法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をガウスの消去法で解くプログラムを作成しなさい。ただし、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$

解答例

問17:連立一次方程式(ヤコブ法)→すみません、解けませんので問題取り消します

連立一次方程式を解くアルゴリズムには様々なものがあるが、その中で「ヤコブ法」について調べ、そのアルゴリズムを説明しなさい。また、次の連立方程式をヤコブ法で解くプログラムを作成しなさい。ただし、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$

問18:ナップサック問題

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

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

  • 1 ≤ $n$ ≤ 100
  • 1 ≤ $W_i$ ≤ 100
  • 1 ≤ $V_i$ ≤ 100
  • 10n ≤ $x$ ≤ 100n

とする。

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

例18-1

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

例18-2

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]
438

例18-3

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]
783

例18-4

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]
2260

例18-5

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]
3594

例18-6

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]
3388

参考:例の作り方

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

解答例

問19:最長共通部分列

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

ただし、

  • 1 ≤ $n$ ≤ 104
  • 1 ≤ $m$ ≤ 104

とする。

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

例19-1

s = "pencil"
t = "penguin"
4

例19-2

s = "dreamingly"
t = "dreadfully"
6

例19-3

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

例19-4

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)"
31

例19-5

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)"
71

解答例

問20:個数制限なしナップサック問題

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

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

  • 1 ≤ $n$ ≤ 100
  • 1 ≤ $W_i$ ≤ 100
  • 1 ≤ $V_i$ ≤ 100
  • 1 ≤ $x$ ≤ 104

とする。

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

例20-1

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

例20-2

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]
78897

例20-3

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]
22260

例20-4

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]
284574

例20-5

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]
34565

参考:例の作り方

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)

解答例

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