微信

使用微信服务,更方便

职友集>Java面试题 > java解决约瑟夫问题

java解决约瑟夫问题

2015-05-16 06:30:02 阅读( 357 )

1801人 收藏本页

标签:Java面试题

/约瑟夫问题(丢手帕)
//设编号为1,2,3…n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始
//报数,数到m的那个人出列,他的下一位又从1开始报数,数到m的那个人又出
//列,依次列推,知道所有人出列为止,由此产生一个出对编号的序列
package com;
public class Demo3 {
public static void main(String[] args){
CycLink cyclink=new CycLink();
cyclink.setLen(9);
cyclink.setK(1);
cyclink.setM(1);
cyclink.createLint();
cyclink.show();
cyclink.play();
}
}

class Child{
int no;
Child nextChiled=null;
public Child(int no){
//给一个编号
this.no=no;
}
}
//环形链表
class CycLink{
//先定义一个指向链表第一个小孩的引用
//指向第一个小孩的引用,不能动
Child firstChild=null;
Child temp=null;
int len=0;//表示共有多少个小孩
int k=0;
int m=0;
//设置链表大小
public void setLen(int len){
this.len=len;
}
public void setK(int k){
this.k=k;
}
public void setM(int m){
this.m=m;
}
//开始play
public void play(){
Child temp=this.firstChild;
Child temp2=temp;
//1.先找到开始数数的人
for(int i=1;i<k;i++){
temp=temp.nextChiled;
}
while(this.len!=1){
//2.数m下
for(int j=1;j<m;j++){
temp2=temp;
temp=temp.nextChiled;
}
//找到要出圈的前一个小孩
// Child temp2=temp;
// while(temp2.nextChiled!=temp){
// temp2=temp2.nextChiled;
// }
//3.将数到m的小孩,退出圈
temp2.nextChiled=temp.nextChiled;
//让temp指向下一个数数的小孩
temp=temp.nextChiled;
this.len–;
}
//最后一个小孩
System.out.println(“最后是”+temp.no);
}

// 初始化环形链表
public void createLint(){
for(int i=1; i<=len; i++){
//创建第一个小孩
if(i==1){
Child ch=new Child(i);
this.firstChild=ch;
this.temp=ch;
}
else if(i>1 & &i<len){
Child ch=new Child(i);
temp.nextChiled=ch;
temp=ch;
}
else{
Child ch=new Child(i);
temp.nextChiled=ch;
temp=ch;
temp.nextChiled=this.firstChild;
}
}
}

public void show(){
Child temp=this.firstChild;
do{
System.out.print(temp.no+” “);
temp=temp.nextChiled;
}while(temp!=this.firstChild);
}
}

来自IT公司面试手册

下一篇:java开发工程师笔试题

上一篇:newinstance()和new有什么区别?

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题