問題：找出整數(shù)1~N范圍和為M的所有集合，M<=N且M>1，集合里的數(shù)不允許重復(fù)。
解答：這個(gè)問題用遞歸解決最簡單，代碼如下：
1 #define MAX_NUM 20 //要足夠大
2 int log[MAX_NUM]; //記錄和數(shù)
3 int index = 0; //log[]數(shù)組的當(dāng)前指針
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 }
如果允許重復(fù)只需要將上面第18條代碼改為：
calc(i, n - i);
即可。
擴(kuò)展問題：在數(shù)組{5,1,7,9,2,10,11,4,13,14}中找到和為28的所有集合，集合中不允許有重復(fù)的數(shù)。
解答：第一步要先對(duì)數(shù)組排序，然后按照上去的思路，對(duì)程序略做一些改動(dòng)。
代碼如下：
1 #define MAX_NUM 20 //要足夠大
2 int log[MAX_NUM]; //記錄和數(shù)
3 int index = 0; //log[]數(shù)組的當(dāng)前指針
4
5 void calc__(int *nArr //數(shù)組,
6 int start //數(shù)組起始元素下標(biāo),
7 int nArrLen //數(shù)組長度,
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 }
這個(gè)問題的解答思路是相當(dāng)簡單的，但如何把程序?qū)懙募?xì)致、簡捷是除了解答思路以外的另一個(gè)關(guān)鍵。就像迷宮最短路徑的那個(gè)問題，言語描述很簡單，但把實(shí)現(xiàn)的程序?qū)懞么_要花一些時(shí)間。
posted on 2008-08-29 16:13
胡滿超 閱讀(1055)
評(píng)論(0) 編輯 收藏 引用