一、簡介
約瑟夫問題（有時也稱為約瑟夫斯置換，是一個出現(xiàn)在計算機(jī)科學(xué)和數(shù)學(xué)中的問題。在計算機(jī)編程的算法中，類似問題又稱為約瑟夫環(huán)。又稱“丟手絹問題”.）
例子：
len個人圍成一個圈，玩丟手絹游戲。從第k個人開始，從1開始數(shù)數(shù)，當(dāng)數(shù)到m時，數(shù)m的人就退出圈子，當(dāng)圈子只剩下一個人為止。
問題分析與算法設(shè)計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現(xiàn)方法。
題目中l(wèi)en個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示，可以使用結(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向第一個孩子的頭節(jié)點，另一個為作為判斷的節(jié)點temp（負(fù)責(zé)跑龍?zhí)祝?/p>
具體代碼如下：
java" id="highlighter_52376">
|
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
|
package demo11;/** * 約瑟夫問題， 化為丟手絹 * * @author tianq 思路：建立一個Child類 一個循環(huán)列表類CyclLink */public class demo11 { public static void main(String[] args) { CyclLink cyclink = new CyclLink(); cyclink.setLen(15); cyclink.createLink(); cyclink.setK(2); cyclink.setM(2); cyclink.show(); cyclink.play(); }}// 先建立一個孩子類class Child { // 孩子的標(biāo)識 int no; Child nextChild; // 指向下一個孩子 public Child(int no) { // 構(gòu)造函數(shù)給孩子一個id this.no = no; }}class CyclLink { // 先定義一個指向鏈表第一個小孩的引用 // 指向第一個小孩的引用，不能動 Child firstChild = null; Child temp = null; int len = 0; // 表示共有幾個小孩 int k = 0; //開始的孩子 int m = 0; //數(shù)到幾推出 // 設(shè)置m public void setM(int m) { this.m = m; } // 設(shè)置鏈表的大小 public void setLen(int len) { this.len = len; } // 設(shè)置從第幾個人開始數(shù)數(shù) public void setK(int k) { this.k = k; } // 開始play public void play() { Child temp = this.firstChild; // 1.先找到開始數(shù)數(shù)的人 for (int i = 1; i < k; i++) { temp = temp.nextChild; } while (this.len != 1) { // 2.數(shù)m下 for (int j = 1; j < m; j++) { temp = temp.nextChild; } // 找到要出圈的前一個小孩 Child temp2 = temp; while (temp2.nextChild != temp) { temp2 = temp2.nextChild; } // 3.將數(shù)到m的小孩，退出 temp2.nextChild = temp.nextChild; // 讓temp指向下一個數(shù)數(shù)的小孩 temp = temp.nextChild; // this.show(); this.len--; } // 最后一個小孩 System.out.println("最后出圈" + temp.no); } // 初始化環(huán)形鏈表 public void createLink() { for (int i = 1; i <= len; i++) { if (i == 1) { // 創(chuàng)建第一個小孩 Child ch = new Child(i); this.firstChild = ch; this.temp = ch; } else { if (i == len) { // 創(chuàng)建第一個小孩 Child ch = new Child(i); temp.nextChild = ch; temp = ch; temp.nextChild = this.firstChild; } else { // 繼續(xù)創(chuàng)建小孩 Child ch = new Child(i); temp.nextChild = ch; temp = ch; } } } } // 打印該環(huán)形鏈表 public void show() { Child temp = this.firstChild; do { System.out.print(temp.no + " "); temp = temp.nextChild; } while (temp != this.firstChild); }} |
結(jié)果：
總結(jié)
以上就是本文關(guān)于java編程約瑟夫問題實例分析的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/tianqingdezhuanlan/article/details/52304263
