Java采用循环链表结构求解约瑟夫问题
本文实例讲述了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); } }