面对现实,超越自己
逆水行舟,不进则退
posts - 269,comments - 32,trackbacks - 0
转自:http://www.cppblog.com/humanchao/archive/2008/08/29/60368.html

问题找出整数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 2012-04-10 12:37 王海光 阅读(632) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理