标题：灵魂守恒定律
出处：Felix021
时间：Fri, 22 Oct 2010 23:54:10 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1945

内容：
一切都是从，那道蚂蚁题，开始的
那题中的蚂蚁有20只，爬在长的木棒一根
左边蚂蚁10只向右爬
右边蚂蚁10只向左爬
蚂蚁爬的速度都相同
一碰头各自原速调头
然后就问，这些个蚂蚁，要碰多少次头才会从木棒上都掉下去

一说起这个问题，可能很多人有看过编程之美4.7 蚂蚁爬杆的问题：有一根27厘米长的细长木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置 处各有一只蚂蚁。木杆很细，不能同时通过2只蚂蚁。开始时候，蚂蚁的头朝左还是朝右是任意的，他们只会朝前走或者掉头，但是不会后退。当任意2只蚂蚁碰头后时，2只蚂蚁会同时掉转头朝反方向走。架设蚂蚁每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最短时间和最长时间。

留一些空间不剧透，有兴趣的同学可以先想想然后再往下看。

啦
啦
啦
啦
啦
啦
啦
啦
啦
啦
啦
啦


两只蚂蚁碰头的时候，既然只是各自掉头且速度不变，那么可以认为，在不严格区分两只蚂蚁（比如要求具体某只蚂蚁的运动路径）时，两只蚂蚁只是擦肩而过，继续往前走。在编程之美4.7中，通过这种假设来分析，既然每一只蚂蚁都是继续向前走，那么离运动方向端点最近的蚂蚁耗时最短，反之最长。

回到最初的喷头次数问题上，其实问题的切入点已经在标题中给出了（这个名字是Jieyu想出来的，借用一下，嗯）："灵魂守恒"。对于任意一只蚂蚁，不假设每只蚂蚁在碰头的时候继续往前走，只是假设在每次喷头时两只蚂蚁交换了"灵魂"，于是向左的灵魂继续向左，向右的灵魂继续向右（这并不影响碰头的次数）。于是每一只蚂蚁的灵魂都是不断向前的，那么每只向右的蚂蚁的灵魂在向前爬的时候，都会遇到10只向左的蚂蚁的灵魂，进行10次交换，由于灵魂和身体一一对应（灵魂守恒），每个灵魂交换的次数，也就是所有蚂蚁碰头的次数。所以最后的答案是10×10。

这个证明不太严谨。如果使用继续向前走的方式，就可以用很严格的数学来进行证明。我们甚至可以推广到m只向右n只向左的情况，结论是m*n次碰头。证明过程么——数学归纳法。

在1:1 (1只向左，1只向右)的情况下，很显然结果是 1次 = 1 × 1。
假设1:k (1只向左，k只向右)的情况下，需要碰头 k次 = 1 × k。
那么当n = k + 1的时候，很容易通过1:k推广到1:(k+1)的情况，证明需要 (1 × k) + 1 = 1 × (k + 1) = k + 1次
再假设当 x : n 的时候，需要 x * n次
那么当m = x + 1时，可以通过 x:n的情况推广到(x+1):n的情况，证明需要 (x × n) + n = (x + 1) × n次
所以m:n的情况下需要m * n次。


Generated by Bo-blog 2.1.0