双重河内塔I
2024-09-07 17:44:15
双重河内塔问题
又称:双重汉诺塔问题
这是《具体数学:计算机科学基础(第2版)》中的一道课后习题
这道题也是挺有意义的,我打算写三篇随笔来讲这个问题
双重河内塔包含 2n 个圆盘,它们有 n 种不同的尺寸,每一种尺寸的圆盘有两个。如通常那样,要求每次只能移动一个圆盘,且不能把较大的圆盘放在较小的圆盘上面。
a 如果相同尺寸的圆盘是相互不可区分的,要把一个双重塔从一根桩柱移动到另一根桩柱需要移动多少次?
b 如果在最后的排列中要把所有同样尺寸的圆盘恢复成原来的从上到下的次序,需要移动多少次?
提示:这是一个难题,实在应该是个“附加题”。
本文章针对a问题,后面两篇随笔针对b问题
经典汉诺塔问题如果理解了,a问题应该不难
经典汉诺塔有n个圆盘,我们设将所有圆盘从A塔-->C塔需要的步数为\(F_n\)
则\(F_1=1\)
又\(F_n = F_{n-1} +1+ F_{n-1}\)
易证\(F_n =2^n -1\)
我们设双重汉诺塔问题中2n个圆盘,完成所有移动的最终步数为\(A_n\)
易证\(A_n=2 \times F_n\)
得\(A_n=2^{n+1}-2\)
代码实现
#include<stdio.h>
int step;
void Move(int id,char from,char to){
printf("第%d步:将%d号型盘子%c-->%c\n",++step,id,from,to);
return ;
}
void Hanio(int n,char spos,char tpos,char epos){
if(n==1){
Move(n,spos,epos);
Move(n,spos,epos);
}
else {
Hanio(n-1,spos,epos,tpos);
Move(n,spos,epos);
Move(n,spos,epos);
Hanio(n-1,tpos,spos,epos);
}
}
int main(){
int n;
scanf("%d",&n);
Hanio(n,'A','B','C');
printf("最后总的步数为%d步\n",step);
}
最新文章
- 深入理解Java:内部类
- 频率直方图(hist)
- 【转】C++怎么读写windows剪贴板的内容?比如说自动把一个字符串复制.
- Netty中BIO,NIO
- ImageView的属性android:scaleType
- PHP单例模式编写
- webpack性能优化——DLL
- 一个div实现白眼效果
- ECO开放平台对接文档说明
- GridView item设置点击背景
- 微信小程序https配置
- 基于jQuery实现的Ajax 验证用户名唯一性
- python--selenium简单模拟百度搜索点击器
- keras环境
- 笔记--Wcf全面解析(上)---(1)
- log4j2介绍及配置
- java对象中的三种状态和脏检查及刷新缓存机制
- grep的若干用法
- json.dumps(i[&#39;bd_res&#39;], ensure_ascii=False)
- mybatis 学习二 conf xml 配置信息