问答 （数学趣味类）《又是馒头惹的？》√已有答案√欢迎拓展和应用√

yzh_nj_china

同意楼上的观点！

fferror

大家如此渴望数学解法（这里可以理解为更简洁的方法），我就转一帖：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换：
k   --> 0
k+1  --> 1
k+2  --> 2
...
...
k-2  --> n-2
k-1  --> n-1 //我觉得应该把这句去掉，去掉后才是(n-1)个人

变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n

如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：

令f[j]表示j个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]。

递推公式
f[1]=0
f[j]=(f[j-1]+m)%j  (j>1)

有了这个公式，我们要做的就是从1-n顺序算出f[j]的数值，最后结果是f[n]。因为实际生活中编号总是从1开始，我们输出f[n]+1。

递推公式都出来了，不必写代码了。

这样是不是简单很多？

yzh_nj_china

100个呢~~
就得推上面100个人的~~~

fferror

回楼上：
递推公式的时间复杂度是线性的，是高效的解法，这种计算量对于计算机是小菜一碟。

1234561

引用第21楼fferror于2007-12-17 19:48发表的 :
大家如此渴望数学解法（这里可以理解为更简洁的方法），我就转一帖：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
.......

似乎也不怎么简单，这样的问题好像就是专门为编程而准备的，用来显示计算机的优势，哈哈哈哈

fferror

计算机有自己的优势所在。人类能够利用自己的智慧，把一个看似复杂的问题规约到计算机所擅长的领域，这体现了人类的高明。而且，计算机本身也是人类智慧的伟大成就。

yzh_nj_china

我的神啊~~纯数学方法快出现吧~~

killl

具体数学第一版中文：
pdf，从verycd获取的，7天有效：


http://exs.mail.foxmail.com/cgi- ... 1e4b6cc96abf5264d80

提取码：1c8e09b4

磁铁

感谢楼上，我也下乐，嘿嘿，下了排除题目用

blueicenan

大家好厉害！我下班接受体检了！1月要出去一趟！呵呵

谢谢磁铁老大！强劲的吸引力！终于在近1500多帖中产生一枚精华！

呜呜呜呜呜

磁铁

都是前几位优秀回帖者造就的精华 ，你还敢躲红包？

nuoan

如果没有计算机，这道题还是不容易有结果的~~
21，
给出一个java程序的Josephus解法

// Josephus.java
//
// Circle List implementation of the Josephus problem

public class Josephus
{
  protected CircleList soldiers; // the circle of potential messengers
  protected int skip;     // number to skip during selection process

  // No-operand constructor.
  // Post: Creates an empty circle.
  public Josephus() {
  soldiers = new CircleList();
  skip = 0;
  }

  // pre: a Josephus object has been created.
  // post: sets up a Josephus situation with numMessengers messengers and
  // a specified number to skip during the selection process.
  public void init(int numMessengers, int numToSkip) {
  soldiers.clear();
  for (int i = 1; i <= numMessengers; i++)
    soldiers.addAfterCurrent(new Integer(i));
  skip = numToSkip;
  }

  // pre: A Josephus problem has been set up, with at least one potential
  //   messenger.
  // post: Messenger selected has been displayed on the screen; those not
  //    selected have had their names printed in the order in which
  //    they were excluded.
  public void findMessenger() {
  soldiers.next();
  while (soldiers.size() > 1) {
    for (int i = 1; i <= skip; i++) {
    System.out.println("Skip " + soldiers.getCurrent());
    soldiers.next();
    }
    System.out.println("Remove " + soldiers.getCurrent());
    soldiers.removeCurrent();
  }
  System.out.println("The messenger is " + soldiers.getCurrent());
  }

  public static void main(String[] args) {
  if (args.length != 2)
    System.out.println( " usage: Josephus <numPeople> <numSkip>" );
  else {
    int num = Integer.parseInt(args[0]);
    int skip = Integer.parseInt(args[1]);
    System.out.println( "Solving Josephus problem with " + num +
        " people, skipping every " + skip);
    Josephus myJosephus = new Josephus();
    myJosephus.init(num, skip);
    myJosephus.findMessenger();
  }
  }
}

fferror

向blueicenan讨红包。为磁铁助威。