next up previous contents index
: 章末付録: パーソナルコンピュータの歴史 : ユークリッドの互除法とその計算量 : 参考: 領域計算量と時間計算量   目次   索引

章末の問題

  1. (計算量 -- computational complexity -- の理論への導入) prime_factorization N % K が何回実行されたかを数えることができるように改良し, 入力する数 N をいろいろ変えて実行しこの余りを求める演算が 何回実行されるか記録しなさい. それをグラフにまとめなさい (方眼紙またはそれに 準ずるものを用いてきれいに書こう).
  2. フィボナッチ数 $F_0, \ldots, F_{200}$ を求めるプログラム を書きなさい.
  3. ${\rm gcd}(F_k,F_{k-1}) = 1$ であることを証明せよ.
  4. $1000000000000283$ は二つの素数に分解する. この分解を試みよ.



Nobuki Takayama 平成15年9月12日