【约瑟夫环的问题】

Question

【约瑟夫环的问题】
有17个人（编号从0到16），按编号依次排列成一个圆环（编号16的接着编号为0 的人），从编号为0 的人开始报数，数到3的人退出圆环，如此循环，最后留下的那个人的编号是什么？
0，1，2，3，4，5，6，7，8，，9，10，11，12，13，14，15，16
要求：请用面向对象的思想来处理这个问题并在下面写出具体的代码（可以选择你熟悉的语言，如java/C++/C#等）

Answer 1

import java.util.ArrayList;public class Test
{
public static int test(int len)
{
ArrayList<String> data = new ArrayList<String>();
for(int i = 0; i <= len - 1; i++)
{
data.add(i + "");
}
int search = 0;
for(int i = 0; i < len - 1; i++)
{
search += 2;
search %= data.size();
System.out.println(data.remove(search));
}
return Integer.parseInt(data.get(0).toString());
}

public static void main(String[] args)
{
int result = test(17);
System.out.println("final result:" + result);
}
}

Answer 2

public class Josephus {  /**
   * 自己的编号
   */
  private final int number;  /**
   * 链表指针
   */
  private Josephus previous;  /**
   * 链表指针
   */
  private Josephus next;  /**
   * 创建一个新的<code>Josephus</code>对象。
   * 
   * @param number
   *          自己的编号
   */
  public Josephus(int number) {
    this.number = number;
  }  
  /**
   * 返回 <code>number</code> 的当前值。
   *
   * @return <code>number</code> 的当前值
   */
  public int getNumber() {
    return number;
  }  /**
   * 返回 <code>previous</code> 的当前值。
   * 
   * @return <code>previous</code> 的当前值
   */
  public Josephus getPrevious() {
    return previous;
  }  /**
   * 设置 <code>previous</code> 的当前值。
   * 
   * @param previous
   *          <code>previous</code> 的当前值
   */
  public void setPrevious(Josephus previous) {
    this.previous = previous;
  }  /**
   * 返回 <code>next</code> 的当前值。
   * 
   * @return <code>next</code> 的当前值
   */
  public Josephus getNext() {
    return next;
  }  /**
   * 设置 <code>next</code> 的当前值。
   * 
   * @param next
   *          <code>next</code> 的当前值
   */
  public void setNext(Josephus next) {
    this.next = next;
  }  /**
   * 从自己开始报数，报到的人被踢走。
   * 
   * @param n
   *          报的数字
   * @return 被踢走的人
   */
  public Josephus startCountingOut(int n) {
    Josephus current = this;
    for (int i = 1; i < n; i++) {
      current = current.getNext();
    }
    return current.countOut();
  }  /**
   * 从自己开始报3个数，报到的人被踢走。
   * 
   * @return 被踢走的人
   */
  public Josephus startCountingOut() {
    return startCountingOut(3);
  }  /**
   * 被报到，而被踢走
   * 
   * @return 被踢走的人
   */
  private Josephus countOut() {
    previous.setNext(next);
    next.setPrevious(previous);
    return this;
  }
  
  @Override
  public String toString() {
    StringBuilder buff = new StringBuilder(64);
    buff.append("Josephus");
    buff.append("\nNum:  ").append(number);
    buff.append("\nPrev: ").append(previous.getNumber());
    buff.append("\nNext: ").append(next.getNumber());
    return buff.toString();
  }
    public static Josephus init(int n) {
    Josephus[] arrays = new Josephus[17];
    for (int i = 0; i < arrays.length; i++) {
      arrays[i] = new Josephus(i);
    }
    for (int i = 0; i < arrays.length; i++) {
      arrays[i].setNext(arrays[(i + 1) % n]);
      arrays[i].setPrevious(arrays[(i + n - 1) % n]);
    }
    return arrays[0];
  }  public static void main(String[] args) {
    Josephus j = init(17);
    do {
      System.out.println("报数的人:");
      System.out.println(j);
      j = j.startCountingOut();
      System.out.println("被踢走的人:");
      System.out.println(j);
      // 移交给下一个人
      j = j.getNext();
    } while ((j.getNext()) != j); // 就他一个了
    System.out.println("最后的幸存者:");
    System.out.println(j);
  }
}
比如这个

Answer 3

kan kan  呵呵  

