约瑟夫问题-使用单链表进行一圈人报数

algorithm

问题:人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,处刑下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

翻译过来就是,编号1…n的n个人围成一个环,约定编号为k的人开始报数,数到m的人出列,他的下一位又开始从1报数…以此类推。输出出队编号。

(设定1<= k <=m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package com.youdef.DataStructure.linkedlist;
/*
约瑟夫单向环形链表

1. 有n个节点的单循环链表
由第k节点开始计数m,删除对应的
从被删除结点的下一个节点从1开始计数
直到最后一个结点被删除。
*/
public class JosephuCircle {
public static void main(String[] args) {
CircleSingleLinkedList csl = new CircleSingleLinkedList();

csl.addBoy(14); //添加14个小孩
csl.showBoy();

//测试小孩出圈
csl.countBoy(10,7, 14);
}
}


/*
first
boy
curBoy 辅助指针用于遍历 从指向first开始
*///创建单向环形链表
class CircleSingleLinkedList {
//first结点,当前没编号
private Boy first = null;

//创建nums个结点
public void addBoy(int nums){
if (nums < 1){ //插入的数值校验
System.out.println("nums数值不正确");
return;
}
//辅助指针,帮助构建环形链表,辅助指针curBody始终指向最后
Boy curBoy = null;
for (int i=1; i<=nums; i++){
Boy boy = new Boy(i);
if (i==1){ //第一个小孩节点的话
first = boy;
first.setNext(first); //zhe 构成环!!
curBoy = first; //辅助指针 指向第一个(这里还是初始化阶段)
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy; //
}
}
}

//遍历环形列表,打印
public void showBoy(){
if (first == null){
System.out.println("没有任何~~.");
return;
}
Boy curBody = first;
while (true){
System.out.printf("小孩编号 %d \n",curBody.getNo());
if (curBody.getNext() == first){
break; //遍历结束
}
curBody = curBody.getNext(); //指针后移
}
}

/**
* @param startNo 从第几个小孩开始数数 k
* @param countNum 数几下,也就是介绍里面的m
* @param nums 最初有多少
*/
//根据输入计算 出圈顺序
public void countBoy(int startNo, int countNum, int nums){
if (first == null || startNo < 1 || startNo > nums){
//校验
System.out.println("参数输入有误,请重新输入.");
return;
}
Boy helper = first; //辅助指针
//让helper指向最后一个结点(归位,此时helper在后,first在前)
while (true){
if (helper.getNext() == first) break;
helper = helper.getNext();
}
//从第k个小孩开始数,即startNo
for (int i=0; i<startNo-1; i++){
first = first.getNext();
helper = helper.getNext();
}
//小孩开始报数,m,first和helper同时移动m-1次
//first负责出 helper紧随其后,维护指针&链表
while (true){
if (helper == first){//圈中 只有一个结点了
break;
}
for (int i=0; i<countNum-1; i++){ //指针同时移动 m-1次
first = first.getNext();
helper = helper.getNext();
}
//此时first指向要出圈的结点
System.out.printf("小孩%d出圈\t",first.getNo());
first = first.getNext();
helper.setNext(first); //这里操作相当于删除一个结点,维护单链表
}
System.out.printf("最后一个小孩 %d\n",first.getNo());

}
}


//创建Boy节点
class Boy {
private int no; //编号
private Boy next; //指向下一个节点

public Boy(int no){
this.no = no;
}

public int getNo(){
return no;
}
public void setNo(int no){
this.no = no;
}
public Boy getNext(){
return this.next;
}
public void setNext(Boy next){
this.next = next;
}
}

最终打印:

1
小孩2出圈	小孩9出圈	小孩3出圈	小孩11出圈	小孩6出圈	小孩1出圈	小孩13出圈	小孩12出圈	小孩14出圈	小孩5出圈	小孩10出圈	小孩4出圈	小孩7出圈	最后一个小孩 8

本文作者:Anthony

本文链接: https://www.youdef.com/posts/51.html

评论