Rumah >Java >javaTutorial >经典问题约瑟夫问题的Java实现
最近比较有时间啦,有时间搞下java,个人觉得学这门语言语法太多啦,不一一去学习啦,心血来潮,挂了个struct2的源代码,一入深似海啊,看得我天花缭乱,从最简单的开始吧。
约瑟夫问题,也是被称为丢手绢问题。利用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
Atas ialah kandungan terperinci 经典问题约瑟夫问题的Java实现. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!