AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 96. 奇怪的汉诺塔    原题链接    中等

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-19 10:20:06 ,  所有人可见 ,  阅读 5908


29


14

题目描述

汉诺塔问题,条件如下:

1、这里有A、B、C和D四座塔。

2、这里有n个圆盘,n的数量是恒定的。

3、每个圆盘的尺寸都不相同。

4、所有的圆盘在开始时都堆叠在塔A上,且圆盘尺寸从塔顶到塔底逐渐增大。

5、我们需要将所有的圆盘都从塔A转移到塔D上。

6、每次可以移动一个圆盘,当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时,可将圆盘移至这座塔上。

请你求出将所有圆盘从塔A移动到塔D,所需的最小移动次数是多少。
汉诺塔塔参考模型

输入格式
没有输入
输出格式
对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数,每个结果占一行。

输入样例:
没有输入
输出样例:
参考输出格式

正解 DP+递推

解题思路:首先,我们可以初步确定,这是一道递归/递推的题目。(因为是汉诺塔问题)

  1. 我们先考虑三个塔的汉诺塔问题,最优秀方案:必然是先挪走n-1个圆盘,然后再挪走圆盘N,
    因此可以得出递推方程也就是 d[i]=d[i-1]*2+1;
    之所以要乘以2,是因为第一次挪到第二个塔,然后还要挪移回到第三个塔,下面四个塔也是这样的
  2. 接着考虑四塔问题,我们可以这么思考,首先挪走j个塔,也就是有四个塔可以选择,然后再挪走剩下的n-j个塔,此时有三个塔可以选择,因此这就是我们的状态转移方程:f[i]=min(f[i],f[j]*2+d[n-j]);//i表示当前一共有几个塔,也就是上文所说的n
#include <bits/stdc++.h>
using namespace std;
int d[21],f[21],i,j;
int main()
{
    for (i=1;i<=12;i++)
        d[i]=2*d[i-1]+1;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for (i=1;i<=12;i++)
        for (j=0;j<i;j++)
            f[i]=min(f[i],f[j]+f[j]+d[i-j]);
    for (i=1;i<=12;i++)
        cout<<f[i]<<endl;
}

20 评论


用户头像
18537231688   2020-09-11 20:44      1    踩      回复

Orz


用户头像
小小蒟蒻   2020-07-08 20:51      1    踩      回复

嗯,递归求解也可以,每个塔就是一个栈。还是单调栈。扩展可以搞n塔m个盘子的玩法。不过5塔5盘的递归方式有点搞不明白了。。。


用户头像
哈哈哈hh   2020-06-24 22:23      1    踩      回复

orzz


用户头像
memset0   2020-01-30 17:25      1    踩      回复

QWQ


用户头像
听雨者   2019-12-16 18:33      1    踩      回复

解题思路中的第二条,不应该是首先移走j个圆盘吗,QAQ


用户头像
Frank2008_2   2019-10-05 17:25      1    踩      回复

666666666666666666666

用户头像
秦淮岸灯火阑珊   2019-10-05 19:17      1    踩      回复

QwQ


用户头像
ohha_chen   2024-05-14 21:19         踩      回复

QwQ


用户头像
一无是处小fw   2022-01-17 12:18         踩      回复

%%%


用户头像
cherryyh   2021-12-22 19:13         踩      回复

666膜拜大佬


用户头像
chiptune   2021-08-26 12:43         踩      回复

讲的不错


用户头像
cin   2021-04-08 17:19         踩      回复

妙啊,妙啊


用户头像
xnuohz   2020-10-15 14:33         踩      回复

%%%


用户头像
wickphy   2020-06-20 14:28         踩      回复

nb


用户头像
G_A_TS   2019-07-23 12:28         踩      回复

%%%%%%

用户头像
秦淮岸灯火阑珊   2019-10-05 19:17         踩      回复

QwQ


用户头像
zhangxu   2019-05-22 11:26         踩      回复

%%%%%%%%

用户头像
秦淮岸灯火阑珊   2019-10-05 19:17      1    踩      回复

QwQ


用户头像
晓玲   2019-05-03 10:58         踩      回复

赞!

用户头像
秦淮岸灯火阑珊   2019-05-03 13:03         踩      回复

%%%


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息