アルゴリズムとデータ構造 補足資料9-1 「ハノイの塔」 横浜国立大学 理工学部 数物・電子情報系学科 富井尚志 ハノイの塔 ハノイの塔 • 条件1:一度に一枚の円盤だけが移動できる。 • 条件2:どの円盤もその円盤より小さい円盤 の上においてはいけない。 • 条件3:棒Cを補助的な場所として良い。 ハノイの塔:実際にやってみよう (準備) • A4の紙を配ります。 (裏紙:再利用紙です。裏側の白い面を使いま す。) • まず、半分に切ってください。 – できた2枚のうち、一枚をまた半分に切ってください。 • できた2枚のうち、一枚をまた半分に切ってください。 – できた2枚のうち、一枚をまた半分に切ってください。 » できた2枚のうち、一枚をまた半分に切ってください。 » 5回くらいでいいです。。。 » これも再帰的。。。 ハノイの塔:実際にやってみよう (準備) 半分に切 る ハノイの塔:実際にやってみよう (準備) ハノイの塔:実際にやってみよう (準備) ● ● × 5 ● × ● 4 ● × ● 3 × ● × × 2 ● × ・ ・ 1 × ・ ・ 番号をかいて、 四隅にしるしをつけよう。 (奇数のカードの四隅には●、偶数のカードの四隅には×) これは使いません。→ ハノイの塔:実際にやってみよう (準備) ● ● 5 × × 4 ●● ● × ● 3× × ● ● × 2・ × ・ × 1 ・ ・ 順番に重ねる。 ハノイの塔:実際にやってみよう (準備) ● × ● × ● ×・ ● × ・ ・ × ● ・ × ● 5 312 4 × ● × ● 順番に重ねる。 (四隅のしるしが見えるように) ハノイの塔:実際にやってみよう (準備) ● × ● × ● ×・ ● × ・ ・ × ● ・ × ● 5 312 4 × ● × ● 棒(領域)A 円盤→カード 棒→領域 棒(領域)B 棒(領域)C ハノイの塔:実際にやってみよう (準備) スタート ● × ● × ● ×・ ● × ・ ・ × ● ・ × ● 5 312 4 × ● × ● 棒(領域)A 棒(領域)B 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (準備) ● × ゴール ● × ● ×・ ● ・× ・ × ● ・ × ● 5 312 4 × ● 棒(領域)A × ● 棒(領域)B 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (まずは2枚から) × × 2・ × ・ × 1 ・ ・ 棒(領域)A 棒(領域)B 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (まずは2枚から) スタート × ・ ・ × × ・ 1 2 ・ × 棒(領域)A 棒(領域)B 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (まずは2枚から) AからCへ 移動 × × ・ 2 2をBに移動させ るにまず、 その上の1を Cに移動させる × ・ 1 × 棒(領域)A ・ 棒(領域)B ・ 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (まずは2枚から) AからBへ 移動 × × ・ 2 一番下の2を Bに移動させた × 棒(領域)A ・ 1 × 棒(領域)B ・ ・ 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (まずは2枚から) CからAへ 移動 × ・ ・ × Cに退避して いた1を Bに移動させた ゴール! 棒(領域)A × ・ 1 2 ・ × 棒(領域)B 棒(領域)C •一度に、一番上の1枚だけ移動できる •どのカードも、そのカードより小さいカードの 上においてはいけない •領域Cを補助的な場所として使用してよい 最終的に、カードの束を、領域Aから領域Bに移動させる ハノイの塔:実際にやってみよう (つぎは3枚) ● ● 3 × ● × 2 ● × ・ × ・ ・ ・ 1 棒(領域)A 棒(領域)B 棒(領域)C 実際にやってみよう ハノイの塔:実際にやってみよう × × 4 ● × ● 3× × ● × 2・ ● × ・ × 1 ・ 棒(領域)A ・ 棒(領域)B 棒(領域)C 実際にやってみよう ゴールがBかCかは あまり気にせず、4枚、5枚、、、 ハノイの塔:解き方 × × 4 ● × ● 3× × ● × 2・ ● × ・ × 1 ・ 棒(領域)A ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには ハノイの塔:解き方 × × 4 ● × ● 3× × ● × 2・ ● × ・ × 1 ・ 棒(領域)A ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには、 まずその上の紫を ハノイの塔:解き方 × × ● 4 × ● 3 × ● × × 2・ ● × 1 ・ 棒(領域)A 棒(領域)B ・ × ・ 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して ハノイの塔:解き方 × × ● 4 × ● 3 × × ● × 2・ ● × 1 ・ 棒(領域)A 棒(領域)B ・ × ・ 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし ハノイの塔:解き方 × × 4 ● × ● 3× × ● × 2・ ● × 1 ・ 棒(領域)A ・ × ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して 一番下をBに動かし Cに退避した部分をBに「移動」 ハノイの塔:プログラム × × 4 ● × ● 3× × ● × 2・ ● × ・ × 1 ・ 棒(領域)A ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには hanoi( 4, “棒A”, “棒B”, “棒C”) ハノイの塔:プログラム × × 4 ● × ● 3× × ● × 2・ ● × ・ × 1 ・ 棒(領域)A ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには、 まずその上の紫を hanoi( 3, “棒A”, “棒C”, “棒B”) ハノイの塔:プログラム × × ● 4 × ● 3 × ● × × 2・ ● × 1 ・ 棒(領域)A 棒(領域)B ・ × ・ 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して hanoi( 3, “棒A”, “棒C”, “棒B”); ハノイの塔:プログラム × × ● 4 × ● 3 × × ● × 2・ ● × 1 ・ 棒(領域)A 棒(領域)B ・ × ・ 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して hanoi( 3, “棒A”, “棒C”, “棒B”); 一番下をBに動かし move(“棒A”, “棒B”); ハノイの塔:プログラム × × 4 ● × ● 3× × ● × 2・ ● × 1 ・ 棒(領域)A ・ × ・ 棒(領域)B 棒(領域)C この水色の山をBに動かすには、 まずその上の紫をCに「移動」して hanoi( 3, “棒A”, “棒C”, “棒B”); 一番下をBに動かし move(“棒A”, “棒B”); Cに退避した部分をBに「移動」 ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } おっと、その前に ゴミは必ず、各自持ち帰ってください。 ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:プログラム void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } ndisk-1枚 ndisk枚 src : “棒A” dst: “棒B” work: “棒C” ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(3, “棒A”, “棒B”, “棒C”) ゴールのイメージ 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(2, “棒A”, “棒C”, “棒B”) ゴールのイメージ 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(2, “棒A”, “棒C”, “棒B”) ゴールのイメージ 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ 棒A 棒B 棒C src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ src から dst 棒C へ work を使って 棒B 移動 hanoi(1, “棒A”, “棒B”, “棒C”) src 棒B 棒A if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒A 2 枚の円盤を hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src 棒A 棒B 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 move(“棒A”, “棒B”) src から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 棒B 棒A hanoi(1, “棒A”, “棒B”, “棒C”) 「棒Aから棒Bへ移動」 棒A 2 枚の円盤を hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src 棒A 棒B 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); 棒C hanoi(ndisk-1, work, dst, src); hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 } 何もしないで戻る ハノイの塔:実行の様子 ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(3, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src 棒A 棒B 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } move(“棒A”, “棒C”) 「棒Aから棒Cへ移動」 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 hanoi(1, “棒B”, “棒C”, “棒A”) ゴールのイメージ 棒A 棒B 棒C src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 hanoi(1, “棒B”, “棒C”, “棒A”) ゴールのイメージ src から dst 棒C へ work を使って 棒B 移動 hanoi(1, “棒B”, “棒C”, “棒A”) src 棒B 棒A if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒A 2 枚の円盤を hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒B から dst 棒C へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒B”, “棒C”, “棒A”) ndisk src hanoi(0, “棒B”, “棒A”, “棒C”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C 1 枚の円盤を 棒B から dst 棒C へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 move(“棒B”, “棒C”) src から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 棒B 棒A hanoi(1, “棒B”, “棒C”, “棒A”) 「棒Bから棒Cへ移動」 棒A 2 枚の円盤を hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒B から dst 棒C へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒B”, “棒C”, “棒A”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒B”, “棒C”, “棒A”) ndisk src 棒A 棒B 1 枚の円盤を 棒B から dst 棒C へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); 棒C hanoi(ndisk-1, work, dst, src); hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 } 何もしないで戻る ハノイの塔:実行の様子 ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒B”, “棒C”, “棒A”) hanoi(3, “棒A”, “棒B”, “棒C”) hanoi(1, “棒B”, “棒C”, “棒A”) ndisk src 棒A 棒B 棒C 1 枚の円盤を 棒B から dst 棒C へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒A”, “棒C”, “棒B”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒A から dst 棒C へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } move(“棒A”, “棒B”) 「棒Aから棒Bへ移動」 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(2, “棒C”, “棒B”, “棒A”) ゴールのイメージ 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(2, “棒C”, “棒B”, “棒A”) ゴールのイメージ 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 hanoi(1, “棒C”, “棒A”, “棒B”) ゴールのイメージ 棒A 棒B 棒C src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 hanoi(1, “棒C”, “棒A”, “棒B”) ゴールのイメージ src から dst 棒B へ work を使って 棒A 移動 hanoi(1, “棒C”, “棒A”, “棒B”) src 棒B 棒C if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒A 2 枚の円盤を hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒C から dst 棒A へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒C”, “棒A”, “棒B”) ndisk src hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C 1 枚の円盤を 棒C から dst 棒A へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 move(“棒C”, “棒A”) src から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 棒B 棒C hanoi(1, “棒C”, “棒A”, “棒B”) 「棒Cから棒Aへ移動」 棒A 2 枚の円盤を hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒C から dst 棒A へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒C”, “棒A”, “棒B”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒C”, “棒A”, “棒B”) ndisk src 棒A 棒B 1 枚の円盤を 棒C から dst 棒A へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); 棒C hanoi(ndisk-1, work, dst, src); hanoi(0, “棒B”, “棒A”, “棒C”) 円盤数が0なので、 } 何もしないで戻る ハノイの塔:実行の様子 ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒C”, “棒A”, “棒B”) hanoi(3, “棒A”, “棒B”, “棒C”) hanoi(1, “棒C”, “棒A”, “棒B”) ndisk src 棒A 棒B 棒C 1 枚の円盤を 棒C から dst 棒A へ work を使って 棒B 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } move(“棒C”, “棒B”) 「棒Cから棒Bへ移動」 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ 棒A 棒B 棒C src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 hanoi(1, “棒A”, “棒B”, “棒C”) ゴールのイメージ src から dst 棒B へ work を使って 棒A 移動 hanoi(1, “棒A”, “棒B”, “棒C”) src 棒B 棒C if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒A 2 枚の円盤を hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src hanoi(0, “棒A”, “棒C”, “棒B”) 円盤数が0なので、 何もしないで戻る 棒A 棒B 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 move(“棒A”, “棒B”) src から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 棒B 棒C hanoi(1, “棒A”, “棒B”, “棒C”) 「棒Aから棒Bへ移動」 棒A 2 枚の円盤を hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src 棒A 棒B 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); 棒C hanoi(ndisk-1, work, dst, src); hanoi(0, “棒C”, “棒B”, “棒A”) 円盤数が0なので、 } 何もしないで戻る ハノイの塔:実行の様子 ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } hanoi(1, “棒A”, “棒B”, “棒C”) hanoi(3, “棒A”, “棒B”, “棒C”) hanoi(1, “棒A”, “棒B”, “棒C”) ndisk src 棒A 棒B 棒C 1 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work hanoi(2, “棒C”, “棒B”, “棒A”) を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ndisk src 2 枚の円盤を 棒C から dst 棒B へ work を使って 棒A 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 棒A 棒B 棒C ハノイの塔:実行の様子 hanoi(3, “棒A”, “棒B”, “棒C”) ndisk src 3 枚の円盤を 棒A から dst 棒B へ work を使って 棒C 移動 if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } 完了:呼び出し元(main関数)に戻る 棒A 棒B 棒C ハノイの塔:移動回数 void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); move(src, dst); hanoi(ndisk-1, work, dst, src); } } hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く ハノイの塔:移動回数 void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); mn-1回の移動 move(src, dst); 1回の移動 hanoi(ndisk-1, work, dst, src ); mn-1回の移動 } } hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く ハノイの塔:移動回数 void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); mn-1回の移動 move(src, dst); 1回の移動 hanoi(ndisk-1, work, dst, src ); mn-1回の移動 } } hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く、と、 mn = 2 x mn-1 +1 ハノイの塔:移動回数 void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); mn-1回の移動 move(src, dst); 1回の移動 hanoi(ndisk-1, work, dst, src ); mn-1回の移動 } } hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く、と、 mn = 2n-1 ハノイの塔:移動回数 O(2n) void hanoi(int ndisk, char *src, char *dst, char *work) { if(ndisk>=1){ hanoi(ndisk-1, src, work, dst); mn-1回の移動 move(src, dst); 1回の移動 hanoi(ndisk-1, work, dst, src ); mn-1回の移動 } } hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く、と、 mn = 2n-1 ハノイの塔:移動回数 O(2n) n 2n-1 2 3 3 7 4 15 8 255 16 65,535 32 4,294,967,295 64 およそ1019 100 およそ1030 1,000 およそ10300 hanoi(n, , , )の移動回数(n枚の円盤全体を移動さ せるのに必要な移動回数):mnと置く、と、 mn = 2n-1 ハノイの塔:移動回数 O(2n) n 2n-1 2 3 x 10-10秒: 0.3ナノ秒 3 7 x 10-10秒: 0.7ナノ秒 4 15 x 10-10秒: 1.5ナノ秒 8 255 x 10-10秒: 26ナノ秒 16 65,535 x 10-10秒: 6.6マイクロ秒 32 4,294,967,295 x 10-10秒: 0.4秒 64 およそ109秒:およそ57年 100 およそ1020秒:およそ1兆年:宇宙の歴史100回分 1,000 およそ10290秒:およそ10282年:宇宙の歴史10272回分 円盤を目にもとまらぬ早業(1秒間に100億回) で移動させたら… mn = 2n-1
© Copyright 2024 ExpyDoc