12

jzoj 6797. 【2014广州市选day2】hanoi

 3 years ago
source link: http://www.cnblogs.com/Sport-river/p/13658285.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Description

你对经典的hanoi塔问题一定已经很熟悉了。有三根柱子，n个大小不一的圆盘，要求大盘不能压在小盘上，初始时n个圆盘都在第一根柱子上，最少要多少步才能挪到最后一根柱子上？

现在我们来将hanoi塔扩展一下，由三根柱子扩展到四根柱子，其余规则不变。例如，3个圆盘，四根柱子A到D，初始时圆盘都A柱上，我们用五步就可以将圆盘都挪到D柱上：

第一步：将圆盘1从A挪到B；

第二步：将圆盘2从A挪到C；

第三步：将圆盘3从A挪到D；

第四步：将圆盘2从C挪到D；

第五步：将圆盘1从B挪到D。

你的任务是写一个程序求解四柱子hanoi塔问题最少要多少步可以解决。

Input

输入只有一行，为一个正整数n。（1<=n<=1000）

Output

输出为一个正整数，代表n盘四柱子hanoi塔问题最少要多少步可以解决。

Solution

在做经典汉诺塔问题的时候，我们是用递推求出n个盘子时的步数的，我们做这道题的时候也就类比，尝试是否能够递推解决问题

以下是前10个数的表

盘子数 步数 1 1 2 3 3 5 4 9 5 13 6 17 7 25 8 33 9 41 10 49 ... ...

观察上面的表格，我们发现，从1个盘子到2个盘子与2个到3个各增加了2步即 \(2^{1}\) 步；从3个到4个、从4个到5个与从5个到6个各增加了4步即 \(2^{2}\) 步，以此类推，我们做出猜想

\[f_{i}=f_{i-1}+2^{k} \]

其中 \(k \in N^{*}\) 且是递增的

对于 \(2^{k}\) 会加（k+1）次

数据

\(n \leqslant 1000\)

所以直接递推就好

#include <cstdio>
#include <algorithm>
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int n,cnt,num,i;
long long add,f[1001];
int main()
{
    open("hanoi");
    scanf("%d",&n);
    f[1]=1;f[2]=3;f[3]=5;
    add=4;cnt=3;num=3;
    for (i=4;i<=n;i++)
    {
        f[i]=f[i-1]+add;
        cnt--;
        if (!cnt) cnt=++num,add*=2;
    }
    printf("%lld",f[n]);
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK