个人中心
文章发布
退出
作者热门文章
- Java锁的逻辑（结合对象头和ObjectMonitor）
- 还在用饼状图？来瞧瞧这些炫酷的百分比可视化新图形（附代码实现）⛵
- 自动注册实体类到EntityFrameworkCore上下文，并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
25
4
用递归方法编写的问题解决程序具有 结构清晰 ， 可读性强 等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决.
递归算法在 可计算性理论 中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易.
我们先从一个最简单的例子导入.
求 斐波那契数列 的第n位（C++代码）:
1
#include <bits/stdc++.h>
2
using
namespace
std;
3
4
int
fibonacci(
int
n) {
5
if
(n <=
1
) {
6
return
n;
7
}
else
{
8
return
fibonacci(n-
1
) + fibonacci(n-
2
);
9
}
10
}
11
12
int
main() {
13
int
n ;
14
cin >>
n ;
15
printf(
"
斐波那契数列前 %d 项为：\n
"
, n);
16
for
(
int
i =
1
; i <= n; i++
) {
17
printf(
"
%d
"
, fibonacci(i));
18
}
19
printf(
"
\n
"
);
20
return
0
;
21
}
回溯法的实现过程通常采用递归的方式，每次递归都会尝试一种可能的情况，如果这种情况不符合要求，就回溯到上一层递归，尝试其它的情况。在回溯的过程中，需要记录已经尝试过的情况，以避免重复计算.
回溯法的时间复杂度通常比较高，因为它需要搜索所有可能的情况。但是，在一些特殊的情况下，回溯法可以通过剪枝等优化技巧来提高效率.
1
#include <bits/stdc++.h>
2
3
#define
MAX_N 100
//
最大的问题规模
4
5
int
n;
//
问题规模
6
int
a[MAX_N];
//
存储解的数组
7
8
//
检查当前解是否合法
9
int
check(
int
cur) {
10
//
TODO: 根据具体问题实现
11
}
12
13
//
回溯函数
14
void
backtrack(
int
cur) {
15
if
(cur == n) {
//
找到一个解
16
//
TODO: 处理解的代码
17
return
;
18
}
19
for
(
int
i =
0
; i < n; i++) {
//
枚举当前位置的所有可能取值
20
a[cur] = i;
//
尝试将当前位置设为i
21
if
(check(cur)) {
//
如果当前解合法
22
backtrack(cur +
1
);
//
继续搜索下一个位置
23
}
24
}
25
}
26
27
int
main() {
28
//
TODO: 读入问题规模n和其它必要的输入
29
backtrack(
0
);
//
从第0个位置开始搜索
30
return
0
;
31
}
在实际使用中，需要根据具体问题实现check函数和处理解的代码.
下面是一个八皇后问题的回溯法实现:
1
#include <iostream>
2
using
namespace
std;
3
4
const
int
N =
8
;
5
int
queen[N];
//
存放每一行皇后所在的列号
6
7
bool
check(
int
row,
int
col)
//
判断当前位置是否可以放置皇后
8
{
9
for
(
int
i =
0
; i < row; i++
)
10
{
11
if
(queen[i] == col || abs(row - i) == abs(col -
queen[i]))
12
return
false
;
13
}
14
return
true
;
15
}
16
17
void
backtrack(
int
row)
//
回溯函数
18
{
19
if
(row == N)
//
找到一组解
20
{
21
for
(
int
i =
0
; i < N; i++
)
22
cout << queen[i] <<
"
"
;
23
cout <<
endl;
24
return
;
25
}
26
27
for
(
int
col =
0
; col < N; col++)
//
枚举当前行所有可能的列
28
{
29
if
(check(row, col))
//
如果当前位置可以放置皇后
30
{
31
queen[row] = col;
//
记录当前皇后所在的列号
32
backtrack(row +
1
);
//
继续搜索下一行
33
}
34
}
35
}
36
37
int
main()
38
{
39
backtrack(
0
);
40
return
0
;
41
}
在上面的代码中，check函数用于判断当前位置是否可以放置皇后，backtrack函数用于搜索所有可能的情况。在搜索过程中，queen数组用于记录每一行皇后所在的列号.
回溯法是一种非常实用的算法，它可以解决很多组合优化问题。但是，由于回溯法的时间复杂度较高，因此在实际应用中需要注意优化.
。
码字不易，点个赞呗§(*￣▽￣*)§ 。
如果您觉得阅读本文对您有帮助，请点一下“
推荐
”按钮，您的
“推荐”
将是我最大的写作动力！欢迎各位转载，但是未经作者本人同意，转载文章之后
必须在文章页面明显位置给出作者和原文连接
，否则保留追究法律责任的权利。
最后此篇关于递归与回溯法的文章就讲到这里了,如果你想了解更多关于递归与回溯法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
25
4
0
在我的类里面，我学习了 Prolog 回溯算法和 Rete forprop 算法，但我也被告知 Rete 可用于进行反向传播。 这是如何运作的？它在哪些方面与 Prolog 回溯相似/不同？ 例如，这
两个 friend P1 和 P2 向共同的 friend P3 发送相同的消息 M。 然而由于一些网络损坏，P3 一次只能接收一个字符不知道接收到的字符是属于 P1 还是 P2。 此外，P3 可能会
我最近发了几个理解递归和回溯的问题，我觉得我现在得到了一些东西，并尝试编写一个测试，我确实解决了数独问题，但是当我以另一种格式编写代码时，代码卡了一会儿，返回False，说明这个问题无解。 grid
有人可以指导我或解释如何在 LISP 中执行回溯吗？任何示例或链接将不胜感激。我确实尝试过谷歌，但是他们都没有足够简单的例子让我理解。 谢谢 最佳答案 典型的方法是将不可变状态向下传递到调用堆栈，辅助
我正在使用 apache 2.2.14 运行 Backtrack 5 R2 (ubuntu) 的完全库存安装。我尝试运行一个简单的 index.html 文件，其中包含一些 javascript 代码
如何在 Javascript 中获取回溯？ 理想的特征: 入口函数名称，或匿名函数的一些有意义的标识符， 每个级别的参数列表， 行号。 这可以用标准的 ECMAScript 完成吗？ 如果没有，是否可
本文首发公众号：小码A梦 回溯算法是一种常见的算法，常见用于解决排列组合、排列问题、搜索问题等算法，在一个搜索空间中寻找所有的可能的解。通过向分支不断尝试获取所有的解，然后找到合适的
Python 是否支持为每个异常/引发/断言显示相同的自定义错误消息(无论代码在哪里中断)？ 我目前对它的破解使用了一个装饰器。我有一个函数main它显示回溯很好，但我希望它也打印my_var (在函
输入: 3,4,8,7,3 5,S,7,2,3, 8,5,5,8,10 9,3,3,8,7 6,10,3,G,1 目标是找到从起点(S)到目标(G)的最佳路径。 我们可以向上、向下、向左、向右移动。
我想匹配一个包含“json”(出现超过 2 次)且两个“json”之间没有字符串“from”的字符串。 For example(what I want the string match or not)
我正在尝试使用回溯方法找到熄灯游戏的解决方案。我无法理解此过程的算法。我的方法是枚举从 0 到 2n2 - 1 的所有整数，并将每个整数转换为具有 n*n 位的二进制数。然后，将其分成n2个二进制数字
所以我正在阅读这本书《服从测试山羊》，在学习 Python 时我在第六章中遇到了一个问题。它说我应该能够运行我们在本章和前一章中设置的功能测试，没有错误；但是，我不断收到我不知道如何修复的回溯。 Tr
我需要一些关于 Android 日志文件反混淆的帮助。 问题是如果我有这样的异常: ... 10-16 10:03:10.488: E/AndroidRuntime(25723): Cau
我有一个看起来像这样的表: here | there | -------+-------+ {1,1} | {1,1} | {1,1} | {2,1} | {1,1} | {1,2} |
我写了一小段代码，它应该接受一个字符数组并让它看起来像计算机正在输入文本。很简单，对吧？但是当我运行它时，Terminal 告诉我: *** stack smashing detected ***:
Python 中的堆栈跟踪显示文件路径。有什么方法可以让它们显示完全限定的函数名称吗？ 例子: class Foo(object): def bar(self): raise
我决定深入学习回溯的概念，我有以下任务: 给定N个投资者，M个城市，N×M个投资者偏好矩阵P(P[i,j]=1，当第i个投资者希望在第j个城市建矿池；P[i, j] = 0 那么他是中立的，当 P[i
设 E - 图 G 中所有边的集合问题是从G中找到顶点的最小子集S，它满足条件:S = E 中每个顶点的所有出边的总和 换句话说:边是街道，我们可以在顶点上放置路灯。如果我们在一个顶点上放置一盏路灯—
我正在尝试做这个我在查找面试问题时遇到的问题。我们被问及将 r 个硬币放置在 n*m 网格上的方法数量，使得每行和每列至少包含一个硬币。 我想到了一个回溯解决方案，按行主要顺序处理网格中的每个单元格，
我使用 DexGuard混淆。我有来自崩溃日志和映射文件的堆栈跟踪。当我运行 retrace.bat 并为其提供堆栈跟踪和映射文件时，输出仍然是混淆格式。 最佳答案 您是否在使用 ProGuard 的
我是一名优秀的程序员,十分优秀！