计蒜客 - 汉诺塔

悠悠 2021-12-03 15:55 332阅读 0赞

问题:

![1516087-20190501155629805-481143157.png][]

思路:

汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的讲解: [「递归练习」汉诺塔][Link 1]，非常生动.

不过这道题单靠传统汉诺塔解法会超时，仔细思考发现，其实没有必要同时搜索hanoi(n - 1, A, C, B)和hanoi(n - 1, B, A, C).

只需调用一次hanoi(n - 1)就可通过计算确定一次操作的移动次数和消耗体力. 使用结构体记录状态. 代码如下:

1 #include <iostream>
     2 using namespace std;
     3 typedef long long ll;
     4 
     5 struct node {
     6     ll cost;
     7     ll step;
     8 };
     9 node hanoi(int n)
    10 {
    11     node np;
    12     if (n == 1) {
    13         np.step = 1;
    14         np.cost = 1;
    15     }
    16     else {
    17         node tmp = hanoi(n - 1);
    18         np.step = tmp.step * 2 + 1;
    19         np.cost = tmp.cost * 2 + n;
    20     }
    21     return np;
    22 }
    23 
    24 int main()
    25 {
    26     int n;
    27     cin >> n;
    28     node x = hanoi(n);
    29     cout << x.step << ' ' << x.cost << endl; 
    30     return 0;
    31 }

转载于:https://www.cnblogs.com/AntonLiu/p/10800033.html

[1516087-20190501155629805-481143157.png]: /images/20211203/d793679e54e0478ab3445008c1bcab47.png
[Link 1]: https://www.bilibili.com/video/av9830115

发表评论取消回复

表情：

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

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

相关阅读

相关汉诺塔

汉诺塔 1.目标 2.思路（算法） 3.实现 4.总结（如何理解这个算法）注意： 1.目标目标很明确就是将下图中A柱子上

淡淡的烟草味﹌/ 2022年11月02日 13:14/ 0 赞/ 66 阅读

相关汉诺塔

package com.someusefuldesign.demo; /假设有A B C三个柱子移动的顺序为： / public class

妖狐艹你老母/ 2022年08月13日 15:54/ 0 赞/ 233 阅读

相关汉诺塔

Problem Description 汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着

Dear 丶/ 2022年06月17日 05:28/ 0 赞/ 309 阅读

相关汉诺塔

汉诺塔 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Prob

约定不等于承诺〃/ 2022年06月11日 03:24/ 0 赞/ 260 阅读

相关汉诺塔

\include<stdio.h> void hanoi(int n,char A,char B,char C) \{ if(n==1) printf("Move s

逃离我推掉我的手/ 2022年06月10日 12:57/ 0 赞/ 308 阅读

相关汉诺塔

include <stdio.h> void hannuota(int n,char A,char B,char C){ if(1 == n){

川长思鸟来/ 2022年06月07日 13:06/ 0 赞/ 227 阅读

相关汉诺塔

汉诺塔 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem D

怼烎@/ 2022年05月29日 05:58/ 0 赞/ 270 阅读

相关汉诺塔

def move(n, a, b, c): if n == 1: \ 如果a只有1盘子 print(a, '-->', c); \ 直接把盘子从a移到c els

迷南。/ 2022年05月18日 22:25/ 0 赞/ 337 阅读

相关计蒜客 - 汉诺塔

问题: ![1516087-20190501155629805-481143157.png][] 思路: 汉诺塔问题非常经典，不懂推荐去看B站正月点灯笼老师的对于汉诺塔的

悠悠/ 2021年12月03日 15:55/ 0 赞/ 333 阅读

相关汉诺塔

// 有柱子 A,B,C // 将n个圆盘分成一个上盘，一个下盘，每次移动都是 / n=1的时

我不是女神ヾ/ 2021年07月24日 23:39/ 0 赞/ 490 阅读