深圳logo设计公司推荐_在线代理的网站_网络上哪里可以做推广_中国大数据平台官网

简介

用 C++ 写了一个汉诺塔程序，它的特点是可以看出移动之后的效果，即可以查看移动之后目标塔中圆盘的顺序，是否和来源塔的圆盘顺序一致。
运行程序的效果图如下。这里用了 5 个圆盘示例，可以自行添加任意数量的圆盘：

---

程序逻辑

汉诺塔游戏的要求：

1. 把 n 个圆盘从 source 塔移到 dest 塔，可以借助 intermediate 作为过渡塔。
2. 最大的圆盘在最下面，越往上则圆盘越小。移动过程中必须始终保持这个规律。

汉诺塔程序用到了递归程序，大致的 3 个逻辑步骤是：

1. 把 source 上面的 n - 1 个盘子移到 intermediate 。
2. 把 source 最底下的盘子移到 dest 。
3. 把 intermediate 的 n - 1 个盘子移到 dest。

对汉诺塔的讲解，可参看清华大学郑莉教授的 C++ 课程： https://www.bilibili.com/video/BV1hv411g7Vu

---

源码

源码如下。其中用到 std::stack 数据结构，最符合汉诺塔的“后进先出”要求。

// 该程序展示汉诺塔 hanoi tower 游戏。
#include <iostream>
#include <stack>
#include <string>// 该函数用于把每个 tower 中的盘子展示出来。
void show_tower(std::stack<std::string> tower, std::string tower_name) {if (tower.empty()) {std::cout<< tower_name  << " is empty." << std::endl;} else {std::cout << "\nshowing: " << tower_name << std::endl;unsigned plates = tower.size();for (std::size_t i = 0; i < plates; ++i) {std::cout << "tower[" << i  << "]= " << tower.top() << std::endl;tower.pop();  // 删除顶部的盘子。}}
}// 把 source 最上面的盘子移到 dest 。
void move_one_plate(std::stack<std::string>& source, std::stack<std::string>& dest) {dest.emplace(source.top());  // emplace 比 push 更高效。source.pop();  // 删除 source 最顶部盘子的记录。
}// 汉诺塔程序把 n 个圆盘从 source 塔移到 dest 塔，可以借助 intermediate 作为过渡塔。
void hanoi(unsigned n, std::stack<std::string>& source, std::stack<std::string>& dest, std::stack<std::string>& intermediate) {  // 1. 设置递归程序的停止条件 baseline 。if (n == 1) {  // 只有一个盘子时，直接从 source 移到 destmove_one_plate(source, dest);} else {  // 2. 把 source 上面的 n - 1 个盘子移到 intermediate hanoi(n - 1, source, intermediate, dest);// 3. 把 source 最底下的盘子移到 dest move_one_plate(source, dest);// 4. 把 intermediate 的 n - 1 个盘子移到 dest。hanoi(n - 1, intermediate, dest, source);}
}int main() {std::stack<std::string> tower_source;  // 压入 5 个盘子进行示例。tower_source.emplace("plate_500");  // emplace 比 push 更高效。tower_source.emplace("plate_400");tower_source.emplace("plate_300");tower_source.emplace("plate_200");tower_source.emplace("plate_100");std::stack<std::string> tower_intermediate;std::stack<std::string> tower_dest;show_tower(tower_source, "tower_source");  show_tower(tower_intermediate, "tower_intermediate");  show_tower(tower_dest, "tower_dest");  hanoi(tower_source.size(), tower_source, tower_dest, tower_intermediate);std::cout << "\nafter hinoi function " << std::endl;show_tower(tower_source, "tower_source");  show_tower(tower_intermediate, "tower_intermediate");  show_tower(tower_dest, "tower_dest");  return 0;
}

---

—————————— 本文结束 ——————————