算法--递归--汉诺塔问题
发布日期:2021-07-01 03:39:29
浏览次数:2
分类:技术文章
本文共 1675 字,大约阅读时间需要 5 分钟。
文章目录
1. 问题分析
游戏规则:一次只能挪一片;小的只能在大的上面;把所有的从A柱挪到C柱。 递推公式:- 上部 n - 1 个 A 到 B;
- 最底下 1 个 A 到 C ;
- 上部 n - 1 个 B 到 C;
终止条件:
n = 1 时,A 到 C;/** * @description: 汉诺塔递归问题 * @author: michael ming * @date: 2019/4/7 20:10 * @modified by: */#includeusing namespace std;void hanoi(size_t n, string startP, string middleP, string destP, size_t &counts){ if(n == 1) { cout << startP << " ---> " << destP << endl; counts++; return; } else { hanoi(n-1, startP, destP, middleP, counts); //n-1个从开始-->中间 cout << startP << " ---> " << destP << endl; //最底下那个开始-->目的地 counts++; hanoi(n-1, middleP, startP, destP, counts); //n-1个从中间-->目的地 }}int main(){ cout << "请输入汉诺塔层数:"; size_t n, steps = 0; cin >> n; hanoi(n,"a","b","c",steps); cout << "共走了 " << steps << " 步。" << endl; return 0;}
2. 面试题
《程序员面试金典》
- 题目
在经典汉诺塔问题中,有 3 根柱子及 N 个不同大小的穿孔圆盘,盘子可以滑入任意一根柱子。一开始,所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。请编写程序,用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1: 输入:A = [2, 1, 0], B = [], C = [] 输出:C = [2, 1, 0]示例2: 输入:A = [1, 0], B = [], C = [] 输出:C = [1, 0]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/hanota-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。- 解题
class Solution { public: void hanota(vector & A, vector & B, vector & C) { h(A,B,C,A.size()); } void h(vector & A, vector & B, vector & C, int n) { if(n == 1) { C.push_back(A.back()); A.pop_back(); return; } h(A,C,B,n-1); C.push_back(A.back()); A.pop_back(); h(B,A,C,n-1); }};
转载地址:https://michael.blog.csdn.net/article/details/89074972 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月23日 06时35分56秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Android--W/System.err: java.net.UnknownServiceException: CLEARTEXT communication to 10.114.35.103
2019-05-02
休息的艺术
2019-05-02
计算机科学经典文章
2019-05-02
Python 大全
2019-05-02
在python 解释器中学习linux系统函数调用
2019-05-02
[bash]: 删除代码注释
2019-05-02
Vmware虚拟机下三种网络模式配置
2019-05-02
今日整理PDF电子书资料
2019-05-02
在赛凡新的Warmup!
2019-05-02
Dtrace 资源库 URL 大全
2019-05-02
C问题集
2019-05-02
Bash 编程问题集
2019-05-02
怎么样学习代码
2019-05-02
URL: 技术图书清单
2019-05-02
没有sh -x , 写bash 就是 个笑话!
2019-05-02
【数据库-MySql】This function has none of ... in its declaration and binary logging is enabled
2019-05-02
【框架-MFC】CTreeCtrl(chenlu-2):创建二叉树
2019-05-02
【框架-MFC】CTreeCtrl(chenlu-3):双击事件和选择事件
2019-05-02