//约瑟夫问题
package com.ym;
public class Demo3 {
public static void main(String[] args) {
// TODO Auto-generated method stub
CycLink c =new CycLink();
c.setNum(5);
c.createLink();
c.setK(2);
c.setM(2);
c.play();
}
}
class Node
{
int no;
Node nextNo= null;
public Node(int no)
{
//编号
this.no=no;
}
}
class CycLink
{
Node first=null; //第一个,不能动
Node temp=null; //游标
int num=0; //结点个数
int k=0;
int m=0;
//设置结点个数
public void setNum(int num)
{
this.num=num;
}
//设置 才第几个开始
public void setK(int k)
{
this.k=k;
}
//设置 数到几
public void setM(int m)
{
this.m=m;
}
//开始游戏
public void play()
{
Node temp1=this.first;
//找到第k个
for(int i=1;i<k;i++)
{
temp1=temp1.nextNo;
}
//数m下,找到出圈的前一个结点
while(this.num!=1)
{
for(int j=1;j<m;j++)
{
temp1=temp1.nextNo;
}
Node temp2=new Node(temp1.no);
temp2.nextNo=temp1.nextNo;
while(temp2.nextNo!=temp1)
{
temp2=temp2.nextNo;
}
temp2.nextNo=temp1.nextNo;
temp1=temp1.nextNo;
this.num--;
}
System.out.print(temp.no);
}
//初始化链表
public void createLink()
{
for(int i=1;i<=num;i++)
{
if(i==1)
{
Node no= new Node(i);
this.first=no;
this.temp=no;
}
else if(i==num)
{
Node no= new Node(i);
this.temp.nextNo=no;
this.temp=no;
this.temp=this.first;
}
else
{
Node no= new Node(i);
this.temp.nextNo=no;
this.temp=no;
}
}
}
public void showCyc()
{
Node temp=this.first;
for(int i=1;i<=num;i++)
{
System.out.print(temp.no+" ");
temp=temp.nextNo;
}
}
}
72行总是提示空指针异常
------解决思路----------------------
//初始化链表
public void createLink()
{
for(int i=1;i<=num;i++)
{
if(i==1)
{
Node no= new Node(i);
this.first=no;
this.temp=no;
}
else if(i==num)
{
Node no= new Node(i);
this.temp.nextNo=no;
this.temp=no;
this.temp=this.first;//没有把最后一个点的nextNo赋值对
}
else
{
Node no= new Node(i);
this.temp.nextNo=no;
this.temp=no;
}
}
}