关于一推论
  • 板块学术版
  • 楼主盐焗蛋
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/5/7 20:08
  • 上次更新2023/10/23 16:23:21
查看原帖
关于一推论
709361
盐焗蛋楼主2023/5/7 20:08

这个推论的初衷是为了优化某题的时间复杂度,但不知怎么的脑子混沌,推不下去了。(虽然真的很简单)

给一个长度nn的数列

|(a1a_1-ana_{n})|+|(a2a_2-an−1a_{n-1})|+|(a3a_3-an−2a_{n-2})|+……+|(a(1+n)/2a_{(1+n)/2}-a(1+n)/2a_{(1+n)/2})|……

我们拆括号,应该是:

|a1a_1-ana_{n}|+|a2a_2-an−1a_{n-1}|+|a3a_3-an−2a_{n-2}|+……+|a(1+n)/2a_{(1+n)/2}-a(1+n)/2a_{(1+n)/2}|

这个时候,我们可以清楚的发现,a1a_1,a2a_2,a3a_3这些数可以合并起来,变成a1a_1+a2a_2+a3a_3。ana_{n},an−1a_{n-1},an−2a_{n-2}也可以合并起来,变成ana_{n}-an−1a_{n-1}-an−2a_{n-2}。

于是乎,就变成|(a1a_1+a2a_2+a3a_3+……+a(1+n)/2a_{(1+n)/2})|-|(ana_{n}+an−1a_{n-1}+an−2a_{n-2}+……+a(1+n)/2a_{(1+n)/2})|,两边都出现了a(1+n)/2a_{(1+n)/2},抵消成|(a1a_1+a2a_2+a3a_3+……+a(1+n)/2−1a_{(1+n)/2-1})|-|(ana_{n}+an−1a_{n-1}+an−2a_{n-2}+……+a(1+n)/2+1a_{(1+n)/2+1})|

这样子对吗?(处于脑子不正常状态下推出这个结论的我)

这样是可以举出反例的。

如nn=5时,数列为4、1、3、9、2。

|4-2|+|1-9|+|3-3|=10

而按照我的推论,应为|(4+1)|-|(9+2)|=6

嗨嗨嗨,推错了。

那,正确应该怎么推呢?(本人5年级,当时脑子混沌,哪里写错了勿喷)

2023/5/7 20:08
加载中...