翻硬币问题分析

翻硬币问题分析

我们把每一次的翻转称为一次“小翻转”，从顶上开始连续翻n次称为 　　一次“大翻转”。最后翻到全是正面朝上的状态时，如果用了 a 次大翻转和 b 次小翻转，那么总的翻转次数是 a*n + b。研究一次大翻转的置换结构。自底向上(为方便我们实际上用自左向右)，用 1, 2, 3, ..., n 标记 n 个硬币，用 a' 表示硬币 a 的反面朝上状态。我们还在这一摞硬币的右端放一面镜子，那么，初始状态是：('|' 表示镜子的位置) 　　[1 2 3 4 ... n-1 n | n' (n-1)' ... 4' 3' 2' 1'] 　　经过一次大翻转后，成为： 　　[2 4 6 ... 5' 3' 1' | 1 3 5 ... 6' 4' 2'] 　　这个变换很有规律。只要令 a'=-a，可以看出，一次大翻转就是把编号 　　为 c 的硬币变换到 c/2 (mod 2n+1) 的位置。看其逆变缓将更明显。 　　显然，如果 2^m=1 (mod 2n+1)，那么经过 m 次大翻转后，所有硬币都 　　归到原位而且面朝上。此时共用了 m*n 次小翻转。 　　显然，如果 2^m=-1 (mod 2n+1)，那么经过 m 次大翻转后，所有硬币 　　都将归到原位，并且正面朝下。如果不做最后那个大翻转的最后那个n 　　个硬币翻过来的小翻转，那么就能得到正面全朝下的状态，此时需要 　　m*n-1 次小翻转。剩下的问题是，证明只有上面所述两种情况下才会出现正面全朝上的局面。需要证明几个事实： 　　1) 进行任意次大翻转后，再进行 0 < b < n-1 次小翻转，那么不可 　　能出现全部硬币正面朝上的局面。 　　(即要出现正面全朝上的情况，必然有 b=0 或 b=n-1.) 　　2) 如果经过 m 次大翻转后全部硬币正面朝上，那么确实每个硬币都 　　回到了原来的位置。 　　3) 如果经过 m 次大翻转后全部硬币正面朝下，那么确实每个硬币都 　　回到了原来的位置。 　　2) 与 3) 比较容易证明，证法也类似。1) 证起来麻烦一些。当然可以用数学归纳法来证明。 　　这个就是这个程序的思路，有了思路，我想你这个T和D应该就知道是什么意思了吧？陈晨！