算法趣题：不用除法，如何求n个数的最小公倍数

    下面给出一种算法，该算法只需要使用加法运算和比较运算就可以求出n个数的最小公倍数：每一次操作都把当前最小的那个数加上它的初始值，直到所有数都相等为止。下面这个列表显示了用这个算法寻找30, 12, 18三个数的最小公倍数的全过程。初始时12是三个数中的最小数，于是该数加上12；接下来18成了最小的数，于是该数加上18变成了36；此时第二个数24又变成了最小数，于是再加上其对应的初始值12；以此类推直到三个数都变成相同的数180为止，这个180就是30, 12, 18的最小公倍数。

30 12 18
30 24 18
30 24 36
30 36 36
60 36 36
60 48 36
60 48 54
60 60 54
60 60 72
90 60 72
90 72 72
90 84 72
90 84 90
90 96 90
120 96 90
120 96 108
120 108 108
120 120 108
120 120 126
150 120 126
150 132 126
150 132 144
150 144 144
150 156 144
150 156 162
180 156 162
180 168 162
180 168 180
180 180 180

    这个算法为什么是正确的呢？它有什么实际用途呢？

 
    当所有数相等，操作停止时，得到的数肯定是所有数公共的倍数；但如何保证它是最小的公倍数呢？下面我们证明，在整个算法过程中，每个数加到了它们的最小公倍数L后必然停止继续增加。试想，假如某一次操作后n个数的{zd0}值超过了L（不妨设此时这个{zd0}的数是{dy}个数），这就说明r·x1 <= L < (r+1)·x1，其中x1表示{dy}个数的初始值，r·x1和(r+1)·x1分别表示{dy}个数在本次操作前后的值；由于L是x1的倍数，不可能既大于r·x1又小于(r+1)·x1，我们立即知道r·x1就等于L；但r·x1是这一轮中的最小值（因为接下来它被操作了），而在这一轮中还没有超过L的数，于是我们立刻得知此时所有数都等于L，算法已经提前结束了。

    这个算法有一个很有趣的实际用途。假如我有3个MM，与她们各自约会一次的“来电指数”分别为30, 12和18。我希望同这3个MM保持相同的亲近度，最合理的策略就是在相同的时间内与{dy}个MM约会L/30次，与第二个MM约会L/12次，与第三个MM约会L/18次（L仍然表示{zd0}公倍数）。但我不能表现出对MM忽冷忽热的态度，我想让我与每个（特定的）MM的约会频率尽量固定。我应该如何安排具体的约会时间以使得与各MM的约会尽可能平均地分布呢？一个好的做法就是对这三个“来电指数”做一次上述的最小公倍数算法，第i次被操作的是哪个数，第i天就和那个MM出去。

    同样的道理，这个算法经常用来实现一些多线程的任务。假如每个线程需要的刷新速度各不相同，各个线程又需要同步刷新，那么一个不错的办法就是用上述方法来确定每一次来处理哪个线程。

友链：       邻家特工 工具