排序

散列

递归

汉诺塔

点击展开题目 汉诺塔

汉诺塔(又称河内塔)问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象成模型就是说：

有三根相邻的柱子，标号分别为$A$、$B$、$C$，$A$柱子按金字塔状叠放着$n$个不同大小的圆盘，现在要把所有盘子一个一个移动到柱子$C$上，并且任何时候同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，并给出具体的移动方案。

输入描述： 一个正整数$n$($1\le n\le 16$)，表示圆盘的个数。

输出描述： 第一行输出一个整数，表示至少需要的移动次数。

接下来每行输出一次移动，格式为X->Y，表示从柱子$X$移动最上方的圆盘到柱子$Y$最上方。

输入样本：

1

样本输出：

1
A->C

代码长度限制[待补充] KB | 时间限制[待补充] ms | 内存限制[待补充] MB | 栈限制[待补充] KB

思路 该问题运用递归思想求解。 将$n$个盘子从$A$柱移到$C$柱，可拆解为三个步骤： 先把上面$n - 1$个小盘从$A$移到$B$，这需要$S_{n - 1}$次； 接着把最底下最大的$1$个盘子从$A$移到$C$，需$1$次； 最后把$n - 1$个小盘从$B$移到$C$，又需$S_{n - 1}$次。 由此得到总步数公式$S_n = 2\cdot S_{n - 1}+1$，初始条件$S_1 = 1$，进而推出通项公式$S_n = 2^n - 1$。在具体移动过程中，大盘的移动操作必须夹在两次小盘搬运中间，以保证符合规则。

C++

#include <bits/stdc++.h>
using namespace std;
int n;
void f(int n, char from, char to, char mid)
{
    if(n == 0) return;
    else
    {
        f(n - 1, from, mid, to);
        printf("%c->%c\n", from, to);
        f(n - 1, mid, to, from);
    }
}

int main()
{
    cin >> n;
    cout << pow(2, n) - 1 << "\n";
    f(n, 'A', 'C', 'B');
    return 0;
}

Java

[待补充]

Python

[待补充]

贪心

二分

two pointers

其他高效技巧与算法

贡献者: Withnoidea

上一页入门模拟