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

問２６：ラグランジュ補間

以下のように、それぞれ３つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた３つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された１１個の観測点でしか行えず、得られた観測値をそれぞれ fx_observed, hx_observed, gx_observed とする。

import numpy as np
f = lambda x: 1/(1 + np.exp(-x))
g = lambda x: 1.0/(1.0+x**2)
h = lambda x: np.sin(x)

x_observed = np.linspace(-10, 10, 11) # 観測点

fx_observed = f(x_observed) # f(x) の観測値
gx_observed = g(x_observed) # g(x) の観測値
hx_observed = h(x_observed) # h(x) の観測値

ラグランジュ補間を用いて、 $y = f(x)$, $y = g(x)$, $y = h(x)$ を補間しなさい。ただし、 Scipy は用いないものとする（答え合わせに使うのは良い）。また、そのアルゴリズムを説明しなさい。

インターネットで検索して得たプログラムをそのまま使ったり改変して使っても構いませんが、そのときは取得元のURLを明記してください。

問２７：スプライン補間

以下のように、それぞれ３つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた３つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された１１個の観測点でしか行えず、得られた観測値をそれぞれ fx_observed, hx_observed, gx_observed とする。

import numpy as np
f = lambda x: 1/(1 + np.exp(-x))
g = lambda x: 1.0/(1.0+x**2)
h = lambda x: np.sin(x)

x_observed = np.linspace(-10, 10, 11) # 観測点

fx_observed = f(x_observed) # f(x) の観測値
gx_observed = g(x_observed) # g(x) の観測値
hx_observed = h(x_observed) # h(x) の観測値

スプライン補間を用いて、 $y = f(x)$, $y = g(x)$, $y = h(x)$ を補間しなさい。ただし、 Scipy は用いないものとする（答え合わせに使うのは良い）。また、そのアルゴリズムを説明しなさい。

インターネットで検索して得たプログラムをそのまま使ったり改変して使っても構いませんが、そのときは取得元のURLを明記してください。

問２８：多項式近似

以下のように、それぞれ３つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた３つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された１１個の観測点でしか行えず、得られた観測値をそれぞれ fx_observed, hx_observed, gx_observed とする。

import numpy as np
f = lambda x: 1/(1 + np.exp(-x))
g = lambda x: 1.0/(1.0+x**2)
h = lambda x: np.sin(x)

x_observed = np.linspace(-10, 10, 11) # 観測点

fx_observed = f(x_observed) # f(x) の観測値
gx_observed = g(x_observed) # g(x) の観測値
hx_observed = h(x_observed) # h(x) の観測値

$y = f(x)$, $y = g(x)$, $y = h(x)$ を多項式近似しなさい。ただし、 Scipy および Numpy.polyfit は用いないものとする（答え合わせに使うのは良い）。また、そのアルゴリズムを説明しなさい。

インターネットで検索して得たプログラムをそのまま使ったり改変して使っても構いませんが、そのときは取得元のURLを明記してください。

問２９：一方通行の街を通り抜ける

街 $C$ は $n$ 個の交差点から成っています。この街は一方通行の道が多く、どの交差点からどの交差点に行けるかは正方行列 $G$ で表されています。交差点 $i$ から交差点 $j$ に行ける場合は $G_{i,j} = 1$, 行けない場合は $G_{i,j} = 0$ です（ただし $0$ ≤ $i, j$ ≤ $n - 1$）。双方向通行が可能な場合は $G_{i,j} = G_{j,i} = 1$ となっています。いま、街 $C$ に交差点 $0$ から入り、交差点 $n - 1$ から出て通り抜けようとしています。通り抜けることができる経路を全て列挙する関数を作成しなさい。ただし、同じ交差点は２度通らないこととします。また、通り抜けることができない場合は、空の配列を返すようにしなさい。

例29-1

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

[[0, 2, 3, 4]]

例29-2

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

[[0, 1, 4, 7], [0, 1, 3, 6, 7]]

例29-3

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

[[0, 7],
 [0, 5, 2, 6, 3, 7],
 [0, 5, 2, 3, 7],
 [0, 5, 1, 6, 3, 7],
 [0, 5, 1, 6, 2, 3, 7]]

例29-4

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

[]

参考：例の作り方

import numpy as np
n = 8
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 i == j:
            G[i][j] = 0
G

問３０：二色で塗り分ける

ノード数 $n$ の無向グラフが隣接行列 $G$ で表されています。 $G$ は $n$ 行 $n$ 列の正方対称行列で、ノード $i$ とノード $j$ が隣接していれば $G_{i,j} = 1$、隣接していなければ $G_{i,j} = 0$ になっています。

隣接しているノードは必ず違う色になるように、ノードに色を塗ることにします。$G$ を入力した時に、二色で塗り分けることができる場合は True, できない場合は False を返す関数を作成しなさい。

例30-1

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

True

例30-2

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

False

例30-3

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

True

例30-4

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

False

参考：例の作り方

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