問題：找出整數1~N范圍和為M的所有集合，M<=N且M>1，集合里的數不允許重復。
解答：這個問題用遞歸解決最簡單，代碼如下：
1 #define MAX_NUM 20 //要足夠大
2 int log[MAX_NUM]; //記錄和數
3 int index = 0; //log[]數組的當前指針
4
5 void calc(int start, int n)
6 {
7 if (n == 0)
8 {
9 for(int j = 0; j < index; j++)
10 printf("%d ", log[j]);
11 printf("\n");
12 }
13 else
14 {
15 for(int i = start; i<=n; i++)
16 {
17 log[index++] = i;
18 calc(i + 1, n - i);
19 }
20 }
21
22 index--;
23 }
如果允許重復只需要將上面第18條代碼改為：
calc(i, n - i);
即可。
擴展問題：在數組{5,1,7,9,2,10,11,4,13,14}中找到和為28的所有集合，集合中不允許有重復的數。
解答：第一步要先對數組排序，然后按照上去的思路，對程序略做一些改動。
代碼如下：
1 #define MAX_NUM 20 //要足夠大
2 int log[MAX_NUM]; //記錄和數
3 int index = 0; //log[]數組的當前指針
4
5 void calc__(int *nArr //數組,
6 int start //數組起始元素下標,
7 int nArrLen //數組長度,
8 int sum)
9 {
10 if (sum == 0)
11 {
12 for(int j = 0; j < index; j++)
13 printf("%d ", log[j]);
14 printf("\n");
15 }
16 else
17 {
18 for(int i = start; i < nArrLen; i++)
19 {
20 log[index++] = nArr[i];
21 calc__(nArr, i+1, nArrLen, sum - nArr[i]);
22 }
23 }
24
25 index--;
26 }
這個問題的解答思路是相當簡單的，但如何把程序寫的細致、簡捷是除了解答思路以外的另一個關鍵。就像迷宮最短路徑的那個問題，言語描述很簡單，但把實現的程序寫好確要花一些時間。
posted on 2008-08-29 16:13
胡滿超 閱讀(1060)
評論(0) 編輯 收藏 引用