原文链接：http://www.mydrs.org/program/list.asp?id=297
[问题描述]给出小球钟的运作规则，给出启动时刻的小球个数，求小球重新全部回到原来位置的周期。
[分析]
该题是典型的模拟题。按常规思想：逐分钟地模拟小球钟的运作，直至钟底部的小球队列重又回到初始状态时为止。这期间流逝的天数即为小球钟的运作周期。但这样全部模拟基本上无法在规定的时间内出解，必须做一些改进。
于是，我们想到通过模拟出每个小球回到原来位置上所需的天数，然后求它们的最小公倍数。但是，如果仍是单纯的模拟，速度仍然很慢。
我们可以先模拟小球钟最先24小时的运行情况，得到一天后的钟底部的新小球队列。有了这个条件后，我们可以在两次的钟底部小球队列间建立起一种置换。
设初始时，钟底部的小球编号依次是：1, 2, 3, ..., n。一天后，钟底部的小球编号依次是：p1,p2,p3,...,px 。
则我们可以建立这样的置换
1 2 3 ... n
p1 p2 p3 ... pn
注意到小球钟的运作规则保证了上述置换是不变的，就可以计算出小球钟运行48小时后，72小时后，……，钟底部的小球队列情况，直至队列情况重新是1, 2, 3,…, n。
这样，在求得以上置换的基础上，我们可以求每一个小球回到原位置的周期，然后求它们的最小公倍数即可。
作者：李翼
来源：福建师大附中
时间：2001-12-14
上一篇：《网络传输问题》解题报告
下一篇：