随笔 - 89  文章 - 118  trackbacks - 0
<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理