约瑟夫问题，也是被称为丢手绢问题。利用c++或者java的单向环形链表能够较好的解决，但肯定不是最简单的方法。就仅仅是我在学习java的过程中的一个小的作业题。
问题的来源，据说著名犹太历史学家 josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，一开始要站在什么地方才能避免被处决？josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
具体的要求参见度娘：约瑟夫问题
public class demo4 { public static void main(string[] args) { // todo auto-generated method stub cyclink cyclink = new cyclink(); int len=41; int k=1; int m=3; cyclink.setlen(len); cyclink.creatlink(); cyclink.show(); cyclink.setk(k); cyclink.setm(m); cyclink.playgame(); }}class node{ int no; node nextnode = null; //节点的构造函数 public node(int no) { //给一个编号 this.no = no; }}//环形链表class cyclink{ //先定义一个指向链表第一个节点的引用 //指向第一个节点的引用不能动 node firstnode = null;//没有新开辟空间，它在纸上谈兵！！！！ node tempnode =null;//跑龙套的选手！！！很重要！！！！（纸上谈兵） int len = 0;//表示共有多少个节点(node) int k =0;//表示要从第k个节点开始计数 int m =0;//表示每数到m个节点要被删除 //设置链表的大小（长度） public void setlen(int len) { this.len = len; } //设置从第k个人开始计数 public void setk(int k) { this.k=k; } //设置从第m个人开始计数 public void setm(int m) { this.m=m; } //初始化环形链表 public void creatlink() { for(int i=1;i<= len ;i++) { if(i==1) { //创建第一个节点 node ch=new node(i);//ch可不是纸上谈兵，实实在在的开辟了空间 this.firstnode = ch;//“纸上”的firstnode指向了有实际空间的ch this.tempnode = ch;//“纸上”的tempnode指向了有实际空间的ch } else //其余节点（不是第一个头结点） { if(i==len)//（如果要创建最后一个节点） { //创建最后一个节点 node ch=new node(i);//创建（实际开辟）最后节点，以第二个为例 tempnode.nextnode = ch;//"纸上"的tempnode.nextnode指向2节点 tempnode = ch;//在“纸上”变更龙套选手 tempnode.nextnode = this.firstnode;//纯粹纸上谈兵，龙套（最后节点）的下个节点指回初始节点 } else { //继续创建一个节点 node ch=new node(i);//创建（实际开辟）下一个节点，以第二个为例 tempnode.nextnode = ch;//"纸上"的tempnode.nextnode指向2节点 tempnode = ch;//在“纸上”变更龙套选手 } } } } //开始丢手帕游戏 public void playgame() { //1、找到第k个节点 node temp1=null; node temp2=null; temp1 = firstnode; for(int i=1; i<k; i++) { temp1=temp1.nextnode; } int cn=1;//删除的顺序标志 while(len!=1) { //2、从第1步中找到的k人开始计数，找第m-1个用户（方便第3步修改其下个节点的指向） for(int j=1; j<m-1; j++) { temp1=temp1.nextnode; } //3、将第2步中找到的用户修改其下个节点的指向 temp2=temp1.nextnode;//temp2就是要被删去的节点 system.out.println("第"+cn+"个删除的节点编号："+ temp2.no); temp1.nextnode=temp2.nextnode; temp1 = temp1.nextnode; cn++; len--; } //4、显示最后剩下的节点 system.out.println("最后剩下的节点是："+temp1.no); } //打印该循环链表 public void show() { //定义个龙套选手 node temp=this.firstnode;//将“龙套”选手的“帽子”扣在第一个节点上 system.out.print("初始节点编号： "); do { system.out.print(temp.no+" "); temp = temp.nextnode; }while(temp!=this.firstnode); system.out.println(" "); }}
相关推荐：
php-java-bridge使用笔记，php-java-bridge
java学习随笔--- 捣蛋vector，java随笔---vector
以上就是经典问题约瑟夫问题的java实现的详细内容。