非递增序列
给定 10 * 5 的牌，即由 5 组，每组分别是 1 - 10
从每组中随机选择一张牌，得到的序列是非递减的情况有多少种？
例如 1 1 2 5 9 是符合要求的
但是 2 5 3 7 9 是不符合要求的
最简单的办法是采用 5 个循环求解
1 #include <iostream>
2 using namespace std;
3
4 int main()
5 {
6 int total = 0;
7 for (int a = 1; a != 11; ++a)
8 {
9 for (int b = a; b != 11; ++b)
10 {
11 for (int c = b; c != 11; ++c)
12 {
13 for (int d = c; d != 11; ++d)
14 {
15 for (int e = d; e != 11; ++e)
16 {
17 ++total;
18 cout << a << ' '
19 << b << ' '
20 << c << ' '
21 << d << ' '
22 << e << endl;
23 }
24 }
25 }
26 }
27 }
28 cout << total << endl;
29 }
得到 2002 种情况。
但是采用 5 个循环的方式只是一种最为直观的解法，如果改成 m * n 的情况如何办？
更好的解法应该是用递归。
1 #include <iostream>
2 using namespace std;
3
4 int a[100];
5 int total = 0;
6
7 void foo(int t, int k, int m, int n)
8 {
9
10 if (k >= n)
11 {
12 ++total;
13 for (int i = 0; i != n; ++i)
14 {
15 cout << a[i] << ' ';
16 }
17 cout << endl;
18 return;
19 }
20 else
21 {
22 for (int i = t; i != m + 1; ++i)
23 {
24 a[k] = i;
25 ++k;
26 foo(i, k, m, n);
27 --k;
28 }
29 }
30 }
31
32 void bar(int m, int n)
33 {
34 foo(1, 0, m, n);
35 cout << total << endl;
36 }
37
38 int main()
39 {
40 bar(10, 5);
41 }
42
posted on 2011-11-02 19:57
unixfy 阅读(725)
评论(0) 编辑 收藏 引用