Sharpmark's Personal Home Page

具体数学 - 约瑟夫问题

It seems a lot of stuff is attributed to Gauss…
either he was really smart or he has great press agent.
May be he just had a magnetic personality.

最近在看《具体数学 Concrete mathematics》,这是一本值得计算机相关专业任何年级的同学阅读的书。
第一章通过三个问题:The Tower of Hanoi; Lines in the Plane; The Josephus Problem. 前两个问题以前学习的深度已经够了,所以看了没有太大感觉,Josephus Problem的解决给了我很大的震撼。一个看似平常而无捷径的问题,通过用二进制表示,最终居然只要用一个循环移位就能解决。之后又扩展到 Josephus方程一般形式。其间,他的解题方法论很重要,以及其严谨的思路和发散的思维。
现列出书中第一章使用的解题方法:

  1. Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3.
  2. Find and prove a mathematical expression for the quantity of interest.
  3. Find and prove a closed form for our mathematical expression.

已经翻译完成The Josephus Problem小节。对此感兴趣的点此下载(版本1.1.1,2007-12-23)。