ハノイの塔
★自分が理解している事
「(n-1)ハノイが解けると仮定するとnハノイも解けること」
は理解できます。
そして数学的帰納法によりすべての自然数についてハノイは「解ける」
ここまではわかります。
★わからないのは、その「解き方」です。
「解ける」ことはわかるのですが「解き方」がわからないのです。
何故このプログラムで正解が表示されるのかが理解できないのです。
確かに、紙と鉛筆でプログラムの流れを追っていくと解けています。
しかし、何でこのプログラムで解けるのかがわからないのです。
棒ｘは出発点
棒ｙは目的地
棒ｚは作業棒
です。
(n-1)ハノイをひとかたまりと考え、作業棒Zに移す。
nハノイを目的地Yに移す。
(n-1)ハノイをひとかたまりと考え、目的地Yに移す。
そんな説明で確かに納得した気になりはします。
しかしこのプログラムでは(n-2)以下の場合についてはいっさい語っていません。
何かだまされてる気がします。
このプログラムでは(n-1)について語っていますが
(n-2)以下については全く語っていません。
数学的帰納法により「解ける」ことは証明済みですが、
「その解き方」がこのプログラムでよいという「証明」はありますでしょうか？
理解のコツはありますでしょうか？
よろしくお願いいたします。
#include<stdio.h>
#include<stdlib.h>
void hanoi(int n, char x, char y, char z)
{
if(n==0)
{/* 何もしない */}
else
{
hanoi(n-1,x,z,y);
printf("%c->%c,",x,y);
hanoi(n-1,z,y,x);
}
}
int main(void)
{
int num;
scanf("%d",&num);
hanoi(num,'A','B','C');
return 0;
}
