大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
汉罗塔的一般解法
一般来说,汉罗塔大多数人都是玩过了的。并且有一个很容易得到的规律,那就是先要将前(n – 1)项移动到过渡桩上面去,然后将最后一盘放在最终放的位置,然后再将(n – 1) 个盘子移动到最终位子。那么就完成了汉罗塔。
不管是多少个盘子,只要他的柱子只有三个,那么解法都是这个模式,所以很容易得到递归求解,如果是求总的移动次数,那么递归写法应该是如下:
#include <stdio.h>
int f(int n) // n是盘子数
{
if(1 == n)
{
return 1; //很容易得到 一个盘子当然只需要移动一次就得到结果
}
else
{
return f(n - 1)*2 + 1; // 简化版
//return f(n - 1) + 1 + f(n - 1);
// 这上面的式子的意思正如我上面所说 ,先将前n - 1 个盘子移动到过渡桩上面去,然后移动最后一个盘子,再移动前 n - 1 个盘子
// 所以是 f(n - 1) 的移动次数 加上最后一个盘子移动的一次 再加上f(n - 1)个盘子移动的次数 得到总次数
}
}
int main()
{
int n;
scanf("%d",&n); //盘子数
printf("%d个盘子总共移动次数为: %d",n,f(n));
return 0;
}
以上就是求解n个盘子需要移动的次数
而有时侯有的题目会考每次移动的盘子的步骤打印出来,那么就需要将上面的递归改变一下就可以得到每步的怎么移动的了
如下:
PS: 我就直接写递归函数了
void f(int n, char begin,char end,char through)
{
if(1 == n)
{
printf("%c -> %c\n",begin,end);
}
else
{
f(n - 1,begin,through,end); //移动前n - 1 个盘子到过渡盘
printf("%c -> %c\n",begin,end); // 将最后一个盘移动到最终柱子
f(n - 1,through,end,begin); // 将 n - 1 个盘子移动到最终柱子
}
}
如上就是每步盘子是如何移动的递归程序,只要明白了基本的移动方式,那么写出汉罗塔递归程序还是很好写的。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182680.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...