Answer 4

能不能解释一下，第二个for循环那里的算法，是怎么想到要这样写的呢？

Answer 5

  public static int jos( int people, int passes )
    {
        Collection<Integer> theList = new LinkedList<Integer>( );            // Construct the list
        for( int i = 1; i <= people; i++ )
            theList.add( i );            // Play the game;
        Iterator<Integer> itr = theList.iterator( );
        while( people-- != 1 )
        {
            for( int i = 0; i <= passes; i++ )
            {
                if( !itr.hasNext( ) )
                    itr = theList.iterator( );
         
                itr.next( );
            }               
            itr.remove( );    
        }
        
        itr = theList.iterator( );        return itr.next( );
    }

Answer 6

import java.util.List;
import java.util.ArrayList;class Team{
private List<people> peoplelst;
private int len;

public Team(){
len = 0 ;
peoplelst = new ArrayList<people>();
}

public void setLen(int length){
len = length;
}

public void init(){
for(int i = 0 ; i < len ; i++)
peoplelst.add(new people(i));
}

public void remove(int num){
peoplelst.remove(num);
}

public int size(){
return peoplelst.size();
}

public int getFirst(){
return peoplelst.get(0).getNum();
}

public int getNum(int index){
return peoplelst.get(index).getNum();
}
}class people{
private int num;
public people(int number){
num = number;
}

public int getNum(){
return num;
}
}class call{
private static int status = 0;

public static void call(){
status++;
}

public static void recall(){
status = 0;
}

public static Integer getStatus(){
return status;
}
}public class Test{

public static void main(String[] args){
Team t = new Team();
t.setLen(17);
t.init();
int index = -1;
//开始游戏
while(t.size() != 1){
call.call();
index ++;
if(index > t.size() - 1){
index = 0;
}
if(call.getStatus() == 3){
t.remove(index);
index-- ;
call.recall();
}

}
System.out.println(t.getFirst());
}
}

Answer 7

public class Count3Quit {
public static void main(String[] args) {
PersonCircle pc = new PersonCircle(17);
int countNum = 0; //0,1,2,3报数
Person p = pc.first;
while (pc.count > 1) {
countNum++;
if (countNum == 3) {
countNum = 0;
pc.delete(p);
}
p = p.right;
} System.out.println(pc.first.id);
}
}
/**
 * 人类具有id, 该人两边的人引用 
 */
class Person {
int id;
Person left;
Person right;
}/**
 * 人构成一圈的类 
 */
class PersonCircle {
int count = 0;
Person first, last; PersonCircle(int n) {
for (int i = 0; i < n; i++) {
add();
}
}
/**
 * 把一人加入到圈中
 */
void add() {
Person p = new Person();
p.id = count;
if (count <= 0) {
first = p;
last = p;
p.left = p;
p.right = p;
} else {
last.right = p;
p.left = last;
p.right = first;
first.left = p;
last = p;
}
count++;
}
/**
 * 从圈中删除一个人
 * @param p
 */
void delete(Person p) {
if (count <= 0) {
return;
} else if (count == 1) {
first = last = null;
} else {
p.left.right = p.right;
p.right.left = p.left; if (p == first) {
first = p.right;
} else if (p == last) {
last = p.left;
}
}
count--;
}
}
希望对你有帮助

Answer 8

简单易懂
参考
public class Test {
public static void main(String[] args) {
boolean[] arr = new boolean[17];
for(int i=0; i<arr.length; i++) {
arr[i] = true;
}

int leftCount = arr.length;
int countNum = 0;
int index = 0;

while(leftCount > 1) {
if(arr[index] == true) {
countNum ++;
if(countNum == 3) {
countNum = 0;
arr[index] = false;
leftCount --;
}
}

index ++;

if(index == arr.length) {
index = 0;
}
}

for(int i=0; i<arr.length; i++) {
if(arr[i] == true) {
System.out.println(i);
}
}
}
}

Answer 9

