主题：连续整数和问题
hhjyxq2008
[专家分：0] 发布于 2007-03-06 21:39:00
今天第一次布置的数据结构问题就不会做 大家帮帮忙啊 (已解决 谢谢大家)
问题描述:
大部分正整数都可以表示为2个以上正整数之和.例如,6=1+2+3,9=4+5=2+3+4
编程任务:连续整数和问题要求计算给定的正整数可以表示为多少个2个以上连续整数之和
例如 输入9 则输出2 输入6就输出1
最后更新于：2007-03-07 21:42:00
回复列表 （共11个回复）
沙发
argentmoon [专家分：13260] 发布于 2007-03-06 22:25:00
第一次题目就不想动脑了，这可了得？
板凳
hhjyxq2008 [专家分：0] 发布于 2007-03-06 22:28:00
我已经想了一个晚上
3 楼
argentmoon [专家分：13260] 发布于 2007-03-06 23:12:00
此题是不是from ds.fzu.edu.cn？
搞不好还是校友-_-
如果是，那么这ds作业往往有一个星期的时间，好好想。一个晚上不算什么，难的你还没见到。
4 楼
海上飞洪 [专家分：520] 发布于 2007-03-07 00:23:00
好像是ACM的题目
5 楼
雪光风剑 [专家分：27190] 发布于 2007-03-07 12:46:00
这样：
伪代码：
for i->1~n/2
s=0,j=i
while s<n
s+=j++
如果s和n相同，打印s
6 楼
fiveyes [专家分：310] 发布于 2007-03-07 13:38:00
楼主苦思一个晚上，这种态度是非常好的。在论坛求助，而不是到互联网搜索，显然是不希望简单抄一个答案了事，而是想要掌握解题的方法。
建议楼主继续努力思考，实在不行了，再通过搜索来获取解答。
这里有一些分析：
算法分析
设可行数列为 A = { a1 , a2 , a3 , ... }
根据题意知，A 是一组 d=1 的等差序列，
没 A 有 s 个元素，
则数列和 SA = s * a1 + s(s-1)/2 = n
显然 a1 的取值范围为 ( 1<=a1<=n/2 )
问题就是成了判断一元二次方程有无整数解,
其中 a1 , n 为常数，s 为所求变量。
s = ( -(2*a1-1) + sqrt( (2*a1-1)^2 + 8*n ) ) / 2
如果楼主感到仍然难以解决，可以参考一下这些分析的来源页面，这里除了这些分析，还附了一个完整的程序：
http://blog.csdn.net/zeroDspace/archive/2005/10/22/513471.aspx
7 楼
euc [专家分：4310] 发布于 2007-03-07 14:46:00
只求可能的组数就行了.
int conum (int a)
{
int n = 0;
if (a%2==0 && 2*(a&(a-1)) < sqrt (2*a) || a%2==1) n++;
for (int i = 3; i < sqrt (2*a); i+=2)
if (a%i==0)
n++;
return n;
}
但不敢保证.
8 楼
hhjyxq2008 [专家分：0] 发布于 2007-03-07 20:10:00
我就是福州大学的 星期六就要交了 想不出来啊 能帮帮忙吗 谢谢
9 楼
ororz [专家分：10] 发布于 2007-03-07 20:20:00
学弟加油，给你一个提示，有sqrt(n)的算法。
10 楼
hhjyxq2008 [专家分：0] 发布于 2007-03-07 20:28:00
谢谢大家了
我来回复
您所在位置：