読者です 読者をやめる 読者になる 読者になる

数学パズル「ハノイの塔」をC言語で攻略する!

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

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

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

ほらほら

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

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

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

出産祝いに

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

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

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

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

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

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

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

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

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

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

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

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

うーん。

1枚なら、AからB。

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

3枚なら‥‥?

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が1より大きいときとそうでないときで場合分けして考えていくところもポイント。

3枚の円盤のときを考えていくよ!

f:id:ruruganbaru:20161228112910j:plain

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

①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のn乗)-1}回で解けます。

がんばるぞっ!

ちなみに、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