24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

ghw_nit

铁杆木虫 (正式写手)

应助: 14 (小学生)
金币: 7901.9
散金: 147
红花: 6
帖子: 653
在线: 175.8小时
虫号: 774851
注册: 2009-05-20
性别: GG
专业: 控制理论与方法

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

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

回复此楼

» 猜你喜欢

求个博导看看已经有16人回复
上海工程技术大学张培磊教授团队招收博士生已经有4人回复
上海工程技术大学【激光智能制造】课题组招收硕士已经有5人回复
求助院士们，这个如何合成呀已经有4人回复
临港实验室与上科大联培博士招生1名已经有9人回复
需要合成515-64-0，50g，能接单的留言已经有4人回复
自荐读博已经有4人回复
写了一篇“相变储能技术在冷库中应用”的论文，论文内容以实验为主，投什么期刊合适？已经有6人回复
带资进组求博导收留已经有10人回复
最近几年招的学生写论文不引自己组发的文章已经有11人回复

1楼 2013-06-04 22:24:06

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

龙文章

木虫 (正式写手)

应助: 4 (幼儿园)
金币: 4065.4
散金: 14
红花: 13
沙发: 17
帖子: 862
在线: 163.6小时
虫号: 2115921
注册: 2012-11-09
性别: GG
专业: 组合数学

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
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)，即得到次大组合。