java 的代码
  public class Josephus {
    public static int[] arrayOfJosephus(
                               int number, int per) {
        int[] man = new int[number];         for(int count = 1, i = 0, pos = -1; 
                count <= number; count++) { 
            do { 
                pos = (pos+1) % number;  // 環狀處理 
                if(man[pos] == 0) 
                    i++;                 if(i == per) {  // 報數為3了 
                    i = 0; 
                    break; 
                } 
            } while(true);             man[pos] = count; 
        } 
        
        return man;
    }    public static void main(String[] args) {
        int[] man = Josephus.arrayOfJosephus(41, 3);
        int alive = 3;
        
        System.out.println("約琴夫排列："); 
        for(int i = 0; i < 41; i++) 
            System.out.print(man[i] + " "); 
        System.out.println("\nL表示3個存活的人要放的位置："); 
        for(int i = 0; i < 41; i++) { 
            if(man[i] > alive) 
                System.out.print("D"); 
            else 
                System.out.print("L");             if((i+1) % 5 == 0) 
                System.out.print("  "); 
        }         System.out.println();
    }
}

Answer 10

谢谢 貌似是对的
List<Person> list = new ArrayList<Person>();
//初始化
for(int i = 0;i<17;i++){
list.add(new Person(i));
}

int size = list.size(); //第一次的人数
int index = 0; //第一次的开始下标
int temp = 0; //第一次之前余数 
while(list.size()>1){
try{
index+=2; //向前2个人，就是数3个人
list.remove(index); //剔除数3个人
}catch(IndexOutOfBoundsException e){
index = 0; //下标清空
index -= (size+ -temp) % 3; //得到刚才一轮剩余的人
temp = index; //暂时存放刚才一轮剩余的人
size = list.size(); //得到新一轮的人数
}
}
System.out.println(list.get(0)); //输入最后的那个人

Answer 11

public class Game1 {
public static void main(String[] args) {
int[] g = new int[17];
int m = 0;//记录有多少个元素的值是3
int j = 0;
while (m < 16) {
for (int i = 0; i < g.length; i++) {
j++;
if (g[i] != 3) {
g[i] = j;
} else {
j--;//给下一个g[]赋值，这里是保持j的值不变
}
if (j == 3) {
j = 0;
m ++;
}
}
}
for (int i = 0; i < g.length; i++) {
if (g[i] != 3) {
System.out.print(i + 1);
}
}
}
}
输出结果是：第11个人

Answer 12

public class Count3Quit2 {
public static void main(String[] args) {
KidCircle kc = new KidCircle(17);
int countNum = 0;
Kid k = kc.first;
while(kc.count > 1) {
countNum ++;
if(countNum == 3) {
countNum = 0;
kc.delete(k);
}
k = k.right;
}

System.out.println(kc.first.id);
}
}class Kid {
int id;
Kid left;
Kid right;
}class KidCircle {
int count = 0;
Kid first, last;

KidCircle(int n) {
for(int i=0; i<n; i++) {
add();
}
}

void add() {
Kid k = new Kid();
k.id = count;
if(count <= 0) {
first = k;
last = k;
k.left = k;
k.right = k;
} else {
last.right = k;
k.left = last;
k.right = first;
first.left = k;
last = k;
}
count ++;
}

void delete(Kid k) {
if(count <= 0) {
return;
} else if (count == 1) {
first = last = null;
} else {
k.left.right = k.right;
k.right.left = k.left;

if(k == first) {
first = k.right;
} else if( k == last) {
last = k.left;
}
}
count --;
}
}

Answer 13

  不好意思，效果不怎么好。这次看能否好点public class Count3Quit2 {
public static void main(String[] args) {
KidCircle kc = new KidCircle(17);
int countNum = 0;
Kid k = kc.first;
while(kc.count > 1) {
countNum ++;
if(countNum == 3) {
countNum = 0;
kc.delete(k);
}
k = k.right;
}System.out.println(kc.first.id);
}
}class Kid {
int id;
Kid left;
Kid right;
}class KidCircle {
int count = 0;
Kid first, last;KidCircle(int n) {
for(int i=0; i<n; i++) {
add();
}
}void add() {
Kid k = new Kid();
k.id = count;
if(count <= 0) {
first = k;
last = k;
k.left = k;
k.right = k;
} else {
last.right = k;
k.left = last;
k.right = first;
first.left = k;
last = k;
}
count ++;
}void delete(Kid k) {
if(count <= 0) {
return;
} else if (count == 1) {
first = last = null;
} else {
k.left.right = k.right;
k.right.left = k.left;if(k == first) {
first = k.right;
} else if( k == last) {
last = k.left;
}
}
count --;
}
}

