5个数字相加为指定数

keeya0416 · 发表于 2010-3-19 09:04:00

您需要登录才可以下载或查看，没有账号？欢迎注册

×

在一个递增的整数数列中，怎么以最快的速度找到5个数，使其和为指定数
设数列个数为 N ，指定数为 M。

qianyb · 发表于 2010-3-19 09:42:34

设N个数为Num[N]
用M除以N,得到商为A,余数B
for i=1 to N/2
Num[i]=A+i
Num[N-i]=A-i
next
然后把最大的数加上B
就可以了

keeya0416 · 发表于 2010-3-19 10:11:15

没明白什么意思
怎么得到的是哪5个数呢

keeya0416 · 发表于 2010-3-19 10:15:45

2楼的
你那好像不是这个题目吧

qianyb · 发表于 2010-3-19 10:20:24

你是说从N个递增数中取5个值相加等于M吗?
递增没有规律的话,没什么快捷的方法吧,只能一个个组合试了
如果有规律的话就是先求M除以5的平均值,然后以平均值为中心一边递增,一边递减.然后在最大的值上加上M除以5的余数

keeya0416 · 发表于 2010-3-19 10:25:02

增量没规律的话就只能一个个组合取么
那在取组合的时候有没有什么好的技巧尽量少计算些呢

keeya0416 · 发表于 2010-3-19 14:50:11

原来用5个指针写过一段代码
时间复杂度在o（n）里
不过漏解

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 5个数字相加为指定数