应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 专业学科区 » 数学 » 计算数学 » 已经排好序的数组的求和问题
141/2返回列表12下一页
查看: 1719  |  回复: 13
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

ghw_nit

铁杆木虫 (正式写手)

[求助] 已经排好序的数组的求和问题

现有一个排好序的数组，假如这个数组有n个数，此时的排序是由大到小排列的，在这n个数中任取m个数加和，这种和有什么关系呢？
假如我取5个数，那么我可以肯定的说这个数组中前五个数的和是所有的五个数的组合中最大的拿一个，那么次大的是哪一个，是不是把第五个数去掉，换成第六个数就是次大的呢，第三大的是把第五个位置换成第七个数呢，这是我的猜测，不能证明，不知道我的猜测是不是对，能不能证明这件事呢。希望有人能指点一下。谢谢
回复此楼

» 猜你喜欢
1楼 2013-06-04 22:24:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
回帖支持 ( 显示支持度最高的前 50 名 )

weft

木虫 (正式写手)

【答案】应助回帖

引用回帖:
4楼: Originally posted by ghw_nit at 2013-06-05 07:54:51
是的，昨天有点晕了，现在已经向清楚了

你这个猜想不成立, 事情似乎没那么简单. 你看看下面的例子(n=5): 考察递降数组: 7, 6, 5, 4, 1. 在m=3的情形, 最大的和是7+6+5=18, 次大的是7+6+4=17, 但是第三大的并不是7+6+1=14, 而应该是7+5+4=16.
赞一下(2人) 回复此楼
5楼2013-06-06 03:27:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
普通回帖

weft

木虫 (正式写手)

【答案】应助回帖

感谢参与，应助指数 +1
话说, 这不是排序不等式的直接推论吗?
赞一下 回复此楼
2楼2013-06-05 05:53:53
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pippi6

铁杆木虫 (著名写手)

工程和科学数值计算咨询
你的猜测成立应该是比较明显的，证明好像也就是个力气活吧
赞一下 回复此楼
3楼2013-06-05 06:08:23
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ghw_nit

铁杆木虫 (正式写手)
是的，昨天有点晕了，现在已经向清楚了
赞一下 回复此楼
4楼2013-06-05 07:54:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

ghw_nit

铁杆木虫 (正式写手)
能不能进一步的帮我分析一下呢，我现在是再设计一个算法，数据量比较大，现在找的方式就是穷举法了，效率比较低，我想要分析这个过程就是想要降低一下搜索的范围。谢谢
赞一下 回复此楼
6楼2013-06-06 07:53:08
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

leungzipang

银虫 (小有名气)

【答案】应助回帖

感谢参与，应助指数 +1
可以这么想：在序列中插入辅助元素，使它成为等差序列。等差的情况是好办的。
写出这个等差列的所有组合情况，把它们的和排序，然后去掉那些含有辅助元素的组合，剩下就是你要的了。
赞一下 回复此楼
7楼2013-06-07 15:27:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

pippi6

铁杆木虫 (著名写手)

工程和科学数值计算咨询
引用回帖:
5楼: Originally posted by weft at 2013-06-06 03:27:04
你这个猜想不成立, 事情似乎没那么简单. 你看看下面的例子(n=5): 考察递降数组: 7, 6, 5, 4, 1. 在m=3的情形, 最大的和是7+6+5=18, 次大的是7+6+4=17, 但是第三大的并不是7+6+1=14, 而应该是7+5+4=16....

5 楼的反例举得好。不愧为敏才。
赞一下 回复此楼
8楼2013-06-07 18:05:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

weft

木虫 (正式写手)

【答案】应助回帖

引用回帖:
7楼: Originally posted by leungzipang at 2013-06-07 15:27:56
可以这么想：在序列中插入辅助元素，使它成为等差序列。等差的情况是好办的。
写出这个等差列的所有组合情况，把它们的和排序，然后去掉那些含有辅助元素的组合，剩下就是你要的了。

想法好是好, 但暂且先不论这么插入之后的计算复杂度(我想这是楼主最关心的), 套用一部电影的名字, 就是Mission Impossible. 看这个例子: , 很容易证明, 不管你怎么在中间插入数字, 都不可能得到一个等差数列, 否则就与是无理数相矛盾了.
赞一下 回复此楼
9楼2013-06-08 01:56:14
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

龙文章

木虫 (正式写手)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
ghw_nit: 金币+30, ★★★很有帮助 2013-06-08 20:09:47
一个组合变为次大的组合，肯定是其中某一个数，被替换为紧邻它的下一个数，前提当然是紧邻它的下一个数不在原组合中。所以我们要找到替换哪一个数，差值最小，即可得到次大组合。

注：本文一些符号表示为下角标，请脑补。。。
新建一个数组x[n],记由大到小排列后数组为x1, x2, x3, ... , x(n).
新建一个数组i[m]，每一项都是不大于n的正整数，用以表示这m个数在原数组中的位置，即
i1, i2, i3, ... , i(m) 表示取到的m个数为 x(i1), x(i2), x(i3), ... x(i(m)).

我觉得需要构建一个新的数组d[n-1]，为原数组相邻两数之差，即d1 = x1 - x2, d2 = x2 - x3, ... , d(n-1) = x(n-1)- x (n).

对于每一个i1, i2, i3, ... , i(m) ，如果i值+1已在阵中，那么不继续考虑；如果i值+1不在阵中，那么找到d(i值)。然后比较所得的最多m个d(i值)，找出最小的那个，对应的x(i值)就是要被替换的那个，把它换成x(i值+1)，即得到次大组合。
赞一下 回复此楼
10楼2013-06-08 17:28:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 ghw_nit 的主题更新
141/2返回列表12下一页
普通表情 龙 兔 虎 猫
信息提示
关闭
请填处理意见
关闭