| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 620 人关注过本帖
标题:[求助]这里有一道题的源码。大家看看,分析下算法思想。
取消只看楼主 加入收藏
jdxyw2004
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2005-9-24
收藏
 问题点数:0 回复次数:0 
[求助]这里有一道题的源码。大家看看,分析下算法思想。
任给 1<=n<=20 个不同的非零正整数,每个正整数最多使用1次,请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。

例如,
data[] = {1,2,3,4};
ncount = 4;
函数返回 10

分解如下。(0不算)

1 = 1
2 = 2
3 = 3 = 1+2
4 = 4 = 1+3

5 = 2+3 = 1+4
6 = 2+4 = 1+2+3
7 = 3+4 = 1+2+4
8 = 1+3+4
9 = 2+3+4
10 = 1+2+3+4
源码如下
long getsumcount(long data[],long count)
{ std::set<long> sumset;
int state[20] = {0};
long sum = 0,sp = 0;
while(sp>=0)
{ if(sp==count)
{ sumset.insert(sum);
--sp;
}
switch( state[sp] )
{ case 0:
state[sp] = 1;
sum += data[sp];
++sp;
break;
case 1:
state[sp] = 2;
sum -= data[sp];
++sp;
break;
case 2:
state[sp] = 0;
--sp;
break;
}
}
return (long)sumset.size();
}

搜索更多相关主题的帖子: 源码 算法 思想 
2006-05-29 16:18
快速回复:[求助]这里有一道题的源码。大家看看,分析下算法思想。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024098 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved