Plain's Blog

休想打败我的生活🔥

  1. 1. 引入
  2. 2. 使用环形链表的方式解决
    1. 2.1. 结果
  3. 3. 闲言碎语

引入

约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”.)

丢手帕游戏是约瑟夫问题的一个变种,游戏很简单,N个小孩围成一个圈,标号为1到N,从编号为m的小孩开始报数,报到第L个小孩退出游戏,然后下一个小孩继续从1开始报数,数到第L个小孩退出游戏,如此循环,直到剩下最后一个小孩是胜利者.

使用环形链表的方式解决

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
package com.yusefu;

public class Test {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
//创建链表
CircleLinkList game = new CircleLinkList(10, 2, 4);
long endTime = System.currentTimeMillis();

//玩游戏
game.play();
long playTime = System.currentTimeMillis();

//计算一下时间
System.out.println("创建链表用了" + (endTime - startTime) / 1000.0 + "秒");
System.out.println("玩游戏共用了" + (playTime - startTime) / 1000.0 + "秒");
}
}

/**
* 节点
*/
class Child {
protected int node;
protected Child nextChild;

public Child(int node) {
this.node = node;
}
}

/**
* 链表
*/
class CircleLinkList {

//参与游戏人数
private int playBoys;

//开始位置
private int startIndex;

//结束位置
private int countNum;

//第一个孩子
private Child firstChild;

//标识当前小孩
private Child temp;

/**
* @param playBoys
* @param startIndex
* @param countNum
*/
public CircleLinkList(int playBoys, int startIndex, int countNum) {
this.playBoys = playBoys;
this.startIndex = startIndex;
this.countNum = countNum;
createList();
}

/**
* 创建循环链表
*/
private void createList() {
for (int i = 1; i <= playBoys; i++) {
if (i == 1) { //第一个小孩
Child child = new Child(i);
this.firstChild = child;
this.temp = child;
} else if (i == playBoys) { //最后一个小孩
Child child = new Child(i);
this.temp.nextChild = child;
this.temp = child;
this.temp.nextChild = this.firstChild;//最后一个小孩的下一个小孩指向第一个小孩
} else {
Child child = new Child(i);
this.temp.nextChild = child;
this.temp = child;
}
}
}

/**
* 玩游戏
*/
public void play() {

temp = firstChild;

//先找到从第几个小孩开始数,下一个...下一个...
for (int i = 1; i < startIndex; i++) {
temp = temp.nextChild;
}

System.out.println("游戏开始,从第" + temp.node + "个小孩开始数,数到第" + this.countNum + "个小孩退出游戏");

while (this.playBoys > 1) {

//找到要退出游戏的前一个小孩
for (int i = 1; i < countNum - 1; i++) {
temp = temp.nextChild; //当前temp是要退出的前一个小孩
}

//要退出的小孩
Child leaveChild = temp.nextChild;
System.out.println("当前退出的小孩编号为:" + leaveChild.node);
//将退出小孩的next传给要退出小孩的前一个node的next, 这样小孩就退出了
temp.nextChild = leaveChild.nextChild;

//如果要退出的小孩是第一个小孩,则将第一个小孩重置为退出小孩的下一个小孩
if (leaveChild.node == firstChild.node) {
this.firstChild = leaveChild.nextChild;
}

temp = temp.nextChild;

//玩游戏人数少一个
this.playBoys--;
}

System.out.println("最后剩下的小孩是:" + temp.node);

}
}
结果

游戏开始,从第2个小孩开始数,数到第4个小孩退出游戏
当前退出的小孩编号为:5
当前退出的小孩编号为:9
当前退出的小孩编号为:3
当前退出的小孩编号为:8
当前退出的小孩编号为:4
当前退出的小孩编号为:1
当前退出的小孩编号为:10
当前退出的小孩编号为:2
当前退出的小孩编号为:7
最后剩下的小孩是:6
创建链表用了0.002秒
玩游戏共用了0.004秒
Process finished with exit code 0

闲言碎语

练习一下逻辑思维,以后多看看关于数据结构和算法方面的书

本文作者 : Plain
This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接 : https://plain-dev.com/data-structure-joseph-problem/

本文最后更新于 天前,文中所描述的信息可能已发生改变