Answer 14

import java.util.ArrayList;public class Test
{
    public static int test(int len)
    {
        ArrayList<String> data = new ArrayList<String>();
        for(int i = 0; i <= len - 1; i++)
        {
            data.add(i + "");
        }
        int search = 0;
        for(int i = 0; i < len - 1; i++)
        {
            search += 2;
            search %= data.size();
            System.out.println(data.remove(search));
        }
        return Integer.parseInt(data.get(0).toString());
    }
    
    public static void main(String[] args)
    {
        int result = test(17);        
        System.out.println("final result:" + result);
    }
}

Answer 15

Josephus[] arrays = new Josephus[17];
这句是不是要换成：
Josephus[] arrays = new Josephus[n];

Answer 16

搞数据库的插一腿。。答案为5
create table #tb(a int)
declare @a int=0,@b int=16
while(@a<=@b)
begin
insert into #tb values(@a)
set @a=@a+1
end
drop table #tb
declare @s int=1,@t int=17,@d int=4
while @t>1
begin
delete #tb from #tb a join (select ROW_NUMBER() over (order by(select 1)) as num,a from #tb) b on a.a=b.a
where b.num=@d
set @t=@t-1
set @s=(@s+(17)%@t-1)%@t
if @s=0 begin set @s=@t end
set @d=(@s+3)%@t
if @d=0 begin set @d=@t end
end
select * from #tb

Answer 17

c写的.
int lastpeo(int num)
{
int people[17];//17个人
int in=16;    //退出的16个人.
int i;
int j=0;  //报号0-3
for(i=0;i++;i<16) //17个人
{
people[i]=1;
}
while(in)
{
if(people[num]==1)
{
if(j==3)//退出一个
{
people[num]=0;
j=0;
in--;
}
else//继续报号
{
j++
num++;
}
}
else//没有人.
{
num++;
}
}
for(i=0;i++;i<16)//只剩一个
{
if(people[i]==1)
{
return i;
}
}
}

Answer 18

这个问题都要面向对象耶..cpu不值钱了,霍霍.

Answer 19

我实现的个人感觉最容易理解的一种方法：通过数组实现
public class Ring {

/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从s开始报数，报到d的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的s、d和n，求出所有人的出圈顺序.
*/
public static void main(String[] args) {
//当前所有人
String [] values = {"A","C","G","H","K","L","M","P","Q","B","O","W"};
out(values);
int n = values.length; //当前人数
int s = 3; //开始报数的人
int d = 4; //报到第几个出圈
int flag = -1;
if(d<0){
d = 1;
}
while(n>1){
flag = ((s-1)+d)%n ;
s = flag==0?n:flag;
int sub = flag==0?n-1:flag - 1; //每次出去的人由下标指定
String [] newValues = new String[n-1];
for(int j=0,i=0;j<n;j++){
if(j==sub){
//System.out.println("数据数量["+n+"]下标：values["+sub+"]出"+values[sub]);
continue;
}
newValues[i++] = values[j];
}
values = newValues;
out(values);
n--;
}
System.out.println("最终结果为$ "+values[0]+" $留在圈内");
}
private static void out(String [] args){
StringBuffer sbf = new StringBuffer();
for(int j=0;j<args.length-1;j++){
sbf.append(args[j]+",");
}
sbf.append(args[args.length-1]);
System.out.println(sbf.toString());
}
}

Answer 20

不容易理解，但是最经典（一般书中使用的）
public class Ring_Two { /**
 * @param args
 */
public static void main(String[] args) {
String [] values = {"A","C","G","H","K","L","M","P","Q","B","O","W"};
System.out.println("初始人数：");
out(values);
int n = values.length; //当前人数
int s = 3; //开始报数的人
int d = 4; //报到第几个出圈
int sub = s-1; //记录下标2
int count = 0; //记录出圈的人数
while(count<n){
for(int j=0;j<d;j++){
//System.out.println(values[(sub+j)%n]);
if("o".equals(values[(sub+j)%n])){
sub++;
j--;
}
}
sub = (sub-1+d)%n;
//System.out.println("sub["+sub+"]"+values[sub%n]+"出");
System.out.print(values[sub%n]+"-->");
values[sub]="o";
while(sub<n){
if("o".equals(values[sub%n])){
sub++;
}else{
break;
}
}
count++;
//out(values);
}
}

private static void out(String [] args){
StringBuffer sbf = new StringBuffer();
for(int j=0;j<args.length-1;j++){
sbf.append(args[j]+",");
}
sbf.append(args[args.length-1]);
System.out.println(sbf.toString());
}
}

