求正确性证明

[俞天行 (ytxqωq)]

我刚投胎

[stringdp100005]

还是没想出来，捞一下

[我命由我不由天 (ゴテンクス)]

@stringdp100005 等一下哈，我在写作业

[枣伊吕波 (一只普通的车长)]

bushi,你作业还没写完？

[解雨臣 (栤酱)]

好久的作业

[stringdp100005]

你要写多久啊。

[我命由我不由天 (ゴテンクス)]

@连晨皓 @王天皓 @stringdp100005 马上了，还差 5 篇背诵就好了，我已经把最难的那两张卷子写完了

[解雨臣 (栤酱)]

啊啊啊啊啊啊啊！！？？

[360病毒 (只会打暴力的人)]

bushi，你们作业这么多？几科啊？

[stringdp100005]

再催

[stringdp100005]

啊啊啊啊

[我命由我不由天 (ゴテンクス)]

@360病毒 当然是 3 科呀，我又不是初中生

[我命由我不由天 (ゴテンクス)]

@stringdp100005 不要着急 qwq，就是分为三种：

1. 偶数
2. 模 4 余 1
3. 模 4 余 3

讨论，然后归纳就好了，中间可能还要局部调整（现在打不了等晚点说

[stringdp100005]

我分讨推了半天也没推出来啊

[2345安全卫士 (蛋小黄（蒟蒻）)]

你代码是啥，我看不到

[stringdp100005]

这个

[2345安全卫士 (蛋小黄（蒟蒻）)]

[我命由我不由天 (ゴテンクス)]

@stringdp100005 就是你先算出前三个 1,2,3 先

• 如果 n 是偶数，这个时候的结论就是走 \frac{n}{2} 是最优的
  那么根据之前的 \frac{n}{2} 这个要走的步数我们是知道的，对吧？那么反向推就有一种是 n→\frac{n}{2}→\dots → 1 对吧，那么如果有比这个更优的话必须要满足 step(n)=\min\left\{step(\frac{n}{2})+1,step(n-1)+,step(n+1)+1\right\} 对吧，那么由于归纳的这个假设是 step(\frac{n}{2})≤step(n-1),step(n+1) 所以走 \frac{n}{2} 最优。

剩下的两种情况同理

[stringdp100005]

我的数学太垃圾了 /kel
另外 \operatorname{step} \operatorname{step}

[我命由我不由天 (ゴテンクス)]

@stringdp100005 e这个我知道，但是那个时候，不能打这么多字，因为我妈妈随时可能出来 qwq