ハノイの塔の処理回数の証明

前回授業のハノイの塔のルールの説明を受け、 実際にハノイの塔の処理回数の再帰方程式を示す。 そして実際にその証明ということで、数学的帰納法を用いて証明を行う。

処理速度のオーダの一般例として、 の事例として、クイックソートなどの例を示し、説明のしやすい マージソートについて、再帰方程式を示す。 次に代入法により、その式の一般解を示す。

メモリ利用の問題提起

例として、名前と電話番号のデータベースを作るというテーマとして、 これに必要とするデータ構造の宣言を示し、その問題点を示す。

#define DATA_SIZE 100
#define NAME_SIZE 10
#define TEL_SIZE 10
char name[ DATA_SIZE ][ NAME_SIZE ] ;
char tel[ DATA_SIZE ][ TEL_SIZE ] ;

しかし、DATA_SIZE は、１クラス50人ではなく、学年=200人、学校=1000人かもしれない。 TEL_SIZE は、12-3456 でなく、携帯電話 090-1234-5678 の16文字かもしれない。 "0033"をつけるかもしれない、"内線番号"がつくかもしれない、"国際電話で国別コード"がつくかもしれない。 NAME_SIZE も、漢字8文字=16byteかもしれない、 寿限無 みたいな名前だったら、漢字約100文字=200byte にするのか？ 最初から、こういうめったにない事例に応じて、*_SIZE を巨大にするのは、メモリの無駄。 かといって、

int x ;
char name[ x ] ; // C言語では、配列サイズは定数しか使えない

こういう点で、データサイズが任意というのは、いかにプログラムで扱いにくいのかを説明する。