汉诺塔题目总结

参考了别人的代码的总结

1.四柱汉诺塔问题和n柱汉诺塔问题

题目:

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
double f[70];

void init() {
    f[1] = 1;
    f[2] = 3;

    for(int i = 3; i <= 65; i++) {
        double Max = f[i - 2] * 2 + 3;
        for(int j = 1; j < i; j++)
            Max = min(Max, 2 * f[i - j] + pow(2,j) - 1);
        f[i] = Max;
    }
}

int main() {
    init();
    int n;
    while(scanf("%d", &n) == 1) {
        printf("%d\n", (int)f[n]);
    }
    return 0;
}

2.计算某个盘子被移动的次数

题目:

#include<cstdio>
long long ans[65];
int main() {
    ans[1] = 1;
    for(int i = 2; i <= 60; i++)
        ans[i] = ans[i - 1] * 2;
    int test, x, y;
    scanf("%d", &test);
    while(test--) {
        scanf("%d%d", &x, &y);
        printf("%I64d\n", ans[x - y + 1]);
    }
    return 0;
}

3.无规则汉诺塔

题目:

#include<cstdio>

int main() {
    long long ans[31];
    int test, n;
    ans[1] = 3;
    for(int i = 2; i <= 30; i++)
        ans[i] = ans[i-1] * 3;
    scanf("%d", &test);
    while(test--) {
        scanf("%d", &n);
        printf("%I64d\n",ans[n]);
    }
    return 0;
}

4.状态查询

题目

#include<cstdio>
#include<cstring>
#define maxn 70
int num[3][maxn];
bool solve(int n, int *one, int *two, int *three) {
    if(two[0] == n)
        return 0;
    else if(one[0] == n)
        return solve(n - 1, one + 1, three, two);
    else if(three[0] == n)
        return solve(n - 1, two, one, three + 1);
    return 1;
}

int main() {
    int test, n;
    scanf("%d", &test);
    while(test--) {
        int n, m;
        scanf("%d", &n);
        for(int i = 0; i < 3; i++) {
            scanf("%d", &m);
            for(int j = 0; j < m; j++)
                scanf("%d", &num[i][j]);
            num[i][m] = -1;
        }
        printf("%s\n", solve(n,num[0],num[1],num[2]) ? "true" :"false");
    }
    return 0;
}

5.不规则移动

A.

题目:

#include<cstdio>

int main() {
    long long ans[40];
    int n;
    ans[1] = 2;
    for(int i = 2; i <= 35; i++)
        ans[i] = ans[i - 1] * 3 + 2;
    while(scanf("%d", &n) == 1) {
        printf("%I64d\n", ans[n]);
    }
    return 0;
}

B.

题目:

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 25

int main() {
    long long f[maxn], g[maxn], d[maxn], e[maxn];
    f[1] = 2;
    for(int i = 2; i <= 20; i++)
        f[i] = 3 * f[i - 1] + 2;

    d[1] = 1, d[2] = 4;
    for(int i = 3; i <= 20; i++)
        d[i] = f[i - 1] + f[i - 2] + 2 + d[i - 2];
    e[1] = 1, e[2] = 4;     

    for(int i = 3; i <= 20; i++)
        e[i] = e[i - 2] + 2 + f[i - 2] + f[i - 1];
    g[1] = 2, g[2] = 4, g[3] = 10;
    for(int i = 4; i <= 20; i++) {
        g[i] = 2 * f[i - 2] + 2 * f[i - 3] + 6 + d[i - 3] + e[i - 3];
        g[i] = min(g[i],f[i]);
    }
    int test, n;
    scanf("%d", &test);
    while(test--) {
        scanf("%d", &n);
        printf("%lld\n", g[n]);

    }
    return 0;
}
时间: 04-25

汉诺塔题目总结的相关文章

题目1458:汉诺塔III

题目描述: 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下.由小到大顺序串着由64个圆盘构成的塔.目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面.现在我们改变游戏的玩法,不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到下盘的上面.Daisy已经做过原来的汉诺塔问题和汉诺塔II,但碰到这个问题时,她想了很久都不能解决,现在请你帮助她.现在有N个圆盘,她至少多少

九度oj 题目1458:汉诺塔III

题目描述: 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下.由小到大顺序串着由64个圆盘构成的塔.目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面.现在我们改变游戏的玩法,不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到下盘的上面.Daisy已经做过原来的汉诺塔问题和汉诺塔II,但碰到这个问题时,她想了很久都不能解决,现在请你帮助她.现在有N个圆盘,她至少多少

题目1458:汉诺塔III(不一样的汉诺塔递归算法)

题目链接:http://ac.jobdu.com/problem.php?pid=1458 详解链接:https://github.com/zpfbuaa/JobduInCPlusPlus 参考代码: // // 1458 汉诺塔III.cpp // Jobdu // // Created by PengFei_Zheng on 23/04/2017. // Copyright © 2017 PengFei_Zheng. All rights reserved. // #include <std

3145 汉诺塔游戏——http://codevs.cn/problem/3145/

第一部分:题目 题目描述 Description 汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题.在A,B,C三根柱子上,有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔. 游戏中的每一步规则如下: 1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方) 2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子) 如对于n

hd 1207(四汉诺塔)

三个汉诺塔算法 f(n)=2^n-1 两个思路大同小异 Frame算法 在1941年,一位名叫J. S. Frame的人在<美国数学月刊>上提出了一种解决四柱汉诺塔问题的算法,这是人们熟知的Frame算法: (1)用4柱汉诺塔算法把A柱上部分的n- r个碟子通过C柱和D柱移到B柱上[F( n- r )步]. (2)用3柱汉诺塔经典算法把A柱上剩余的r个碟子通过C柱移到D柱上[2^r-1步]. (3)用4柱汉诺塔算法把B柱上的n-r个碟子通过A柱和C柱移到D柱上[F(n-r)步]. (4)依据上

nyoj89 汉诺塔(二)

题目网址 :http://acm.nyist.net/JudgeOnline/problem.php?pid=89 汉诺塔问题的经典结论: 把i个盘子从一个柱子整体移到另一个柱子最少需要步数是 2的i次方减一.那我们这个给定一个初始局面,求他到目标局面(全部移到第三个柱子上)需要的最少步数.怎么办呢!! 分析: 1.总的来说一定是先把最大的盘子移到第三个柱子上, 然后再把第二大的移到柱子3上, 然后再把第三大的盘子移到柱子3上.........直到把最小的盘子(1号盘子)移到柱子3上,才算结束.

CodeVs[3145 汉诺塔游戏]

题目描述 Description 题目描述 Description 汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题.在A,B,C三根柱子上,有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔. 游戏中的每一步规则如下: 1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方) 2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面,最大盘子下面不能有任何其他大小

汉诺塔递归解决方法经典分析

一位法国数学家曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针.印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔.不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面.僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔.庙宇和众生也都将同归于尽. 虽然这只是一个传说,但也给我们提出了一个问题,

HDU 2064 汉诺塔III(递归)

题目链接 Problem Description 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下.由小到大顺序串着由64个圆盘构成的塔.目的是将最左边杆上的盘全部移到右边的杆上,条件是一次只能移动一个盘,且不允许大盘放在小盘的上面.现在我们改变游戏的玩法,不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出),也不允许大盘放到下盘的上面.Daisy已经做过原来的汉诺塔问题和汉诺塔II,但碰到这个问题时,她想了很久都不能解决,现在