汉诺塔C语言递归实现-创新互联
相信每一次学习C语言的同学都会遇到获诺塔问题,我学习C语言也已经有一段时间了,最近遇到了这个经典的问题,下面来总结一下!!
成都创新互联公司成立于2013年,我们提供高端网站建设公司、成都网站制作、成都网站设计、网站定制、成都全网营销推广、小程序制作、微信公众号开发、成都网站营销服务,提供专业营销思路、内容策划、视觉设计、程序开发来完成项目落地,为主动防护网企业提供源源不断的流量和订单咨询。盘子个数n | 步骤次数 |
1 | 1 |
2 | 3 |
3 | 7 |
4 | 15 |
...... | ...... |
64 | 2^64-1 |
...... | ...... |
n | 2^n-1 |
我们可以计算一下,如果要移动64个盘子,所需要的时间是多少?假设这个小和尚十分聪明,每秒钟移动一个盘子,所需时间:(2^64-1)/3600/24/365=584942417355.07203243911719939117
可以看出挪完64个盘子需要耗费5000多亿年,这显然是不现实的,所以我们仅讨论移盘子的步骤算法就可以。
分治:可以将n-1层移到中转位置上,然后将最下面的大的盘子移到目标位置上,再把n-1个盘子移到目标位置。
完整代码:
//汉诺塔
void move(char pos1, char pos2)
{
printf("%c->%c ", pos1, pos2);
}
// n代表盘子的个数
// POS1代表起始位置
// POS2代表中转位置
// POS3代表目的位置
void Hanoi(int n, char pos1, char pos2, char pos3)
{
if (n == 1)
move(pos1, pos3);
else
{
Hanoi(n-1, pos1, pos3, pos2);
move(pos1, pos3);
Hanoi(n-1, pos2, pos1, pos3);
}
}
int main()
{
int n = 0;
scanf("%d", &n);//盘子个数
Hanoi(n, 'A', 'B', 'C');//A柱 B柱 C柱
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页标题:汉诺塔C语言递归实现-创新互联
当前地址:http://scyanting.com/article/dgjjhg.html