黑马程序员技术交流社区
标题:
求教递归与回溯
[打印本页]
作者:
黄林
时间:
2013-2-7 14:21
标题:
求教递归与回溯
一直没弄懂递归与回溯算法，求高手祥细讲一下，最好有示例代码，谢谢
作者:
张庚
时间:
2013-2-7 15:49
这里给一个例子，
在n个数字中，任意找k个数字（k<=n)，打印所有的可能的情况
例如0, 1, 2
在这3 个数中，找2个数字，
应该打印
0, 1
0, 2
1, 2
这个经典问题可以用递归回溯，或者迭代回溯解决。递归回溯更清晰好理解。
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 //n = 3 k = 2 0 1 2 中任选两个
5 //输出 0 1
6 // 0 2
7 // 1 2
8 //int for_loop(vector<int>& s,int n,int k,int l = 1) {
9 //
10
11 void ouput(vector<int>& s,int k) {
12 for (int j = 1; j <= k; j++)
13 cout << s[j] << " " ;
14 cout << endl;
15 }
16
17
18 //s[0] is shao bing,start from s[1]
19 //递归回溯的方法
20 void for_loop(vector<int>& s,int n,int k,int l) {
21 for (s[l] = s[l-1]+1; s[l] < n; s[l]++) {
22 if (l == k) {
23 ouput(s,k);
24 } else {
25 // for_loop(s,n,k,l++); //well l++ not acceptable!!! l++ means l will not change!!
26 for_loop(s,n,k,l+1);
27 }
28 }
29
30 }
31
32 //同上的算法 但是消除递归
33 //递归回溯，像8皇后问题，本质上和
34 //多重for 循环是一样的，
35 //for (int i =0; i = 10; i++)
36 // for (int j =0; j < 10; j++) //i =0 入栈，j=09 完成了 i = 0 退栈，i+1 继续
37 //关键都是利用递归，深度优先搜索，当n层搜索完了 退回到n-1层
38 //而不用递归我们就要在循环中模拟退回的过程，要能够回到正确的地点，类似入栈出栈 本质一样
39 //只不过有些时候我们不需要明显的标明栈的存在
40 //for (int i = 0;..)
41 // for (int j = i+1; ..) //而不是 for (int j = 1;)
42 // at first l=1
43 void for_loop_norec(vector<int>& s,int n,int k,int l) {
44 s[l] = 0; //s[1] = 0;
45 while (l) {
46 while(s[l] < n) { //处理当前层
47 if (l == k){ //到达最低层，打印结果
48 ouput(s,k);
49 s[l] += 1; //
50 } else { //否则深度优先，进入下一层
51 l += 1;
52 s[l] = s[l-1] +1;
53 }
54 }
55 l--; //下面的处理完了，跳回上一层
56 s[l] += 1; //to the next pos on this level
57 }
58 }
59
60
61
62
63 int main(int argc, char *argv[]) {
64
65 int n = 6;
66 int k = 3;
67 vector<int> s(n + 1,-1);
68
69 for_loop(s,n,k,1);
70
71 cout << "No rec version" << endl;
72
73 for_loop_norec(s, n, k, 1);
74
75 return 1;
76 }
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2