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に移します。ただし、移動の途中で円盤の大小…