Answer 21

刚才那个一运行有问题.
int lastpeo(int num)
{
int people[17];//17个人
int in=16;    //退出的16个人.
int i;
int j=0;  //报号0-3
for(i=0;i<17;i++) //17个人
{
people[i]=1;
}
while(in)
{
if(people[num]==1)
{
if(j==3)//退出一个
{
people[num]=0;
j=0;
in--;
}
else//继续报号
{
j++;
num++;
}
}
else//没有人.
{
num++;
}
if(num==17) num=0;
}
for(i=0;i<17;i++) //只剩一个
{
if(people[i]==1)
{
return i;
}
}
return 100;
}

Answer 22

<?php
$arr = array ();
for($i = 0; $i < 3; $i ++) {
$arr [] = $i;
}
$var=0;
for($i=0;$var!=3;$i++){
//echo $i;
if($i%3!=2){
$arr[]=$arr[$i];
}else{
$var++;
echo $arr[$i],',';
if($var%40==0){
echo "<hr>";
}
}
}

Answer 23

#include <stdio.h>
#include <stdlib.h>#define PERSON 30
#define UNLEAVE 15
#define NUM 9int main(int argv, char **argc)
{
int i, j, t = -1;
char person[30];
char a[PERSON] = {0}; for (i = 0; i < UNLEAVE; i++)
{
for (j = 0; j < NUM; j++)
{
while (person[t%PERSON])
{
t++;
}
}person[t%PERSON] = 1;
}
for (i = 0; i < PERSON; i++)
{
if (!PERSON)
{
printf("%d\n", t+1);
}
} return EXIT_SUCCESS;
}

Answer 24

<?php
function test($int) {
$arr = array ();
for($i = 0; $i < $int; $i ++) {
$arr [] = $i;
}
$var = 0;
for($i = 0; $var != $int; $i ++) {
if ($i % 3 != 2) {
$arr [] = $arr [$i];
} else {
$var ++;
echo $arr [$i], ',';
if ($var % 40 == 0) {
echo "<hr>";
}
}
}
echo count ( $arr );
}
test(17);改一下 从发…… 

Answer 25

2楼已经给出，手痒就也写一个，不过没有贯彻封装成员变量的原则，也没有将报数和删除的动作封装到“点”类。对题意的理解是报到3则删除，下一个重新从0开始报。
public class Run {
public static void main(String[] args) {
        Point startPoint = new Point(0, null);
        Point p = startPoint;
for (int i = 1; i < 17; i++) {
p.nextPoint = new Point(i, p);
p = p.nextPoint;
}
p.nextPoint = startPoint;
        p=nextPoint；
int tick = 0;
do {
startPoint = startPoint.nextPoint;// 移到下一点
tick += 1; // 报数
if (tick == 2) {
startPoint.nextPoint = startPoint.nextPoint.nextPoint;// 删除下一点
startPoint = startPoint.nextPoint;// 新点
tick = 0; // 报数为0
}
} while (startPoint.nextPoint != startPoint);
System.out.print(startPoint.number);
}
}
class Point {
int number;
Point nextPoint;
public Point(int i,Point p){
number=i;
nextPoint=p;
}
}

Answer 26

public static int king(int M, int N) {
// 总人数 M ，数到第 N 个排除。
int k = 0;
for (int i = 2; i <= M; i++){
k = (k + N) % i;
}
return ++k;
}以前看到的 一个超NB的写法

Answer 27

呵呵，很好啊，java 的代码写的不错，不过C语言更OK了

Answer 28

public class YSF
{
public static void main(String[] args)
{
int arr[] = {1,2,3,4,5,6,7,8};
int flag = 5,index=0;
for(int i=arr.length;i>0;i--)
{
index =(index+flag-1)%i;
System.out.print(arr[index]+" ");
for(int j=index;j<arr.length-1;j++)
{
arr[j]=arr[j+1];
}
}
System.out.println();
}
}