【码蹄集】四柱河内塔

川长思鸟来 2023-10-03 19:28 35阅读 0赞

### 题目：四柱河内塔 ###

河内塔问题：  
有三个柱子，编号为1，2，3;在编号为1的柱子上有n个大小不同圆盘，圆盘从小到大，从上到下堆叠，你只可以移动—个柱子上最上面的圆盘。  
现在你需要将编号为1的柱子上的圆盘移到3柱子上，顺序不变;  
**注意:你在移动过程中，不可以将大的圆盘放在小圆盘上，你一次只可以移动一个盘子;**  
现在有一个4个柱子的河内塔，在规则不变的情况下，问最少需要移动多少次才能把盘子从1号柱子移到4号柱子上。

### 格式 ###

输入：一个整数f，表示n去(1, f)的f种情况（n <= 50）。  
输出： 输出f行，表示当n分别取(1, f)的情况下，需要的最少移动次数。

### 样例 ###

输入：12  
输出：

1
    3
    5
    9
    13
    17
    25
    33
    41
    49
    65
    81

### 代码 ###

#include<bits/stdc++.h>
    using namespace std;
    
    using namespace std;
    #define ll long long 
    #define N 10000
    const ll inf = 0x3f3f3f3f;
    ll d[6000], f[6000];
    int main()
    {
        
        ll n;
        cin >> n ;
        for (ll i = 1; i <= n; ++i)
            d[i] = 2 * d[i - 1] + 1;
        memset(f, inf, sizeof f);
        f[0] = 0;
        for (ll i = 1; i <= n; ++i)
            for (ll j = 0; j <= i; ++j)
                f[i] = min(f[i], 2 * f[j] + d[i - j]);
        for (ll i = 1; i <= n; ++i)
            cout << f[i] << endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关【码蹄集】四柱河内塔

题目：四柱河内塔河内塔问题：有三个柱子，编号为1，2，3;在编号为1的柱子上有n个大小不同圆盘，圆盘从小到大，从上到下堆叠，你只可以移动—个柱子上最上面的圆盘。

川长思鸟来/ 2023年10月03日 19:28/ 0 赞/ 36 阅读

相关【码蹄集】矩阵的对角线

题目：矩阵的对角线 ![在这里插入图片描述][568e0f29b6ec4561ae8df219ae4930a2.png] 格式 ![在这里插入图片描述][1e29

缺乏、安全感/ 2023年10月03日 19:28/ 0 赞/ 20 阅读

相关码蹄集迷宫2

一、题目：迷宫2 迷宫中有N堵圆形的墙。两个人被困在迷宫的不同位置。求他们如果要相见，至少要穿过多少堵墙。保证任意两个圆不相交，不重合，也不会相切，但有可能相互包含。人的

一时失言乱红尘/ 2023年10月03日 19:28/ 0 赞/ 49 阅读

相关码蹄集直线

一、题目如果用数学的观点来简化这个世界，将人生看做一条直线，那么世界上的一些人注定和我们平行或者异面。由这种人生哲理，我们可以考虑一下瓜大的同学—共可能有多少种交点数量

男娘i/ 2023年10月03日 19:27/ 0 赞/ 47 阅读

相关河内塔问题_河内Python程序塔（已修改）

河内塔问题 You are challenged for a challenge to find the number of moves required to move a

左手的ㄟ右手/ 2023年03月05日 12:41/ 0 赞/ 8 阅读

相关【C】C语言之经典算法：河内之塔(1)

文章目录前言一、背景二、思路解析三、流程图解析四、代码附上五、结果

末蓝、/ 2022年04月08日 12:16/ 0 赞/ 196 阅读

相关 JAVA - 四柱汉诺塔最优移动次序展示

本文是初学JAVA的自己做的一个小程序，关于面向对象的思想掌握的还不是很好，还没完全从c++过渡过来，尽情各位看官大佬批评指正。（中间汉诺塔的英文单词写错了//尴尬?）各个

深藏阁楼爱情的钟/ 2022年03月25日 01:50/ 0 赞/ 142 阅读

相关 C语言经典算法 - 三色河内塔的代码

如下的内容内容是关于C语言经典算法 - 三色河内塔的内容。 include <stdio.h> void hanoi(int disks, char sour

超、凢脫俗/ 2022年01月17日 13:25/ 0 赞/ 197 阅读

相关河内塔问题（C++版）

> 上次，我们讲了汉诺塔，今天我们来讲一讲和汉诺塔类似的题目《河内塔问题》题目描述 Description 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒

r囧r小猫/ 2021年12月21日 04:45/ 0 赞/ 238 阅读

相关算法训练——c语言经典算法大全-河内之塔(一)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

淡淡的烟草味﹌/ 2021年07月25日 14:41/ 0 赞/ 388 阅读