加载中…约瑟夫问题的数学解法理解
(2013-07-10 22:40:30)
标签：
数学问题奇数定理第四解出时 |
分类： 数学问题 |
1条回答
将这些人从0到n编号，假设除去第k个人。
0, 1, 2, 3, ..., k-2, k-1, k, ..., n-1 //original sequence (1)
0, 1, 2, 3, ..., k-2, , k, ..., n-1 //get rid of kth person (2)
k, k+1, ..., n-1, 0, 1, ..., k-2 //rearrange the sequence (3)
0, 1, ..., n-k-1, n-k, n-k+1, ..., n-2 //the n-1 person (4)
我们假设f(n)的值为n个人中最后存活的人的序号，则
注意到(2)式(3)式(4)式其实是同一个序列。
注意(1)式和(4)式，是同一个问题，不同的仅仅是人数。
对比(3)(4)两式，可以看出(3)中的编号x'与(4)中的编号x对应关系即为x'=(x+k) mod n
http://baike.baidu.com/view/213217.htm#5
维基百科的解法
约瑟夫斯问题[编辑]
约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。
有http://upload.wikimedia.org/math/1/4/4/14464ac1dfe6fa8ad8fda94bb6f01571.png个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
问题是，给定了http://upload.wikimedia.org/math/8/c/e/8ce4b16b22b58894aa86c421e8759df3.png，一开始要站在什么地方才能避免被处决？
历史[编辑]
这个问题是以弗拉维奥·约瑟夫斯命名的，它是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。[1]
解法[编辑]
我们将明确解出http://upload.wikimedia.org/math/5/a/b/5ab5433ea7a35395eaa1d6e6920d1866.png的情况，我们在下面给出一个一般的解法。
设http://upload.wikimedia.org/math/0/d/3/0d396ff3798e53a1ab39289aebca85ee.png。这便给出了以下的递推公式：
如果一开始有奇数个人，则走了一圈以后，最终是号码为1的人被杀。于是同样地，再走第二圈时，新的第二、第四、……个人被杀，等等。在这种情况下，位置为http://upload.wikimedia.org/math/b/3/d/b3de2049c76972e1b1e957772f908c1d.png。这便给出了以下的递推公式：
如果我们把http://upload.wikimedia.org/math/a/8/9/a8988ce0f88f5292aa28b6e49f114d45.png的值列成表，我们可以看出一个规律：
| http://upload.wikimedia.org/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| http://upload.wikimedia.org/math/a/8/9/a8988ce0f88f5292aa28b6e49f114d45.png | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
从中可以看出，http://upload.wikimedia.org/math/e/b/5/eb54bd07fc39a9fc8efa6110fc8fd7bc.png。显然，表格中的值满足这个方程。我们用数学归纳法给出一个证明。
定理：如果http://upload.wikimedia.org/math/c/8/d/c8dbaf588cd7a650cd648176da0470e9.png。
证明：对http://upload.wikimedia.org/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png是奇数的情况。
如果http://upload.wikimedia.org/math/b/b/0/bb0911bf3903527e35526633a4cc6d99.png，其中第二个等式从归纳假设推出。
如果http://upload.wikimedia.org/math/8/8/b/88b3d3714a49a681c5b9feccdcfdd4ff.png，其中第二个等式从归纳假设推出。证毕。
答案的最漂亮的形式，与http://upload.wikimedia.org/math/3/4/b/34b39b37c86a8907d603048200528294.png来证明。
在一般情况下，这个问题的最简单的解决方法是使用动态规划。利用这种方法，我们可以得到以下的递推公式：
http://upload.wikimedia.org/math/1/1/5/11532417ab5b29e38c4c9b46e45535d0.png
如果考虑生还者的号码从http://upload.wikimedia.org/math/6/d/6/6d6271d13c4e6e72746fa3f6a93285bc.png个人视为一个步骤，然后把号码改变。
注释[编辑]
-
^
The War of the Jews 3.387-391
参考文献[编辑]
-
Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 14: Augmenting Data Structures, pp.318.
外部链接[编辑]
- cut-the-knot上的约瑟夫斯游戏（Java Applet）
-
埃里克·韦斯坦因,
约瑟夫斯问题 at MathWorld
喜欢
0
赠金笔