Josephu(约瑟夫)问题解析
2018-11-20 03:19:11来源:博客园 阅读 ()
Josephu问题为:
设置编号为1,2,3,......n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1看是报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人出列,以此类推,直到所有人出列为止,由此产生一个出队编号的序列。
提示:用有个不带头的循环链表来处理Josephu问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。
代码:
public class Demo{ public static void main(String[] args){ CycLink cyclink=new CycLink(); cyclink.setLen(5); cycLink.createLink(); cyclink.show(); } } //小孩 class Child{ //编号 int no; //结点 Child nextChild=null; public Child(int no){ //给编号 this.no=no; } } //环形链表 class CycLink{ //先定义一个指向链表第一个小孩的引用 //指定第一个小孩的引用不能动,不然以后找不到他了 Child firstChild=null; //定义一个游标 Child temp=null; //表示共有几个小孩 int len=0; //设置链表大小 public void setLen(int len){ this.len=len; } //初始化环形链表 public void createLink(){ for(int i=1;i<=len;i++){ if(i==1){ //创建第一个小孩 Child ch=new Child(i); this.firstChild=ch; this.temp=ch; }else{ //创建最后一个小孩 if(i==len){ Child ch=new Child(i); temp.nextChild=ch; temp=ch; temp.nextChild=this.firstChild; }else{ //继续创建小孩 Child ch=new Child(i); //连接,搭桥 temp.nextChild=ch; //temp向前走一步,指向刚刚进来的孩子 temp=ch; } } } } //打印该环形链表 public void show(){ Child temp=this.firstChild; do{ System.out.println(temp.no); temp=temp.nextChild; }while(temp!=this.fistChild); } }
优化:
代码:
public class Demo{ public static void main(String[] args){ CycLink cyclink=new CycLink(); cyclink.setLen(50); cycLink.createLink(); cycLink.setK(2); cycLink.setM(3); cyclink.show(); cyclink.play(); } } //小孩 class Child{ //编号 int no; //结点 Child nextChild=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; //设置m public void setM(int m){ this.m=m; } //设置链表大小 public void setLen(int len){ this.len=len; } //设置从第几个人开始数数 public void setK(int k){ this.k=k; } //开始play public void play(){ Child temp=this.fistChild; //1.先找到开始数数的人 //int i=1;i<k;因为自己也要数一下,所以i不能为k for(int i=1;i<k;i++){ temp=temp.nexChild; } while(this.len!=1){ //2.数m下 for(int j=1;j<m;j++){ temp=temp.nextChild; } //找到要出圈的前一个小孩,有待优化 Child temp2=temp; while(temp2.nextChild!=temp){ temp2=temp2.nextChild; } //3.将数到m的小孩,退出圈 temp2.nextChild=temp.nextChild; //让temp指向数数的小孩 temp=temp.nextChild; this.len--; } //最后一个小孩(验证) System.out.println(temp.no); } //初始化环形链表 public void createLink(){ for(int i=1;i<=len;i++){ if(i==1){ //创建第一个小孩 Child ch=new Child(i); this.firstChild=ch; this.temp=ch; }else{ //创建最后一个小孩 if(i==len){ Child ch=new Child(i); temp.nextChild=ch; temp=ch; temp.nextChild=this.firstChild; }else{ //继续创建小孩 Child ch=new Child(i); //连接,搭桥 temp.nextChild=ch; //temp向前走一步,指向刚刚进来的孩子 temp=ch; } } } } //打印该环形链表 public void show(){ Child temp=this.firstChild; do{ System.out.println(temp.no); temp=temp.nextChild; }while(temp!=this.fistChild); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 面试的时候按照这个套路回答 Java GC 的相关问题一定能过 2020-06-08
- 我可真是醉了,一个SpringBoot居然问了我30个问题 2020-06-08
- Mybaties简单实例测试及注意问题 2020-06-07
- java对象指向问题 2020-06-07
- 解决IDEA Maven下载依赖包速度慢问题 2020-06-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash