| 查看: 2207 | 回复: 13 | ||
ghw_nit铁杆木虫 (正式写手)
|
[求助]
已经排好序的数组的求和问题
|
|
|
现有一个排好序的数组，假如这个数组有n个数，此时的排序是由大到小排列的，在这n个数中任取m个数加和，这种和有什么关系呢？ 假如我取5个数，那么我可以肯定的说这个数组中前五个数的和是所有的五个数的组合中最大的拿一个，那么次大的是哪一个，是不是把第五个数去掉，换成第六个数就是次大的呢，第三大的是把第五个位置换成第七个数呢，这是我的猜测，不能证明，不知道我的猜测是不是对，能不能证明这件事呢。希望有人能指点一下。谢谢 |
回复此楼» 猜你喜欢
估计是周四
已经有3人回复
-
基金啊基金
已经有3人回复
-
科研孤儿太难了
已经有15人回复
-
让我中一个面上吧！
已经有10人回复
-
言之凿凿，明天官网会通知放榜？
已经有17人回复
-
时间戳又变了
已经有17人回复
-
今天系统多次维护，明天很可能放榜！
已经有11人回复
-
时间戳变了，能看出什么问题？
已经有23人回复
-
只有每年这种时候来逛逛小木虫
已经有22人回复
-
放榜前的不淡定
已经有12人回复
5楼2013-06-06 03:27:04
2楼2013-06-05 05:53:53
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
3楼2013-06-05 06:08:23
ghw_nit
铁杆木虫 (正式写手)
- 应助: 14 (小学生)
- 金币: 7901.9
- 散金: 147
- 红花: 6
- 帖子: 653
- 在线: 175.8小时
- 虫号: 774851
- 注册: 2009-05-20
- 性别: GG
- 专业: 控制理论与方法
4楼2013-06-05 07:54:51
ghw_nit
铁杆木虫 (正式写手)
- 应助: 14 (小学生)
- 金币: 7901.9
- 散金: 147
- 红花: 6
- 帖子: 653
- 在线: 175.8小时
- 虫号: 774851
- 注册: 2009-05-20
- 性别: GG
- 专业: 控制理论与方法
6楼2013-06-06 07:53:08
leungzipang
银虫 (小有名气)
- 应助: 27 (小学生)
- 金币: 322.5
- 散金: 411
- 红花: 4
- 帖子: 144
- 在线: 52.1小时
- 虫号: 2361501
- 注册: 2013-03-20
- 性别: GG
- 专业: 天体力学和人造卫星动力学
7楼2013-06-07 15:27:56
pippi6
铁杆木虫 (著名写手)
工程和科学数值计算咨询
- 数学EPI: 6
- 应助: 413 (硕士)
- 贵宾: 0.002
- 金币: 7116.5
- 散金: 15
- 红花: 63
- 帖子: 1639
- 在线: 798.9小时
- 虫号: 2469437
- 注册: 2013-05-14
- 专业: 计算数学与科学工程计算
8楼2013-06-07 18:05:02
9楼2013-06-08 01:56:14
龙文章
木虫 (正式写手)
- 应助: 4 (幼儿园)
- 金币: 4065.4
- 散金: 14
- 红花: 13
- 沙发: 17
- 帖子: 862
- 在线: 163.6小时
- 虫号: 2115921
- 注册: 2012-11-09
- 性别: GG
- 专业: 组合数学
【答案】应助回帖
★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
ghw_nit: 金币+30, ★★★很有帮助 2013-06-08 20:09:47
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
