C++ 递归策略
发布日期:2021-07-22 07:28:52 浏览次数:6 分类:技术文章

本文共 1597 字,大约阅读时间需要 5 分钟。

一、汉诺塔问题

1.问题描述

有a、b、c三个塔柱,8个圆盘在塔柱a上,大小随高度增加而减小,将8个圆盘从塔柱a移动到塔柱b,遵循以下规则:

  1. 每次只移动一个圆盘
  2. 不允许将大圆盘移动到小圆盘之上

2.问题框架

在用递归解决此问题时,递归程序应包含以下参数:

  1. 需要移动圆盘数量
  2. 开始的塔柱名字
  3. 最终所在的塔柱名字
  4. 临时储存圆盘的塔柱名字

据此得到如下函数原型:

void moveTower(int n, char start, char finish, char tmp);

3.递归策略

  1. 将最上面的N-1个圆盘从开始所在的塔柱移动到临时塔柱上
  2. 将最底下的一个圆盘从开始所在的塔柱移动到最终所在塔柱上
  3. 将N-1个圆盘从临时塔柱移回到最终所在塔柱上

4.编码方案

操作输出函数:

void moveSingleDisk(char start, char finish) {
cout << strat << "->" << finish << endl;}

具体实现函数:

void moveTower(int n, char start, char finish, char tmp) {
if (n == 1) {
moveSingleDisk(start, finish); } else {
moveTower(n - 1, start, tmp, finish); moveSingleDisk(start, finish); moveTower(n - 1, tmp, finish, start); }}

二、子集求和问题

1.问题描述

给定一个整数集合和一个目标值,确定是否可以找到这个整数集合的一个子集,子集的和等于指定的目标值

其判定函数如下:

bool subsetSumExists(set
& set, int target);

2.递归策略及实现

选择一个元素,然后将其从集合中删除,创建一个更小的集合。

bool subsetSumExists(set
& ji_he, int target) {
if (ji_he.empty()) {
return target == 0; } else {
int element = *ji_he.begin(); ji_he.erase(element); set
rest = ji_he; return subsetSumExists(rest, target) || subsetSumExists(rest, target - element); }}

这个递归策略包含两个分支,一种包含特定的元素,另一种不包含该特定元素,可以称其为包含/排除模式,在涉及数组和字符串的应用中应注意识别。

三、字符排列

对于一个给定的字符集合可以产生其所有的排列组合。

实现函数如下:

set
generatePermutations(string str) {
set
result; if (str == "") {
result.insert(""); } else {
for (int i = 0; i < str.length(); i++) {
char ch = str[i]; string rest = str.substr(0, i) + str.substr(i + 1); for (string s : generatePermutations(rest)) {
result.insert(ch + s); } } } return result;}

转载地址:https://blog.csdn.net/m0_45689014/article/details/113448390 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【转载】C++中list,vector,deque,map,set区别、联系和使用场景
下一篇:并查集

发表评论

最新留言

初次前来,多多关照!
[***.217.46.12]2024年03月11日 00时06分20秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

心电图计算心率公式_医学常用的计算公式口诀(内外妇儿),赶快收藏! 2019-04-21
select 移动端 第一个无法选中_Python爬虫微博(移动端)评论 2019-04-21
华为云welink成像是反的_华为发布智能办公神器WeLink,可连接会议室开会,还可一键遥控报销和智能翻译... 2019-04-21
唱好铁血丹心谐音正规_趙贤典:打好“感情牌” 唱好“大合唱” 2019-04-21
aix系统vi修改命令_Linux基础知识必备:利用vi编辑器创建和编辑正文文件 2019-04-21
天涯明月刀开发_玩家被天涯明月刀手游“冷落”?六大门派角色竟不带正眼看人... 2019-04-21
this指向undefined uiapp_一个this都没有,真好 2019-04-21
add p4 多个文件_2-3【微信小程序全栈开发课程】index页面完善--vue文件代码解析... 2019-04-21
5w2h原则指的是什么_什么是5W2H分析法?一首小诗带入进入大门。 2019-04-21
技校毕业是什么学历_中等职业学校是什么_中等职业学校毕业是什么学历 2019-04-21
2压缩备份数据库_MySQL数据备份与恢复(二) xtrabackup工具 2019-04-21
英特尔cpu发布时间表_被嘲讽的英特尔核显,强大能力其实超乎你的想象 2019-04-21
chi2inv函数 matlab_MATLAB概率和统计(2) 2019-04-21
lisp修改上一个图素_在Windows上安装Haskell 2019-04-21
ad19 导出step 没有pcb_几款主流PCB软件哪个最好用,你用过几款? 2019-04-21
json mysql 字段 默认值_Newtonsoft.Json 六个超简单又实用的特性,值得一试 【上篇】... 2019-04-21
ocdma相干非相干_《Acconeer 60GHz脉冲相干雷达芯片:A111》 2019-04-21
修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2019-04-21
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2019-04-21