编程示例：约瑟夫环问题

１约瑟夫环的故事

在浩瀚的计算机语言中，总有一些算法——虽然码量很少，
但却能完美又巧妙地解决那些复杂的问题。接下来，
我们要介绍的“约瑟夫环”问题就是一个很好的例子。

这个问题来源于犹太人约瑟夫经历过的故事，在罗马人
占领乔塔帕特后，约瑟夫和他的朋友与39 个犹太人躲到
一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，
于是决定了一个自杀方式，41个人排成一个圆圈，由第1
个人开始报数，每报数到第3人时，该人就必须自杀，然
后再由下一个人重新报数，直到所有人都自杀身亡为止。

然而约瑟夫和他的朋友并不想遵从这个规则，于是，
他们想出新的思路：从一个人开始，越过k-2个人（
因为第一个人已经被越过），并杀掉第k个人。接着，再
越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，
直到最终只剩下一个人留下，这个人就可以继续活着。

      问题是，给定了和，一开始要站在什么地方才能避免
      被处决？如果你是约瑟夫，你会站在什么样的位置呢？
      数数与大家一起，从运用以下两个方面来解决这个问题。

在这场逃生游戏中，约瑟夫的办法是：他要和他的朋友先假装
遵从，然后将朋友与自己安排在第16个与第31个位置，于是逃
过了这场死亡游戏。约瑟夫安排的位置和你想的位置一样吗？

看完这个”约瑟夫环“问题，如果你是当时逃生的人之一，
你会选择遵从规则，还是改变规则呢？

２该问题的解法的历史回顾

有模拟法和数学推导法，其中美国的高纳德教授还在
<<具体数学>>的书中，给出了推导公式
f(N,M)=(f(N-1,M)+M)%N

３能应用于面试的最佳性能的另类解法

假设初始编号为1，2，······，n，现在考虑一种新的编号方式。
第一个人不会被踢掉，那么他的编号从n开始往后加1，变成n+1，
然后第二个人编号变为n+2，直到第q个人，他被踢掉了。然后
第q+1个人编号继续加1，变成了n+q，依次下去。考虑当前踢到
的人编号为kq，那么此时已经踢掉了k个人，所以接下去的人新
的编号为n+k(q-1)+1……

     所以编号为kq+d的人编号变成了n+k(q-1)+d，其中1<=d<q。
     直到最后，可以发现活下来的人编号为qn，问题是怎么根据
     这个编号推出他原来的编号？以n=10,q=3为例，下图就是每
     个人新的编号：

令N=n+k(q-1)+d，那么他上一轮的编号是kq+d=kq+N-n-k(q-1)=k+N-n,
因为k=(N-n-d)/(q-1)=[(N-n-1)/(q-1)],所以上一次编号可以写为
[(N-n-1)/(q-1)]+N-n