问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;
他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列
求被踢出的的顺序。
第一种解决方案
/*约瑟夫环的解决方案
* 变量解释
* 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);
}
}
第二种解决方案
/*约瑟夫环的解决方案
* 变量解释
* n是总人数
* m是报数间距即报道第几个停
* S是第一个开始报数的位置
* 这个程序中有个构造方法test,有三个参数意思如下
* arg1赋值给n,arg2赋值给m,arg3赋值给s
* 还有两个方法run method
***************************************
*/
第二种方案的思想是直接定位要踢出的人是谁!!就是根据第一个人报数的人找到踢出的人
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);
}
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]
分享到:
相关推荐
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
已知n个人(不妨分别以编号1,2,3,…,n 代表)围坐在一张圆桌周围,从编号为 k 的人开始,从1开始顺时针报数1, 2, 3, ...,顺时针数到m 的那个人,出列并输出。然后从出列的下一个人开始,从1开始继续顺时针报数...
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 ...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
:设编号为1,2,…,n的n个人围坐一圈,约定编号为k(1≤k≤n)的人从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。...
问题描述:已经n个人(以编号1,2,3,…,n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部...
约瑟夫环问题描述:编号为1,2,…,n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将...
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k 的人开始逆时针报数,1, 2, 3, ...,数到 ...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 ...
约瑟夫问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部...
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到...
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决...
约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到...
* 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k(1,2,3...n)的人开始报数,数到m(1,2,3...)的那个人出列; * 他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,...
8. 【题目】约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又...
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律...
已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类...