Joseph Problem With Passwords In Java

问题描述：

编号为1，2，......，n的n个人（每个人的信息有编号、姓名和密码三项）按照顺时针方向围坐一圈，

每个人有且只有一个密码（正整数，密码用随机方式赋值，范围1-15）。一开始任选一个正整数作为报数

上限值，从第一个人开始顺时针方向自1开始报数，报到m时停止报数。报m 的人出列，将他的密码作为新

的m 值，从他在顺时针方向的下一个人开始重新报数，如此下去，直到所有人全部出队为止。设计一个程

序来求出队顺序。

分析：

为解决约瑟夫问题而设计的单向循环链表,应实现如下功能：
1 添加元素
2 拥有指示当前选中元素的游标
3 游标可循环访问链表中各元素
4 可将游标向前移动指定步数
5 可删除当前游标所指定的元素
*输入：每个人的信息；起始m值
*输出：出队的人信息。

步骤：

1 确定数据类型
2 建立链表
3 实现循环方法
4 输出结果

 1 import  java.util.*;

 2 import  java.io.*;

 3

 4 public class JosephProb {

 5     static int N;

 6

 7     public static void main(String[] args) throws IOException{

 8         CircleLinkList list=new CircleLinkList();

 9         Scanner sc=new Scanner(System.in);

10         System.out.print("请输入参加的总人数N ：");

11         N=sc.nextInt();

12

13         int i,data[][]=new int [N][2];

14         String name[]=new String[N];

15         System.out.println("请输入每个人的编号和姓名：");

16         for( i=0;i<N;i++){

17             data[i][0]=sc.nextInt();

18             name[i]=sc.nextLine();

19         }

20         System.out.print("请输入初始密码值(正整数)：");

21         int m=sc.nextInt();

22

23         //生成密码

24         List<Integer> l = new ArrayList<Integer>();

25         while(l.size()<N){

26             int j = (int)(Math.random()*15+1);

27                 l.add(j);

28         }

29         //初始化

30         for(i=0;i<N;i++){

31             data[i][1]=l.get(i);

32             list.Init(data[i][0],name[i],data[i][1]);

33         }

34         //出列

35         list.Operation(m);

36         System.out.println("Over!");

37     }

38 }

39 class Person{

40     int number;

41     int password;

42     String names;

43     Person next;

44     public Person (int number,String names,int password){

45         this.number=number;

46         this.names=names;

47         this.password=password;

48         this.next=null;

49     }

50 }

51 class CircleLinkList {

52     Person head;//头结点

53     Person current;

54

55     public boolean isEmpty(){ return head==null; }

56

57     public void Init(int number,String names,int password) {

58         Person tmp=new Person(number,names,password);

59         if(this.isEmpty()){

60             head=tmp;

61             current=head;

62         }

63         else{

64             current.next=tmp;

65             current=tmp;

66         }

67         //最后一个节点的next指向第一个

68         current.next = head;

69     }

70

71     public void Operation(int m){

72         System.out.println("出列人信息：[编号 姓名 密码]");

73         while(current!=current.next){

74             for(int i=1;i<m;i++){    //从1开始报数，到m时停止报数

75                 current=current.next;//指针移动到出列的前一个节点

76             }

77             m=current.next.password;//修改密码为出列人的密码

78             //输出-出队人的信息

79             System.out.print("["+current.next.number+" "+current.next.names+" "+current.next.password+"]\n");

80             current.next=current.next.next;//删除

81         }

82         System.out.println();

83         System.out.println("最后剩余的是  ["+current.number+" "+current.names+" "+current.password+" ]");

84     }

85 }

补充：

可以将出队的人用队列进行存储，并输出。

实现就是新建一个QueueList，添加Insert（）输出Dequeue（）即可。

代码略。

巴特西

Joseph Problem With Passwords In Java

问题描述：

分析：

步骤：

补充：

最新文章

热门文章