小時候不知道你有沒有玩過這個遊戲，將途中的積木移至三根木釘中的其中一根上。規定在每次的移動中，只能搬移一片積木，並且在過程中必須保持金屬片由上至下是直徑由小至大的次序，也就是說不論在那一根木釘上，圓環形的積木都是直徑較小的被放在上層。
這是個很古老的遊戲，在二下時，趙老師有叫我們自己寫過，其實這個的程式不難寫，因為有一定的規律，我們來看看這是怎麼運作的。
這其實始有規律的，如果你細心觀察的話就可以找到問題的所在，下方是河內塔的程式碼，輸入有幾個積木之後，他會自己跑並寫出解法，大家可以試試看。
程式碼:
#include<stdio.h>
#include<stdlib.h>
void move(unsigned n,char left,char mid,char right);
int i=0;//判斷次數
int main()
{
int n,j,k;
again:
printf("請輸入塔高:");//設定塔高
scanf("%d",&n);
while(n>0)//只有>0的整數可以做搬移
{
printf("生成概況如下\n");
for(k=0;k<n;k++)
{
printf(" %d\n",k+1);
}
printf("剛開始位置: a b c\n\n");
printf("移動方法\n");
move(n,'l','r','m'); //開始計算搬移,abc為三根柱子
printf("\n共計:%d次完成\n",i);//判斷次數
printf("完成之後圖形如下\n");
for(k=0;k<n;k++)
{
printf(" %d\n",k+1);
}
system("pause");
}
printf("\n請輸入大於的整數\n\n");//當輸入的數字<=0時
goto again;
return 0;
}
void move(unsigned n,char left,char mid,char right)
{
if(n>0)
{
move(n-1,left,right,mid);//先從開始搬，在搬...依此類推，因為奇數偶數的搬法不同
i++;//步數
switch(left)//判斷最左邊為a,b,c ;另外只判斷左中或者左右兩個塔
{
case 'l'://如果最左邊則搬到b或c
switch(mid)
{
case 'm':
printf(" 第[%d]步: %2d----->%2d \n",i,n,n);//左往中搬移
break;
case 'r':
printf(" 第[%d]步: %2d------------->%2d \n",i,n,n);//左往右搬移
break;
}
break;
case 'm'://中間則搬到a或c
switch(mid)
{
case 'l':
printf(" 第[%d]步: %2d<-----%2d \n",i,n,n);//中往左搬移
break;
case 'r':
printf(" 第[%d]步: %2d----->%2d \n",i,n,n);//中往右搬移
break;
}
break;
case 'r'://右邊則搬到a或b
switch(mid)
{
case 'l':
printf(" 第[%d]步: %2d<-------------%2d \n",i,n,n);//右往左搬移
break;
case 'm':
printf(" 第[%d]步: %2d<-----%2d \n",i,n,n);//右往中搬移
break;
}
break;
}
move(n-1,right,mid,left);//在跳進去一次，主要用來將n減到小於，再從開始做接著...等
}
}
歡迎一起討論分享
沒有留言:
張貼留言
俗話說
凡走過必留下痕跡,凡住過必留下鄰居
凡爬過必留下樓梯,凡來過必留下IP
看過文章之後歡迎留下您寶貴的意見喔!