エラトステネスのふるいとは、素数を列挙する簡単な方法です。 偶数の素数は2だけなので3以上の奇数だけを調べれば良いですね。flag[i]は2i + 3が素数かどうかを表します。（i = 0,・・・N） N = 8190なら2 × N + 3 = 16383まで調べるので1900番目の素数1638…

SICPから次の問題を解いてみたいと思います。問題 φ=(1+√5)/2 としてFib(n)がφ^n/√5 に最も近い整数であることを証明せよ。 ヒント：ψ=(1-√5)/2 とする。数学的帰納法とFibonacci数の定義を用いて Fib(n)=(φ^n-ψ^n)/√5 を証明する。 証明 任意の自然数nにつ…

再帰手続きで有名なハノイの塔をPythonで解いてみました。まずは、ハノイの塔の問題について 3本の棒a、b、cがあります。棒aに、中央に空いたn枚の円盤が大きい順に積まれています。 これを1枚ずつ移動させて棒bに移します。ただし、移動の途中で円盤の大小…

Pythonでパスカルの三角形を書いてみました。 再帰を使うととっても簡潔に書けますね。 def pascal(x, y): if(x == 1 or x == y): return 1 else: return pascal(x - 1, y - 1) + pascal(x, y - 1) def line(n): a = [] for i in range(n): a.append(pascal(…

今度は、再帰を使って書いてみました。 まずは、減算を用いたユークリッド互除法です。 public class Euclid { private static int count; public static void main(String[] args){ try{ int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args…

2つの整数m、n（m > n）をユークリッドの互除法を使って、mとnの最大公約数を求めます。 減算を使った場合のアルゴリズムは次のようになります。 １．mとnが等しくないあいだは次を繰り返す ２．m > nの場合 m = m - n それ以外 n = n - m ３．m（もしくはn…

前回のエントリーでは、再帰手続きを使って書いたのですが、これだとnが増えるごとに計算時間はどんどん遅くなってくるので実用に耐えないアルゴリズムであることは明白です。今度は配列を使って、一度計算したフィボナッチ数を記憶させてやりました。 publi…

フィボナッチ数は一般的に下記のとおりに定義されます。 f_0 = 0、f_1 = 1 f_n+2 = f_n + f_n+1 (n >= 0) これを冗長性を無視して、再帰手続きを使ってJavaで書いてみました。 public class Fibonacci { /** * フィボナッチ数列を生成するプログラム * @para…

前回エントリーのコードでforループを使ったところを再帰で書いてみました。 あと、Mathクラスを使わないように変更してみました。import java.io.*;/** * ニュートン法による平方根の計算 * */ public class Newton { private static final double EPS = 1.…

ニュートン法は、関数 f(x) とその導関数 f'(x) が与えられたとき、方程式f(x)=0 の解を求めるといったもの。 x_n+1 = x_n - f(x)/f'(x) に f(x) = x^2 - a を代入して簡約すると x_n+1 = (x_n + a / x_n) / 2 となり、これを指定した誤差以内になるまで反復…