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

プログラミング問題集(問26〜問30)

問26:ラグランジュ補間

以下のように、それぞれ3つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた3つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された11個の観測点でしか行えず、得られた観測値をそれぞれ 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を明記してください。

解答例

問27:スプライン補間

以下のように、それぞれ3つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた3つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された11個の観測点でしか行えず、得られた観測値をそれぞれ 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を明記してください。

解答例

問28:多項式近似

以下のように、それぞれ3つの関数 $y = f(x)$, $y = g(x)$, $y = h(x)$ に基づいた3つの現象が存在するものとする。ただし、$y = f(x)$, $y = g(x)$, $y = h(x)$ は未知であるとする。それを観測するための実験は、下記の x_observed で示された11個の観測点でしか行えず、得られた観測値をそれぞれ 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を明記してください。

解答例

問29:一方通行の街を通り抜ける

街 $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$ から出て通り抜けようとしています。通り抜けることができる経路を全て列挙する関数を作成しなさい。ただし、同じ交差点は2度通らないこととします。また、通り抜けることができない場合は、空の配列を返すようにしなさい。

例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

解答例

問30:二色で塗り分ける

ノード数 $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

解答例

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