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

プログラミング問題集(問21〜問25)

問21:オイラー法

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

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

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

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

解答例

問22:ルンゲ・クッタ法

$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を明記してください。

解答例

問23:最初に基準を超える者

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

ただし、

  • 1 ≤ $n$ ≤ 106
  • 0 ≤ $a_1$ ≤ $a_2$ ≤ ... ≤ $a_n$ ≤ 109
  • 0 ≤ $k$ ≤ 109

とする。

例23-1

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

例23-2

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

例23-3

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

例23-4

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

参考:例の作り方

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)

解答例

問24:同じ長さの紐が k 本欲しい

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

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

  • 1 ≤ $k$ ≤ 104
  • 1 ≤ $n$ ≤ 104
  • 1 ≤ $L_i$ ≤ 105

とする。

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

解答例

問25: 最長回路発見

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

例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

解答例

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