非遞增序列
給定 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 閱讀(746)
評論(0) 編輯 收藏 引用