練習問題の回答例#
- FizzBuzz
- Scheme
- うるう年測定
- ループ練習
- ループ練習2
- カレンダー出力
- シェルピンスキーのギャスレット
- ハノイの塔
- ひらがな2文字をランダムで出力するプログラム
- フィボナッチ数列1
- フィボナッチ数列2
- 干支を求めるプログラム
- 数当てゲーム
- 世界のナベアツ問題
- 線形合同法
- 素数を求める
- 素数判定
- 転置行列
- 二次方程式の解
- 平方根
- 有理化するプログラム
- 累乗
- 連立方程式を解く
- Haskell
- Scala
- クリティカルパス
- 迷路を解くプログラム
- 平方根を簡単な形にするプログラム
- ボウリングのスコア計算
- Nクイーン問題
- 英単語しりとりプログラム
- C++11
- オリンピックの開催年を出力するプログラム
- 回文判定プログラム
- 配列から大きい要素とその添字を求めるプログラム
- 星座を求めるプログラム
- Hit and Blow
- Base64
- 配列いじり
- うるう年判定
- Caesar暗号解読
フィボナッチ数列 課題3#
- 再帰版の利点
- フィボナッチ数列の定義を直接に表現でき、読み書きに優れる。（この性質はこの問題に限らず、難問でも自然に思いつきやすい。）
- 再帰版の欠点
- 素朴な実装では同じ値を何度も計算するため計算量が指数的増加 O(1.618^n) となり、大きいフィボナッチ数の算出は文字通り桁違いに遅くなる（これは問題依存。再帰が常に爆発的計算量というわけではない）。なのでメモ化しよう！
また再帰が深くなるとコールスタックが溢れて関数呼び出し限界を迎えて異常停止する。関数呼び出し自体もオーバーヘッドがあり若干のコストだ。
- 反復版
- 途中結果を保持しながら順に計算するため計算量が線形 O(n) で高速。スタックオーバーフローの心配もない。ただし、数列の定義との対応は再帰版ほど直感的でない。