求解(约瑟夫问题)

Question

求解(约瑟夫问题)   :12个人围成一圈.从1号开始报号,凡是数到5的人就走出圈子(出局).然后继续报号.试问最后一个出局的人是那一个
                                                                                                                此程序是出自一本书上的试题,请大家做答????????????????

Answer 1

//m个人,每数到n出局
public static void out(int m,int n){
boolean[] people=new boolean[m];
int outCnt=0;
int index=0;
int tempCnt=1;
while(outCnt<m){
index=(index+1)%m;
if(!people[index]){
tempCnt=tempCnt+1;
if(tempCnt==n){
people[index]=true;
System.out.println("#"+(index+1)+" out");
outCnt++;
tempCnt=0;
}
}
}
}

Answer 2

我先注明:源程序是北京尚学堂科技马士兵老师的...教程里有,我转载...
我只是转载(省得被高人骂我偷....)
-------------------------------------------------------------
//数三退一 方法2 典型的约瑟夫环问题
public class count3quit2 
{
public static void main(String[] args) 
{
KidCircle kc = new KidCircle(500);
int countNum = 0;
Kid k = kc.firstKid;
//kc.count;
while(kc.count > 1)
{
countNum++;
if(countNum==3)
{
countNum = 0;
kc.delete(k);
}
k = k.rightKid;
}
System.out.println(kc.firstKid.id);
}
}class Kid
{
int id;
Kid leftKid;
Kid rightKid;
}class KidCircle
{
int count = 0;//圈内的人数,刚开始的圈默认是0
Kid firstKid,lastKid;//开头的小孩和结束的小孩

KidCircle(int n)//构造函数,构造一个指定人数的手拉手的圈子
{
for(int i = 0; i<n; i++)
add();//调用指定次数的add方法
} void add()//向圈内添加小孩的add方法
{
Kid k = new Kid();
k.id = count;//添加的小孩是第几个小孩,添加在哪里?
  if(count<=0)//表明圈内一个小孩都没有
{
  firstKid = k;
  lastKid = k;
  k.leftKid = k;
  k.rightKid = k;
}
else
{
lastKid.rightKid = k;//最后一个小孩的右边是要加入的当前的小孩
k.leftKid = lastKid;//当前要加入的小孩的左手是最后一个小孩
k.rightKid = firstKid;//当前要加入的小孩的的右手是第一个小孩
firstKid.leftKid = k;//第一个小孩的左手是当前要加入的小孩
lastKid = k;//最后一个小孩成为当前要加入的小孩
}
count++;
} void delete(Kid k)//退出一个小孩的delete方法
{//双向回环链表 约瑟夫环问题
if(count <= 0)
{
return;
}
else if(count == 1)
{
firstKid = lastKid = null;
}
else
{
k.leftKid.rightKid = k.rightKid;//?
//lastKid.rightKid = firstKid.leftKid
k.rightKid.leftKid = k.leftKid;//? if(k == firstKid)
{
firstKid = k.rightKid;
}
else if(k == lastKid)
{
lastKid = k.leftKid;
}
}
count--;
}

}

Answer 3

int m;//total person count
int x//the x-th person is to be killedreturn ((m-1)*x+1)%m;that's the last left

Answer 4

能不能对这个程序
//m个人,每数到n出局
public static void out(int m,int n){
boolean[] people=new boolean[m];
int outCnt=0;
int index=0;
int tempCnt=1;
while(outCnt<m){
index=(index+1)%m;
if(!people[index]){
tempCnt=tempCnt+1;
if(tempCnt==n){
people[index]=true;
System.out.println("#"+(index+1)+" out");
outCnt++;
tempCnt=0;
}
}
}
做一个解释

Answer 5

public class run{
int boy_num=12;
newlist nl=new newlist(boy_num);
int way=5;
    public run(){
     for(int i=0;i<boy_num;i++){
       for(int j=0;j<way;j++){
         nl.next();
     }
     nl.gandiao();
      }
   }
     public static void main(String [] ars){
     new run();
}
}
class newlist{
int[] boys;
int num;
int location;
public newlist(int a){
location=-1;
num=a;
boys=new int[num];
for(int i=0;i<num;i++)
   boys[i]=1;
}
public void next(){
   if(location==(boys.length-1)){
      location=0;
      if(boys[location]==0){
     next();
   }
   }else {location++;
     if(boys[location]==0){
     next();
     }
    }
}
public void gandiao(){
      boys[location]=0;
      System.out.println("我挂了，我市"+(location+1)+"号");
    //  for(int i=0;i<12;i++)System.out.print(boys[i]+",");
     // System.out.println("");
}
}
写的很简单 希望有帮助

Answer 6

参看http://community.csdn.net/Expert/topic/5550/5550473.xml?temp=.3700983