加强版汉诺塔算法问题


如果一共有4根柱子,而不是3根,那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?怕数字太大, 给出这个结果%1000的值即可。
输入:
n个盘子
输出:
移动多少次%1000结果即可。

c 算法

妹子萌一个 12 years ago

原理其实是一样的,也没有比3根柱子的复杂多少,由于多了一根柱子可用,移动的步骤反而少了,下面的代码可以把具体步骤打出来:

   
  #include <stdio.h>
  
int num = 0;
void move(char x,char y){
num++;
printf("%c-->%c\n",x,y);
}

void hanoi(int n,char one,char two,char three,char four){
if(n==1){
move(one,four);
}
else if(n==2){
move(one,two);
move(one,four);
move(two,four);
}
else{
hanoi(n-2,one,three,four,two);//将n-2个盘从第一根柱子移到第二根柱子
move(one,three);
move(one,four);
move(three,four);
hanoi(n-2,two,one,three,four);//将n-2个盘从第二根柱子移到第四根柱子
}
}

main(){
int n=0;
printf("input the number of diskes:");
scanf("%d",&n;);
printf("The step to moving %3d diskes:\n",n);
hanoi(n,'A','B','C','D');
printf("total step %d:\n",num);
}

推算了半天。

495年D波纹 answered 12 years ago

Your Answer