HDU-1207 汉诺塔II
2024-10-18 21:22:37
汉诺塔 四根所需要的步数的规律:
规律:
a[1]=1;
a[2]=a[1]+2;a[3]=a[2]+2;(2个加2^1)
a[4]=a[3]+4;a[5]=a[4]+4;a[6]=a[5]+4;(3个加2^2);
…………………………………………(4个加2^3);
汉诺塔II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4548 Accepted Submission(s): 2241
Problem Description
经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩,当然这个传说并不可信,如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。
Gardon是个怕麻烦的人(恩,就是爱偷懒的人),很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难,所以Gardon决定作个小弊,他又找来了一根一模一样的柱子,通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是:当Gardon在一次游戏中使用了N个盘子时,他需要多少次移动才能把他们都移到第三个柱子上?很显然,在没有第四个柱子时,问题的解是2^N-1,但现在有了这个柱子的帮助,又该是多少呢?
Gardon是个怕麻烦的人(恩,就是爱偷懒的人),很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难,所以Gardon决定作个小弊,他又找来了一根一模一样的柱子,通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是:当Gardon在一次游戏中使用了N个盘子时,他需要多少次移动才能把他们都移到第三个柱子上?很显然,在没有第四个柱子时,问题的解是2^N-1,但现在有了这个柱子的帮助,又该是多少呢?
Input
包含多组数据,每个数据一行,是盘子的数目N(1<=N<=64)。
Output
对于每组数据,输出一个数,到达目标需要的最少的移动数。
Sample Input
1
3
12
Sample Output
1
5
81
#include<stdio.h>
#include<math.h>
int main()
{ int n,t,a[100],j,r,q,i;
a[1]=1;
t=0;
q=2;
r=1;
for(i=2;i<=64;i++)
{
if(t==q)
{
r++;
q++;
t=0;
}
a[i]=a[i-1]+pow(2,r);
t++;
}
while(~scanf("%d",&n))
{
printf("%d\n",a[n]);
} return 0;
} ///规律:
//a[1]=1;
//a[2]=a[1]+2;a[3]=a[2]+2;(2个加2^1)
//a[4]=a[3]+4;a[5]=a[4]+4;a[6]=a[5]+4;(3个加2^2);
//…………………………………………(4个加2^3);
最新文章
- 使用js脚本批量下载慕课网视频
- 写在分类之首-----to do list!
- SQL*Loader之CASE10
- C++基础(纯虚函数与抽象类)
- C#二进制文件的读写
- Hadoop运维操作
- [codevs5578][咸鱼]tarjan/结论题
- java递归方法
- 被FusionCharts V3.4抛弃的东西
- 笨方法学python--参数,解包,变量
- Spring的声明式事务管理
- .net core ef 通过dbfirst方式连接mysql数据库
- [SHOI2015]自动刷题机
- python3+selenium入门01-环境搭建
- unable to auto-detect email address
- SpringMVC+Swagger详细整合
- JQuery第一天——入门概述与选择器
- No configuration found for the specified action解决办法(转)
- unity5, custom PBS shader
- Spring_Spring与DAO_Spring的事务管理