约瑟夫环问题：
问题来历
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。 [1]
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。
一般形式
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。
可以使用单向环形链表来解决
设计： 单链表
- data
- next
image-20200713144927140.png
构建一个单向的环形链表的思路：
- 先创建第一个节点，让first指向该节点，并行成环形。
- 后面当我们每创建一个新的节点，就把该节点，加入已有的环形链表中即可。
遍历环形链表：
- 先让一个辅助遍历指向first节点。
- 然后通过一个while循环遍历该环形链表 curBoy.next == first 结束
image-20200713202123765.png
如何创建环形链表？
环形单链表
Boy
public class Boy {
private int no;
private Boy next;
public Boy(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public Boy getNext() {
return next;
}
public void setNo(int no) {
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no + '}';
}
}
1. 添加链表
// 添加链表
public void addBoy(int n){
if (n<1){//检验n的合法性
System.out.println("n不正确");
return;
}
Boy cur = null;
for (int i = 1; i <= n; i++) {
//创建节点
Boy boy = new Boy(i);
//处理第一个最特别的节点
if (i==1){
first = boy;
cur = boy;
first.setNext(cur);
}
cur.setNext(boy);
boy.setNext(first);
cur = cur.getNext();
}
}
2.遍历链表
//遍历链表
public void show(){
if (first==null){//判断链表是否为空
System.out.println("链表为空");
return;
}
//创建辅助指针
Boy cur = first;
while(true){
System.out.println(cur);
if (cur.getNext()==first){//表明已经遍历完成
break;
}
cur = cur.getNext();
}
}
3.出环
/**
*
* @param startNo 起始位置
* @param countNum 计数次数
* @param nums 总人数
*/
public void out(int startNo,int countNum,int nums){
if (first==null || startNo < 0 || startNo > nums){
System.out.println("参数输入有误");
}
Boy helper = first;
while (true){//让helper指向最后一个节点
if (helper.getNext() == first){
break;
}
helper = (helper.getNext());
}
for (int i = 0; i < startNo-1; i++) {
first = first.getNext();
helper = helper.getNext();
}
while (true){
if (first == helper ){
break;
}
for (int i = 0; i < countNum-1; i++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.println(first);
first = first.getNext();
helper.setNext(first);
}
System.out.println("最后一个人为："+helper);
}
CircleSingleLinkedList
public class CircleSingleLinkedList {
public Boy first = null;
// 添加链表
public void addBoy(int n){
if (n<1){//检验n的合法性
System.out.println("n不正确");
return;
}
Boy cur = null;
for (int i = 1; i <= n; i++) {
//创建节点
Boy boy = new Boy(i);
//处理第一个最特别的节点
if (i==1){
first = boy;
cur = boy;
first.setNext(cur);
}
cur.setNext(boy);
boy.setNext(first);
cur = cur.getNext();
}
}
//遍历链表
public void show(){
if (first==null){//判断链表是否为空
System.out.println("链表为空");
return;
}
//创建辅助指针
Boy cur = first;
while(true){
System.out.println(cur);
if (cur.getNext()==first){//表明已经遍历完成
break;
}
cur = cur.getNext();
}
}
/**
*
* @param startNo 起始位置
* @param countNum 计数次数
* @param nums 总人数
*/
public void out(int startNo,int countNum,int nums){
if (first==null || startNo < 0 || startNo > nums){
System.out.println("参数输入有误");
}
Boy helper = first;
while (true){//让helper指向最后一个节点
if (helper.getNext() == first){
break;
}
helper = (helper.getNext());
}
for (int i = 0; i < startNo-1; i++) {
first = first.getNext();
helper = helper.getNext();
}
while (true){
if (first == helper ){
break;
}
for (int i = 0; i < countNum-1; i++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.println(first);
first = first.getNext();
helper.setNext(first);
}
System.out.println("最后一个人为："+helper);
}
}
网友评论