找回密码
 注册
搜索
热搜: 超星 读书 找书
楼主: blueicenan

[科普教学♡] 问答  (数学趣味类)《又是馒头惹的?》√已有答案√欢迎拓展和应用√

[复制链接]
发表于 2007-12-17 19:35:45 | 显示全部楼层
同意楼上的观点!
回复

使用道具 举报

发表于 2007-12-17 19:48:25 | 显示全部楼层
大家如此渴望数学解法(这里可以理解为更简洁的方法),我就转一帖:

问题描述: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。

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

这样是不是简单很多?
回复

使用道具 举报

发表于 2007-12-17 20:05:11 | 显示全部楼层

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

使用道具 举报

发表于 2007-12-17 20:13:43 | 显示全部楼层
回楼上:
递推公式的时间复杂度是线性的,是高效的解法,这种计算量对于计算机是小菜一碟。
回复

使用道具 举报

发表于 2007-12-17 20:15:04 | 显示全部楼层
引用第21楼fferror于2007-12-17 19:48发表的 :
大家如此渴望数学解法(这里可以理解为更简洁的方法),我就转一帖:

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

我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开始):
.......
似乎也不怎么简单,这样的问题好像就是专门为编程而准备的,用来显示计算机的优势,哈哈哈哈
回复

使用道具 举报

发表于 2007-12-17 20:20:42 | 显示全部楼层
计算机有自己的优势所在。人类能够利用自己的智慧,把一个看似复杂的问题规约到计算机所擅长的领域,这体现了人类的高明。而且,计算机本身也是人类智慧的伟大成就。
回复

使用道具 举报

发表于 2007-12-17 20:49:24 | 显示全部楼层
我的神啊~~纯数学方法快出现吧~~
回复

使用道具 举报

发表于 2007-12-17 21:23:10 | 显示全部楼层
具体数学第一版中文:
pdf,从verycd获取的,7天有效:


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

提取码:1c8e09b4
回复

使用道具 举报

发表于 2007-12-17 22:06:33 | 显示全部楼层
感谢楼上,我也下乐,嘿嘿,下了排除题目用
回复

使用道具 举报

 楼主| 发表于 2007-12-17 23:04:49 | 显示全部楼层
大家好厉害!我下班接受体检了!1月要出去一趟!呵呵

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

呜呜呜呜呜
回复

使用道具 举报

发表于 2007-12-18 00:06:24 | 显示全部楼层
都是前几位优秀回帖者造就的精华 ,你还敢躲红包?
回复

使用道具 举报

发表于 2007-12-18 13:12:57 | 显示全部楼层
如果没有计算机,这道题还是不容易有结果的~~
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();
  }
  }
}
回复

使用道具 举报

发表于 2007-12-18 13:29:01 | 显示全部楼层
向blueicenan讨红包。为磁铁助威。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|网上读书园地

GMT+8, 2024-11-1 07:12 , Processed in 0.185396 second(s), 5 queries , Redis On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表