【数据结构与算法】之递归算法:汉诺塔问题

当一个问题规模较大且不易求解的时候,考虑将问题分成几个小额模块,逐一解决:折半查找法。

  • 汉诺塔问题:

三根针,X,Y,Z,X针从下到上穿好了由大到小的64片金片——汉诺塔。按照这个法则移动金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。最终将X上的塔移动到Z上

S1:将X上63个金片借助Z移动到Y上——>再细分步骤

S2:将X上第64个金片移动到Z上

S3:将Y上63个金片借助X移动到Z上——再细分步骤

#include <stdio.h>
//将n个盘子从x借助y移动到z上
void move(int n,char x,char y,char z){
 if(1 == n) {
  printf("%c-->%c\n",x,z );
 }else{
  move(n-1,x,z,y);	//将n-1个盘子从x借助z移动到y上
  printf("%c-->%c\n",x,z);	//将第n个盘子从x移动到z上
  move(n-1,y,x,z);	//将n-1个盘子从y借助x移动到z上
 }   
}
int int main(int argc, char const *argv[])
{
 int n;
 printf("请输入汉诺塔的层数");
 scanf("%d" ,&n);
 printf("移动步骤如下:\n");
 move(n,'x','y','z');
 return 0;
}

此条目发表在数据结构与算法分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注