锐客网

  1. 首页 > it技术 > >

递归回溯与迭代回溯算法框架，打印在n个数字中取k个数字的所有可能

这里给一个例子， 在n个数字中，任意找k个数字（k<=n)，打印所有的可能的情况 例如0, 1, 2在这3 个数中，找2个数字， 应该打印 0, 1 0, 2 1, 2 这个经典问题可以用递归回溯，或者迭代回溯解决。递归回溯更清晰好理解。 1 #include < iostream >
2 #include < vector >
3using namespace std;
4// n = 3 k = 2012中任选两个
5// 输出 0 1
6// 0 2
7// 1 2
8// int for_loop(vector& s,int n,int k,int l = 1) {
9//
10
11void ouput(vector < int >& s, int k) {
12for ( 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// 递归回溯的方法
20void for_loop(vector < int >& s, int n, int k, int l) {
21for (s[l] = s[l - 1 ] + 1 ; s[l] < n; s[l] ++ ) {
22if (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!!
26for_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=0递归回溯与迭代回溯算法框架，打印在n个数字中取k个数字的所有可能
文章图片
9 完成了 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; 递归回溯与迭代回溯算法框架，打印在n个数字中取k个数字的所有可能
文章图片
)
42// at first l=1
43void for_loop_norec(vector < int >& s, int n, int k, int l) {
44 s[l] = 0 ; // s[1] = 0;
45while (l) {
46while (s[l] < n) { // 处理当前层
47if (l == k){ // 到达最低层，打印结果
48ouput(s,k);
49 s[l] += 1 ; //
50} else { // 否则深度优先，进入下一层
51l += 1 ;
52 s[l] = s[l - 1 ] + 1 ;
53 }
54 }
55 l -- ; // 下面的处理完了，跳回上一层
56s[l] += 1 ; // to the next pos on this level
57}
58 }
59
60
61
62
63int main( int argc, char * argv[]) {
64
65int n = 6 ;
66int 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
75return 1 ;
76 }

    推荐阅读


    上一篇：git简单上传/修改上传

    下一篇：算法-数组|最小调整代价