ハノイの塔は、数学パズル。

プログラミングがわからない方も、ちょっと見ていただけたらと思っています。

私もプログラミングは専攻じゃないんです！

ほらほら

数学パズル ハノイの塔 (木のおもちゃ 知育玩具) 1才?100才 出産祝い にお薦め♪ Wooden toys puzzle

- 出版社/メーカー: 木のおもちゃ製作所 銀河工房
- メディア: おもちゃ＆ホビー
- クリック: 10回
- この商品を含むブログ (1件) を見る

こんな感じのおもちゃなんだけど、

出産祝いに

とかなんとか書かれていますが。幼児がこれでどうやって遊ぶんだ？

# ハノイの塔のゲームルール

ハノイの塔は、**３本の棒**とたくさん(**n枚**)の円盤でできています。

上の写真で、３本の棒のうち、左から順に、**A, B, C**としましょう。
最初は、**Aにすべての円盤**があります。ちょうど上の写真のように**大きいものほど下**になるようにです。

**Aのすべての円盤を、大きいものほど下になるようにBにそのまま移し替える**というのが、ざっとしたゲームの流れとなりますが。
ここで、決まりがふたーつ！

1. ある円盤の上には、それより大きい円盤をのせてはならない。

2. 複数の円盤を同時に動かしてはならない。

この条件を満たすために、Cに仮置きして円盤を移動をさせていくわけです。

# n枚の円盤があるとき、どのような手順でゴールにたどりつけるでしょうか？

まずは、**人間**の頭を使って考えてみてください。

どうですか。わかりますか。

頭の中で、移動させることができない私は、絵をかいて頑張っております。

うーん。

１枚なら、AからB。

２枚なら、AからC。AからB。CからB

３枚なら‥‥？

# Cちゃんに解いてもらおう！

われわれ、人間はコンピュータの頭を使うことができます。

だけど、コンピュータに動いてもらうには、私たち人間がお願いしないとやってくれません！ けっこうこれも大変！

なんて頼めばいい？ C言語でプログラムを書いてみましょう！

#include<stdio.h> void hanoi(char a, char b, char c, int n){ if(n>1){ hanoi(a,c,b,n-1);/*①*/ hanoi(a,b,c,1);/*②*/ hanoi(c,b,a,n-1);/*③*/ }else{ printf("from %c to %c\n",a,b); } } int main(void){ int n; printf("How many discs?\nI have "); scanf("%d", &n); hanoi('A', 'B', 'C', n); return 0; }

なんで、そんなプログラムになるんだよ！

私もかなり時間かけて考えました。

これは、どうにもこうにもほかの説明聞いたりするより
**自分の手を動かしたほうが早いんじゃないかな？**

Amazonで、わざわざハノイの塔を買わないでも、テープとか積み重ねてさー！

それでも苦戦するね！！

このプログラムがわかりづらいのは、hanoi という関数の中にまたhanoiという関数があるからだと思います。

こんがらがらー

nが１より大きいときとそうでないときで場合分けして考えていくところもポイント。

３枚の円盤のときを考えていくよ！

絵でかくとこうなるね。プログラム中の①～と、絵の①～は同じものを指しています。

**①hanoi(A,C,B,2)**

hanoi(A,B,C,1) hanoi(A,C,B,1) hanoi(B,C,A,1)

n = 1 になったとき、動かす(else)から、A→B A→C B→C

n-1枚の円盤をCの仮置き場に持っていくのが①の役目。

**②hanoi(A,B,C,1)
**

n = 1 だから、そのままelseの処理へ。A→B

A→B

**③hanoi(C,B,A,2)**

hanoi(C,A,B,1) hanoi(C,B,A,1) hanoi(A,B,C,1)

同様に、すべて n = 1となっているわけだから、C→A C→B A→B

n-1枚のCに仮置きされていた円盤をBへと送るのが③ということ。

# 実行して確かめよう

How many discs?

I have 3

from A to B

from A to C

from B to C

from A to B

from C to A

from C to B

from A to B

予想と同じになってる！

ハノイの塔のゲームとかあるから、それをやってみるとプログラムが何をやっているのかが理解しやすくなると思います。

おっ！なるほどね！って瞬間がきます。

私は、頭を使うゲームみたいなのあんまり好きじゃないです。全然できない！

やってみたらわかるけど、n枚の円盤があるとき、｛（2のｎ乗）－１｝回で解けます。

がんばるぞっ！

ちなみに、10枚円盤があるとこんなことになるから、やめたほうがいいですね笑

How many discs? I have 10 from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from B to A from C to B from C to A from B to A from B to C from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B from C to A from B to A from B to C from A to C from B to A from C to B from C to A from B to A from C to B from A to C from A to B from C to B from A to C from B to A from B to C from A to C from A to B from C to B from C to A from B to A from C to B from A to C from A to B from C to B