用环形链表解决约瑟夫问题
**
一、约瑟夫问题的描述
** ➢Josephu 问题 Josephu问题为:设编号为1, 2, … n的n个人围坐一圈，约定编号为k (1<=k<=n) 的人 从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出 列，依次类推，直到所有人出列为止，由此产生个出 队编号的序列。 ➢提示 用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结 点的单循环链表， 然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被刑除结点 的下一个结点又从1开始计数，直到最后一个结 点从链表中删除算法结束。
二、约瑟夫问题的分析
1、创建环形链表的思路图解 构成一个单项的环形链表思路： （1）先创建第一个节点，让first指向该节点，并形成环状 （2）后面当我们每创建一个新节点，就把该节点，加入到已有的环形链表中即可 遍历环形链表 （1）先让一个辅助指针（变量）curBoy，指向first节点 （2）然后通过一个while循环遍历该换装链表即可curboy.next = first（curboy的下一个节点指向第一个first节点，说明curboy已经遍历到了最后一个节点）程序结束 代码如下：
//添加小孩节点，构成一个环形的链表
public void addBoy(int num){
//num做一个校验
if(num <1){
System.out.println("num的值不正确");
return ;
}
Boy curBoy = null; //辅助指针，帮助构建环形链表
//使用for来创建我们的环形链表
for(int i =1 ; i<=num;i++){
Boy boy = new Boy(i);
if(i==1){
first=boy; //获取 boy的第一个节点所以first为首节点
first.setBoy(first); //构成环形！
curBoy = first; //用curBoy 指向第一个节点
}else{
curBoy.setBoy(boy); //指向下一个节点boy=1
//System.out.printf("curBoy:%d
",curBoy.getId());
boy.setBoy(first); //指回原来的首节点 first
// System.out.printf("boy:%d
",boy.getId());
curBoy = boy ; //后移
// System.out.printf("curbBoy:%d
",curBoy.getId());
}
}
}
2、约瑟夫问题-小孩出圈的思路分析图
根据用户的输入，生成一一个小孩出圈的顺序
n=5,即有5个人
k=1,从第一个人开始报数
m=2,数2下
1.需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点.
补充:小孩报数前，先让first和helper移动k- 1次
2.当小孩报题时，i让first 和helper指针同时的移动m -1次
3.这时就可以将first指向的小孩节点出圈
first= first .next
helper.next= first
原来first指向的节点就没有任何引用，就会被回收
出圈的顺序
2-24->1-35->3
代码如下：
//小孩出圈
/**
*
* @param soid 定义有从哪个小孩先开始
* @param soNmae 定义每次数几下
* @param sum 定义总共有多少个小孩
*/
public void contBoy(int soid , int soName,int sum){
//判断输入的数据是否合法
if(first == null || soid<1 || soid>sum){
System.out.println("输入的数据有误，请你重新输入");
return ;
}
Boy helpboy = first;
//先将helpbot循环至first的前一位 也就环状量表的最火一位
while(true){
if(helpboy.getBoy() == first){
break ;
}
helpboy = helpboy.getBoy();
}
//小孩子报数前需要先让 first 和 helpBoy移动m-1位
for(int i=0;i<soid -1; i ++ ){
first=first.getBoy(); //往前移动一位
helpboy=helpboy.getBoy();
}
//当小孩报数时，让first 和helpBoy指针同时一地哦那个m-1次，然后出圈
//这里是一个循环操作，知道圈中只有一个节点
int i=0;
while(true){
if(helpboy == first){
//因为最后一个一个出圈的helpboy 和first都指向它
break ;
}
//让fist和helpboy同时移动soName-1，
for(int j =0;j< soName -1;j++){
first=first.getBoy(); //往前移动一位
helpboy=helpboy.getBoy();
}//这时first指向的节点就是小孩出圈的节点
System.out.printf("第%d个出圈的小孩为：%d
",++i,first.getId());
//让小孩出圈
first = first.getBoy();
helpboy.setBoy(first);
}
System.out.printf("最后出圈的小孩是：%d
",first.getId());
}
三、代码实现
创建一个Boy的类
class Boy{
private int id;
private Boy boy;
public Boy(int id) {
super();
this.id = id;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public Boy getBoy() {
return boy;
}
public void setBoy(Boy boy) {
this.boy = boy;
}
}
创建一个实现类JuseptuWenti类用来实现方法
class JuseptuWenti{
//创建一个first节点，当前没有编号作为头
private Boy first = null;
//添加小孩节点，构成一个环形的链表
public void addBoy(int num){
//num做一个校验
if(num <1){
System.out.println("num的值不正确");
return ;
}
Boy curBoy = null; //辅助指针，帮助构建环形链表
//使用for来创建我们的环形链表
for(int i =1 ; i<=num;i++){
Boy boy = new Boy(i);
if(i==1){
first=boy; //获取 boy的第一个节点所以first为首节点
first.setBoy(first); //构成环形！
curBoy = first; //用curBoy 指向第一个节点
}else{
curBoy.setBoy(boy); //指向下一个节点boy=1
//System.out.printf("curBoy:%d
",curBoy.getId());
boy.setBoy(first); //指回原来的首节点 first
// System.out.printf("boy:%d
",boy.getId());
curBoy = boy ; //后移
// System.out.printf("curbBoy:%d
",curBoy.getId());
}
}
}
//小孩出圈
/**
*
* @param soid 定义有从哪个小孩先开始
* @param soNmae 定义每次数几下
* @param sum 定义总共有多少个小孩
*/
public void contBoy(int soid , int soName,int sum){
//判断输入的数据是否合法
if(first == null || soid<1 || soid>sum){
System.out.println("输入的数据有误，请你重新输入");
return ;
}
Boy helpboy = first;
//先将helpbot循环至first的前一位 也就环状量表的最火一位
while(true){
if(helpboy.getBoy() == first){
break ;
}
helpboy = helpboy.getBoy();
}
//小孩子报数前需要先让 first 和 helpBoy移动m-1位
for(int i=0;i<soid -1; i ++ ){
first=first.getBoy(); //往前移动一位
helpboy=helpboy.getBoy();
}
//当小孩报数时，让first 和helpBoy指针同时一地哦那个m-1次，然后出圈
//这里是一个循环操作，知道圈中只有一个节点
int i=0;
while(true){
if(helpboy == first){
//因为最后一个一个出圈的helpboy 和first都指向它
break ;
}
//让fist和helpboy同时移动soName-1，
for(int j =0;j< soName -1;j++){
first=first.getBoy(); //往前移动一位
helpboy=helpboy.getBoy();
}//这时first指向的节点就是小孩出圈的节点
System.out.printf("第%d个出圈的小孩为：%d
",++i,first.getId());
//让小孩出圈
first = first.getBoy();
helpboy.setBoy(first);
}
System.out.printf("最后出圈的小孩是：%d
",first.getId());
}
//遍历当前的节点
public void list(){
if(first == null ){
System.out.println("当前节点为空节点");
return ;
}
//提供辅助指针遍历
Boy boy = first;
int i= 0;
while(true){
//直接输出小孩的id
System.out.printf("小孩的id:%d
",boy.getId());
//判断循环是否结束
if(boy.getBoy() == first){
//说明遍历完毕
break ;
}
boy = boy.getBoy(); // 让boy后移
}
}
}
最后在mian函数中运行
public class Testjuseptu {
public static void main(String[] args) {
JuseptuWenti juseptuwenti = new JuseptuWenti();
juseptuwenti.addBoy(5);
juseptuwenti.list();
juseptuwenti.contBoy(1, 2, 5);
}
}
上一篇：
多线程四大经典案例
下一篇：
学习笔记_关系运算符