黑马程序员技术交流社区

标题: 约瑟夫问题（报数游戏），大家还有什么更好的方法吗？ [打印本页]

作者: quan23355 时间: 2013-11-27 10:54
标题: 约瑟夫问题（报数游戏），大家还有什么更好的方法吗？
本帖最后由 quan23355 于 2013-11-27 12:45 编辑

有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，报到3的人出列，下一个人继续从1报数，直到最后剩下一个孩子为止。问剩下第几个孩子。
下面的程序以10个孩子为例，模拟了这个过程，请完善之（提示：报数的过程被与之逻辑等价的更容易操作的过程所代替）。

第一种方法（蓝桥杯给出的答案）：数到不是出列的孩子删除并把这个孩子加到队列的最后，数到出列的孩子直接删除，直到只剩下最后一个孩子为止

Vector a = new Vector();
for(int i=1; i<=10; i++)
{
a.add("第" + i + "个孩子");
}
for(;;)
{
if(a.size()==1) break;
for(int k=0; k<2; k++)
a.add(a.remove(0));
a.remove(0);
}
System.out.println(a);

复制代码

第二中方法（看了韩顺平老师的视频我自己做的）：利用引用来模拟出循环链表来决解

class Peoson{//定义一个孩子类
int num; //孩子编号
static int count=0; //正在游戏中的孩子总数
Peoson getNext=null;//本类的引用，用来指向下一个孩子.
Peoson(int num){
count++; //每创建一个孩子加1
this.num=num;
}
}
public class BaoshuGame {
public static void main(String[] args) {
Peoson p=new Peoson(1); //创建第一个孩子//
Peoson p1=p; //p1表示指针，开始p1为第一个孩子
for (int i = 2; i <= 10; i++) {
//从第二个孩子开始创建，并且前一个孩子指向下一个孩子
Peoson p2=new Peoson(i);//创建孩子对象
p1.getNext=p2; //p1指向这个孩子
p1=p2; //p1变为这个孩子（和p1指向这个孩子是不同的概念，这里实现了p1的移动）
}
p1.getNext=p; //到这为止，p1为最后一个孩子，并指向第一个孩子，循环链表已经形成
//下面开始报数
/*
* 实现过程是：报到的孩子出列，即这个孩子的前一个孩子指向这个孩子的下一个孩子，让
* 这个孩子成为野孩子
* */
while(Peoson.count!=1){
Peoson p2=null;
for (int i = 1; i < 3; i++) {
p2=p;
p=p.getNext;
}
//循环两次后p为第三个孩子了，即要出列的孩子，p2为出列孩子的前一个孩子
p2.getNext=p.getNext;//出列孩子的前一个孩子指向出列孩子的下一个孩子
p=p.getNext;//从出列孩子的下一个孩子开始
Peoson.count--;//孩子个数减1
}
System.out.println(p.num);//打印最后一个孩子的编号，游戏结束
}
}

复制代码

作者: 殷挥笔 时间: 2013-11-27 11:28

import java.util.*;
public class Test2 {
/**
* 有n个孩子站成一圈，从第一个孩子开始顺时针方向报数，报到3的人出列，下一个人继续从1报数，直到最后剩下一个孩子为止。问剩下第几个孩子。
* 下面的程序以10个孩子为例
*/
public static void main(String[] args) {
int num =run(10);
System.out.println("剩下的是第"+num+"人");
}
public static int run(int a) {
List<Integer> list = new LinkedList<Integer>();
for (int i = 1; i <= a; i++) {
list.add(i);
}
int count = 1;
for (int j = 0; list.size() != 1; j++) {
if (j == list.size())
j = 0;
if (count % 3 == 0)
list.remove(j--);
count++;
}
return list.get(0);
}
}

复制代码

这是我写的，楼主看看吧

作者: 石头6004 时间: 2013-11-27 11:34
本帖最后由石头6004 于 2013-11-27 11:43 编辑

上面用循环链表实约瑟夫问题，要模拟整个游戏过程，不仅程序写起来比较麻烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

这里用递推来写：

package cn.itcast;

public class Josephus {

      public static void main(String[] args) {

            int n= 10, m = 3, i, s=0;

            for (i=2; i<=n; i++)

                     s=(s+m)%i;

      System.out.println("The winner is:" + (s+1));

      }

}
复制代码

作者: lovecx24 时间: 2013-11-29 18:18
也可以用数组实现啊：

mport java.util.Scanner;
/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
*/
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
//提示输入总人数
System.out.println("请输入做这个游戏的总人数：");
Scanner sca=new Scanner(System.in);
int m=sca.nextInt();
//提示输入要出圈的数值
System.out.println("请输入要出圈的数值：");
int n=sca.nextInt();
System.out.println("按出圈的次序输出序号：");
//创建有m个值的数组
int[] a=new int[m];
//初始长度，以后出圈一个，长度就减一
int len=m;
//给数组赋值
for(int i=0;i<a.length;i++)
a[i]=i+1;
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(len>0){
if(a[i%m]>0){
if(j%n==0){//找到要出圈的人，并把圈中人数减一
System.out.print(a[i%m]+" ");
a[i%m]=-1;
j=1;
i++;
len--;
}else{
i++;
j++;
}
}else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
i++;
}
}
}
}

复制代码

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2