問２１：オイラー法

$x_0 = 1$ で $y_0 = 2$ となる初期条件で微分方程式

$$\frac{dy}{d x} = 2 - \frac{y}{x}$$

を満足する関数 $y$ の $x = 2$ における値をEuler法で求めるためのプログラムをPythonで作成してください。また、そのアルゴリズムを説明してください。刻み幅を変えた時にどうなるかも考察してください。

ただし Sympy や Scipy.integrate.odeint を使わないこと（答え合わせには使っても良い）。インターネットで検索して得たプログラムをそのまま使ったり改変して使っても構いませんが、そのときは取得元のURLを明記してください。

問２２：ルンゲ・クッタ法

$x_0 = 1$ で $y_0 = 2$ となる初期条件で微分方程式

$$\frac{dy}{d x} = 2 - \frac{y}{x}$$

を満足する関数 $y$ の $x = 2$ における値をRunge-Kutta法で求めるためのプログラムをPythonで作成してください。また、そのアルゴリズムを説明してください。刻み幅を変えた時にどうなるかも考察してください。

ただし Sympy や Scipy.integrate.odeint を使わないこと（答え合わせには使っても良い）。インターネットで検索して得たプログラムをそのまま使ったり改変して使っても構いませんが、そのときは取得元のURLを明記してください。

問２３：最初に基準を超える者

長さ $n$ の単調非減少な数列 $a_0, a_1, ..., a_{n-1}$ と、実数 $k$ を入力したとき、$a_i$ ≥ $k$ となるような最小の $i$ を返す関数を作りなさい。そのような $i$ が存在しない場合には $n$ を返すようにしなさい。

ただし、

1 ≤ $n$ ≤ 10⁶
0 ≤ $a_1$ ≤ $a_2$ ≤ ... ≤ $a_n$ ≤ 10⁹
0 ≤ $k$ ≤ 10⁹

とする。

例23-1

n =  8
a =  [3, 4, 4, 4, 7, 9, 10, 10]
k =  8

例23-2

n =  8
a =  [3, 4, 4, 4, 7, 9, 10, 10]
k =  4

例23-3

n =  8
a =  [3, 4, 4, 4, 7, 9, 10, 10]
k =  0

例23-4

n =  8
a =  [3, 4, 4, 4, 7, 9, 10, 10]
k =  20

参考：例の作り方

import random
n = 8
a = sorted([random.randint(1, 10) for _ in range(n)])
k = random.randint(1, 10)

print("n = ", n)
print("a = ", a)
print("k = ", k)

問２４：同じ長さの紐が k 本欲しい

長さ $x$ の紐が $k$ 本欲しい。手元にあるのは、長さが $L_i$ であるような $n$ 本の紐である。このとき、$x$ の最大値を小数点以下２桁までを切り捨てで出力する関数を作りなさい。

ただし、$x$ や $L$ は実数とし、

1 ≤ $k$ ≤ 10⁴
1 ≤ $n$ ≤ 10⁴
1 ≤ $L_i$ ≤ 10⁵

とする。

例24-1

n =  3
k =  2
L =  [7.47, 6.66, 4.11]

6.66

例24-2

n =  4
k =  5
L =  [2.86, 2.69, 2.05, 5.23]

2.05

例24-3

n =  5
k =  9
L =  [6.33, 3.18, 6.92, 9.38, 8.96]

3.16

例24-4

n =  6
k =  6
L =  [2.7, 6.85, 9.44, 6.27, 2.83, 5.21]

3.42

例24-5

n =  7
k =  11
L =  [2.16, 6.1, 5.85, 7.76, 9.67, 7.41, 2.29]

2.92

参考：例の作り方

import random
from math import floor

n = 3
k = random.randint(int(n / 2), n * 2)
L = [floor((random.random() * 9 + 1) * 100)  / 100 for _ in range(n)]

print("n = ", n)
print("k = ", k)
print("L = ", L)

問２５：最長回路発見

ノード数 $n$ の無向グラフが隣接行列 $G$ で表されています。 $G$ は $n$ 行 $n$ 列の正方対称行列で、ノード $i$ とノード $j$ が隣接していれば $G_{i,j} = 1$、隣接していなければ $G_{i,j} = 0$ になっています。 $G$ を入力した時に、最大ノード数をもつ回路のうち１つを出力する関数を作成しなさい。回路が存在しない場合は、空の配列を返すようにしなさい。

例25-1

n =  5
G = \
[[0, 0, 0, 0, 1],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 1, 0],
 [0, 1, 1, 0, 1],
 [1, 1, 0, 1, 0]]

[1, 4, 3]

例25-2

n =  8
G = \
[[0, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 1, 0],
 [1, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 1, 0, 1],
 [0, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 1, 0, 0, 1, 0],
 [0, 1, 1, 0, 1, 1, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 0]]

[]

例25-3

n =  10
G = \
[[0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 0, 0, 0, 0, 0, 1, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
 [0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
 [0, 1, 1, 0, 0, 0, 0, 1, 0, 0],
 [1, 0, 0, 1, 0, 0, 1, 0, 0, 0]]

[0, 9, 3, 7, 8, 1]

参考：例の作り方

import numpy as np
n = 5
G = np.where(np.random.rand(n, n) < 0.7, 0, 1).tolist()
for i in range(len(G)):
    for j in range(len(G)):
        if G[i][j] != G[j][i]:
            G[i][j] = G[j][i]
        if i == j:
            G[i][j] = 0
G