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

プログラミング問題集(問6〜問10)

問6:二分法

方程式 $f(x) = 0$ の解を求める方法として代表的なものに、二分法とニュートン法がある。二分法は、関数 $y=f(x)$が区間 $[a,b]$ で連続で、解が1つ存在するときに使える。

二分法による解法は、以下の通りである。

  • 区間 $[a,b]$ を2つに分け、その中点をcとする。
  • $f(a)\cdot f(c)$ が負であれば、区間 $[a,c]$ の中に $x$ 軸との交点があるはず。
  • $f(a)\cdot f(c)$ が正であれば、区間 $[c,b]$の中に $x$ 軸との交点があるはず。

というのを繰り返す。

方程式 $e^x - 3 x = 0$ を、区間 [0, 1] に対する二分法を用いて解きなさい。ただし、誤差 $\epsilon < 0.00001$ とする。また、numpy, scipy, sympy などを使うと便利だが、この問題は二分法の理解とPythonでの実装の練習を兼ねているため、これらのライブラリを用いないこと。

# アウトプット例
0.61906128673
  • 誤差 $\epsilon$ の値を変化させた場合にこのアルゴリズムの挙動がどう変化するか答えよ。
  • 同様に方程式 $tanh X + X + 2 = 0$ の解を二分法で求めよ

解答例

問7:ニュートン法

方程式 $f(x) = 0$ の解を求める方法として代表的なものに、二分法とニュートン法がある。ニュートン法は、関数 $y=f(x)$ が単調連続で変曲点がなく、かつ $f(x)$ の導関数が求められるときに使える。

ニュートン法による解法は、次の通りである。

  • ある $x$ における接線を求め、その $x$ 軸との交点を求める。
  • その $x$ 軸との交点の $x$ 座標を新たなxとし、その $x$ における接線を求める。

というのを繰り返す。

方程式 $e^x - 3 x = 0$ を、ニュートン法を用いて解きなさい。ただし、計算は x = 0 からスタートし、$\epsilon < 0.00001$ としたとき以下の収束条件(のいずれか)を用いるものとする。

  1. $|\ f(X_n)\ | < \epsilon$
  2. $|\ X_{n+1} - X_{n}\ | < \epsilon$
  3. $|\ (X_{n+1} - X_{n})\ /\ X_{n}\ | < \epsilon$
  4. $|\ f(X_{n+1}) - f(X_{n})\ | < \epsilon$

また、numpy, scipy, sympy などを使うと便利だが、この問題は二分法の理解とPythonでの実装の練習を兼ねているため、これらのライブラリを用いないこと。

# アウトプット例
0.61906128673
  • 上記の収束条件を変更したときにアルゴリズムの挙動がどう変化するか答えよ。
  • 同様に方程式 $x^2 - 2 x + 1 = 0$ の解をニュートン法で求めよ。
  • 同様に方程式 $e^x sin x - 2 x = 0$ $(0 < x < π)$ の解をニュートン法で求めよ。

解答例

問8:約数

整数 $n$ を入力すると、その約数を列挙する関数を作りなさい。また、そのアルゴリズムを説明せよ。

ただし、$1 \leqq n\leqq 10^6$ とする。

例8-1

n = 60
[2, 3, 4, 5, 6, 10, 12, 15, 20, 30]

例8-2

n = 136
[2, 4, 8, 17, 34, 68]

例8-3

n = 8075
[5, 17, 19, 25, 85, 95, 323, 425, 475, 1615]

解答例

問9:素数判定

整数 $n$ を入力すると、それが素数なら True、素数でなければ False を返す関数を作りなさい。また、そのアルゴリズムを説明せよ。

ただし、$1 \leqq n \leqq 10^6$ とする。

例9-1

n = 53
True

例9-2

n = 12357
False

例9-3

n = 941471
True

解答例

問10:素因数分解

整数 $n$ を入力すると、素因数分解する関数を作りなさい。また、そのアルゴリズムを説明せよ。

ただし、$1 \leqq n \leqq 10^6$ とする。

例10-1

n = 60
[2, 2, 3, 5]

例10-2

n = 136
[2, 2, 2, 17]

例10-3

n = 8075
[5, 5, 17, 19]

解答例

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