ホーム‎ > ‎Python入門 (2008)‎ > ‎

Python発展課題

発展課題

時間の余った人、興味のある人向けの課題です。書かれたことをこなすだけでなく、課題を自分で発展させることも考えてみてください。

発展課題1

1000以下の素数を求めるプログラムを作成してください。
通常これはエラトステネスの篩というアルゴリズムを用いて求めます。具体的には以下のようになります。
2から1000までの整数を用意する。
2を残して、2の倍数を取り除く。
残っている数のうち、2の次に小さい数は3だから、3を残して3の倍数を取り除く。
残っている数のうち、3の次に小さい数は5だから、5を残して5の倍数を取り除く。
以下、取り除く数がなくなるまで同様の操作を繰り返す。
最後まで残っている数が1000以下の素数となります。

発展課題2

c, x_0を正の実数として、数列
x_{n+1} = (x_n^2 + c)/(2x_n)
を適当な項まで計算するプログラムを作成してください。途中経過も表示してください。(この数式はTeX風に書いてあり、^2は2乗を表しています。Pythonにおける^とは意味が異なるので注意してください。)

これはいわゆるニュートン法を使ってcの平方根を求めていることになります。つまり、多項式f(x)と適当な初期値x_0について
x_{n+1} = x_n - f(x_n)/f'(x_n)
という数列を考えると、これはf(x)の零点のいずれかに収束します。しかも、その零点が単純な場合には、十分大きなnに対してx_{n+1}の誤差はx_nの誤差のほぼ2乗に減ります。

(複素数の範囲で)f(x)の各零点について、ニュートン法によってそこに収束する初期値の集合というものが考えられます。f(x)が極端に簡単なものでなければ、それらの集合の境界はジュリア集合というフラクタル図形になります。

発展課題3

入力された正整数nについて、
nが偶数なら2で割る
そうでなければ3倍して1を足す
その結果を次のnの値とする
という処理をnが1になるまで繰り返すプログラムを作成してください。途中経過も表示してください。
例えば3が入力されたとすると、計算は3, 10, 5, 16, 8, 4, 2, 1と進みます(途中経過の表示はこの通りでなくてもかまいません)。

この手続きによってnは必ず1になると思われ(てい)ますが、これはコラッツ予想、あるいは角谷予想と呼ばれる有名な未解決問題です。

更新日時:2008/06/25 23:43:56
Google Sitesに移行:2011/06/30

Comments