ホーム » スタッフ » 斉藤徹 » 再帰方程式とハノイの塔

2008年4月
« 3月   5月 »
 12345
6789101112
13141516171819
20212223242526
27282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰方程式とハノイの塔

再帰を含むプログラムの速度分析の手法として、再帰方程式を説明。

  • 先週説明をした fact() の再帰方程式を示し、一般解を示す。
  • ハノイの塔のルールと、処理ステップ数がH(N)=2^N-1で示されることを、 数学的帰納法で証明。
  • 再帰による2分探索のプログラムを示し、その再帰方程式を示し、 代入法で一般解の予測式を導き出す。
  • 並び替えの処理速度を示すために、クイックソートは再帰が分かりにくいので、 マージソートにより O(N log N) を示す予定。 そのためにマージソートのアルゴリズムから、再帰方程式を示すまでを説明。

来週は、簡単な再帰プログラムより再帰方程式を示したり、速度の見積りなどを、 例題を通して理解確認を中心にしよう。