问题：找出整数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
胡满超 阅读(1044)
评论(0) 编辑 收藏 引用