HDUOJ--汉诺塔II

汉诺塔II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3675    Accepted Submission(s): 1830

Problem Description

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩,当然这个传说并不可信,如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。    Gardon是个怕麻烦的人(恩,就是爱偷懒的人),很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难,所以Gardon决定作个小弊,他又找来了一根一模一样的柱子,通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是:当Gardon在一次游戏中使用了N个盘子时,他需要多少次移动才能把他们都移到第三个柱子上?很显然,在没有第四个柱子时,问题的解是2^N-1,但现在有了这个柱子的帮助,又该是多少呢?

Input

包含多组数据,每个数据一行,是盘子的数目N(1<=N<=64)。

Output

对于每组数据,输出一个数,到达目标需要的最少的移动数。

Sample Input

1

3

12

Sample Output

1

5

81

Author

Gardon

Source

Gardon-DYGG Contest 2

Recommend
JGShining
/
*#include<stdio.h>
#include<math.h>
int main()
{
    long a[65];
    a[1]=1;
long i,j,n,m,r;
    for(i=2,j=1,r=1,m=2;i<66;i++,j++)
        if(j<=m)
            a[i]=a[i-1]+pow(2,r);
        else
{
            m++;
            j=1;
            r++;
            a[i]=a[i-1]+pow(2,r);
        }
    while(scanf("%d",&n)==1){
        printf("%d\n",a[n]);
    }
return 0;
}*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=64;
int arr[maxn];
void func();
int main()
{
int n;
func();
   while(cin>>n)
  cout<<arr[n-1]<<endl;
     return 0;
}
void func()
{
int i,j,k,m;
    memset(arr,0,sizeof(arr));
     k=*arr=1;
       m=2;
    for(i=1,j=0;i<maxn;i++,j++)
arr[j>=m?m++,j=0,k++:NULL,i]=arr[i-1]+(1<<k);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ---(1995)汉诺塔V

汉诺塔V Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

2768
来自专栏ml

HDUOJ----2512一卡通大冒险

一卡通大冒险 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

3519
来自专栏菩提树下的杨过

Flash/Flex学习笔记(39):弹性运动

动画中的弹性运动 从视觉效果上接近 物理经典力学中的单摆运动或弹簧(胡克定律F=Kx)振动 先看下面的模拟演示: 规律: 小球先从出发点(初始为最左侧)向目标点...

2045
来自专栏WOLFRAM

错觉艺术的巅峰,错觉图形大师M.C. Escher的不可能方块的可能模型

1833
来自专栏CreateAMind

carla无人驾驶模拟中文项目 carla_simulator_Chinese

https://github.com/xfqbuaa/carla_simulator_Chinese

1273
来自专栏CreateAMind

carla无人驾驶模拟中文项目 carla_simulator_Chinese

2031
来自专栏ml

HDUOJ----(2064)汉诺塔III

汉诺塔III Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

2838
来自专栏ml

hdu----(1847)Good Luck in CET-4 Everybody!(简单巴什博奕)

Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others)    Memory L...

2544
来自专栏小樱的经验随笔

BZOJ 1008 越狱

1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MB Submit: 8681  Solved:...

3517
来自专栏GIS讲堂

Arcgis for Js实现graphiclayer的空间查询

本节讲的是Arcgis for Js的针对graphiclayer的空间查询,内容很简单,代码如下:

2682

扫码关注云+社区

领取腾讯云代金券