提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

Java采用循环链表结构求解约瑟夫问题

JAVA链表循环 问题 结构 采用 求解 约瑟夫
2023-06-13 09:15:32 时间

本文实例讲述了Java采用循环链表结构求解约瑟夫问题的方法。分享给大家供大家参考。具体分析如下：

这是第一次java考试的试题，对于没看过链表的同学来说就不会做，现在回头看看，还真不难。

约瑟夫问题：
有n个人，其编号分别为1，2，3，…，n。这n个人按顺序排成一个圈。现在给定s和d，从第s个人开始从1依次报数，数到d的人出列，然后又从下一个人开始又从1开始依次报数，数到d的人又出列，如此循环，直到最后所有人出列为止。要求定义一个节点类，采用循环链表结构求解约瑟夫问题。

以下java版的答案：

复制代码代码如下:
importjava.util.Scanner;
publicclassLinkNode{             //单向链表的节点类
   publicintdata;                //存放节点值
   publicLinkNodenext;           //存放节点值的引用
   
   publicLinkNode(intk){        //构造方法，值为k的节点
       data=k;
       next=null;
   }
}
 classJosephus{
   publicstaticvoidprintJosephus(intn,ints,intd){       
       inti=1;                   //创建长为n的循环列表
       LinkNodeq,tail;
        
       LinkNodehead=newLinkNode(i);
       head.next=head;
       tail=head;            //第一个节点，尾巴和头在一起
       
       while(i<n){
           i++;
           q=newLinkNode(i);   //增加一个新节点
           q.next=head;       //节点的引用指向头
           tail.next=q;           //最后一个元素的引用指向了q
           tail=q;             //那么最后一个元素就是q
       }

       intj=0;              //从s开始报数，依次输出出列人的编号
       LinkNodep=head;     //计数起点
       while(j<s-1){
           j++;
           p=p.next;
       }
       while(p.next!=p){
           j=1;
           while(j<d-1)  //计数的起始点
           {
               j++;
               p=p.next;
           }       
           System.out.print(p.next.data+""); //输出出列的节点号
           p.next=p.next.next;
           p=p.next;                               //不断指向下一个节点           
       }
       System.out.print(p.data);
   }

   publicstaticvoidmain(String[]args){
       Scannerinput=newScanner(System.in);
       intn=input.nextInt();
       inta=input.nextInt();
       intb=input.nextInt();
       Josephus.printJosephus(n,a,b);
   }
}

希望本文所述对大家的Java程序设计有所帮助。

相关文章