問題:已知n我的(以編號1,2,3...n分別表示)圍坐在一張圓桌周圍。從編號爲k的人開始報數,數到m的那我的出列;
他的下一我的又從1開始報數,數到m的那我的又出列;依此規律重複下去,直到圓桌周圍的人所有出列
求被踢出的的順序。 php
第一種解決方案 java
/*約瑟夫環的解決方案
* 變量解釋
* n是總人數
* m是報數間距即報道第幾個停
* S是第一個開始報數的位置
* 這個程序中有個構造方法test,有三個參數意思以下
* arg1賦值給n,arg2賦值給m,arg3賦值給s
* 還有方法run
***************************************
English name apanly
chinese name Guo Wei
程序可能不是很完美,若是您發現了更好的方法複製給我一份源程序!!謝謝!!
My Email :apanly@163.com
My MSN :apanly@msn.cn
My QQ:364054110
*/
package yuesefu;
import java.util.*;
public class yuesefuclass {
public int n,m,s;
public int flag,removeflag,number=0;
public String result="";
ArrayList<String> person=new ArrayList<String>();
public yuesefuclass(int arg1,int arg2,int arg3){
n=arg1;
m=arg2;
s=arg3;
flag=s-1;
}
public void run(){
for (int i=0;i<n;i++) { //在LIST中添加N我的
person.add(i, String.valueOf(i+1));
}
while(person.size()>1){
if(flag+1<=person.size()-1)//用於判斷下一個是否已經越界,若是沒有接着向下數數,而且讓標識FLAG+1就是下一我的報數{
number=number+1;
removeflag=flag;
flag=flag+1;
}else//若是越界,接着向下數數可是讓標識FLAG=0就是有從第一我的開始報數,{
number=number+1;
removeflag=flag;
flag=0 ;
}
if(number==m)//若是報數的計數器達到了M,在LIST中刪除這我的,而且將FLAG的位置微調{
if(flag>=1){
flag=flag-1;
}else{
flag=0;
}
result=result+person.get(removeflag)+"-->";
person.remove(removeflag);
number=0;
}
}
result=result+person.get(0);
}
public static void main(String args[]){
yuesefuclass yuesefu =new yuesefuclass(60000,12,3); //進行實例化 ,三個參數分別是n,m,s
yuesefu.run(); //輸出結果
System.out.println(yuesefu.result);
}
} this
第二種解決方案 開發
/*約瑟夫環的解決方案
* 變量解釋
* n是總人數
* m是報數間距即報道第幾個停
* S是第一個開始報數的位置
* 這個程序中有個構造方法test,有三個參數意思以下
* arg1賦值給n,arg2賦值給m,arg3賦值給s
* 還有兩個方法run method
***************************************
*/ rem
第二種方案的思想是直接定位要踢出的人是誰!!就是根據第一我的報數的人找到踢出的人
package yuesefu;
import java.util.*;
//import javax.swing.*;
public class yuesefulei {
public int n,m,s;
public int step,flag,removeflag,rightstep;
public String result="";
public ArrayList<String> person= new ArrayList<String>();
public yuesefulei(int arg1,int arg2,int arg3){
this.n=arg1;
this.m=arg2;
this.s=arg3;
}
/********方法run**************************/
public void run(){
this.flag=s-1;
for(int i=0;i<this.n;i++){
this.person.add(i,String.valueOf(i+1));
}
if (this.m>this.n){
while(this.person.size()>1){
this.step=this.m%this.person.size();
this.method();
}
}else{
while(this.person.size()>1){
if(this.m<=this.person.size()){
this.step=this.m;
}
else{
this.step=this.m%this.person.size();
}
this.method();
}
}
this.result=this.result+this.person.get(0);
//System.out.print(this.person.get(0));
}
/*************方法method*********************/
public void method(){
this.rightstep=this.person.size()-this.flag;
/************************************/
if(this.rightstep>=this.step){
if(this.flag+this.step==0){
if (person.size()==this.rightstep){
this.removeflag=this.rightstep-1;
}else{
this.removeflag=1;
}
}else{
this.removeflag=this.flag+this.step-1;
}
}
else{
this.removeflag=this.step-this.rightstep-1;
}
/************************/
if(this.removeflag+1<=this.person.size()-1){
this.flag=this.removeflag;
}
else{
this.flag=0;
}
//System.out.print(this.person.get(this.removeflag));
//System.out.print("-->");
this.result=this.result+this.person.get(this.removeflag)+"-->";
this.person.remove(this.removeflag);
} get
public static void main (String args[]){
yuesefulei yuesefu =new yuesefulei(60000,12,3);
yuesefu.run();
System.out.println(yuesefu.result);
}
}
原帖地址:http://www.phpjava.org/forum.php?mod=viewthread&tid=428&extra=社區
本文來自: PJDN--php&Java論壇|技術交流社區,打造中國php&java開發者社區[www.phpjava.org]class