深夜求解一道证明题【数学吧】

数学吧关注：892,397贴子：8,756,540

有n个正整数数，每次选其中两个数a、b进行合并，合并后的结果为a*b+1，一直执行合并直到只剩下一个数为止，假设这个数为x
试证明：
1：每次选取的数为当前剩下的数中最小的两个，所得到的x会是最大的
2：每次选取的数位当前剩下的数中最大的两个，所得到的x会是最小的

送TA礼物

IP属地:广东

1楼2013-10-23 02:39回复

和合并后的得数有关系吗？选了大的不就剩小的了？选了小的不就剩大的了？这不是屁问题吗？

来自iPad2楼2013-10-23 03:08

收起回复

数学归纳法，

IP属地:河南

来自Android客户端3楼2013-10-23 03:42

IP属地:湖北

来自Android客户端4楼2013-10-23 10:43

收起回复

IP属地:湖北

来自Android客户端5楼2013-10-23 10:43

容我UP一下，归纳法暂时想不出来

IP属地:广东

6楼2013-10-23 14:05

厉害

9楼2013-10-30 15:56

其实这题如果放到OI里来讲就应该是一个贪心策略的问题
你每次合并如果是拿两个最大的合并的话
那么这两个最大的代价合并也是当前最大的，
你总是把当前最大代价的合并，所剩下的一定是总价值最大的。

IP属地:浙江

10楼2013-10-30 16:10

下载贴吧APP
看高清直播、视频！

贴吧热议榜

发表回复

内容:

使用签名档查看全部

发表

保存至快速回贴