约瑟夫问题的学习心得

约瑟夫问题

约瑟夫问题的引入及历史背景

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环
这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。
人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。
问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

1. 创建单向环形链表，要想实现约瑟夫问题首先需要创建一个单向环形链表

//创建人物节点
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 next;
	}
	public void setNext(Boy next) {
    
		this.next = next;
	}
}

//创建单向环形链表
class CircleSingleLinkedList{
    
	//创建第一个指针，这个指针永远指向第一个孩子节点
	Boy firstBoy = null;
	public void addBoy(int num) {
    
	//进行一个判断，如果人数小于1的话就没有办法创建单向环形链表
		if (num < 1) {
    
			System.out.println("无法构建环形链表！！！");
			return;
		}
		else {
    
			//创建辅助指针用于实现连接下一个结点，因为firstBoy指针不能动
			Boy curBoy = null;
			for (int i = 1; i <= num; i++) {
    
				//开始创建节点
				Boy boy = new Boy(i);
				//进行一个判断，如果是第一个节点的话就让firstBoy指针指向它
				//标记为第一个节点，后面的节点只要连接它即可成环
				if (i == 1) {
    
					//指向第一个节点
					firstBoy = boy;
					//让自己连接自己成环
					firstBoy.setNext(firstBoy);
					//辅助指针也指向第一个节点
					curBoy = firstBoy;
				}
				else {
    
					//将辅助指针的next域与下一个节点进行连接
					curBoy.setNext(boy);
					//将下一个节点的next域与first连接，实现环结构
					boy.setNext(firstBoy);
					//辅助指针移向下一个节点
					curBoy = boy;
				}
			}
		}
	}

1. 遍历环形链表

public void showList() {
    
		//判断firstBoy是否为空，为空的话就说明链表并未创建
		if (firstBoy == null) {
    
			System.out.println("链表未创建");
			return;
		}
		else {
    
			//因为firstBoy指针只能指向第一个不能动，所以创建一个辅助指针来实现遍历操作
			Boy curBoy = firstBoy;
			while(true) {
    
				System.out.printf("第%d个人\n", curBoy.getNo());
				//此时说明全部遍历完毕了，辅助指针有指向了第一个节点
				if (curBoy.getNext() == firstBoy) {
    
					break;
				}
				curBoy = curBoy.getNext();
			}
		}
	}

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

/** * * @param startNo 从第几个人开始数 * @param countNum 表示数几下被处决 * @param sumBoy 一共有多少个人 */
	public void countBoy(int startNo, int countNum, int sumBoy) {
    
		/* 首先进行判断，看这个环是否存在，从第几个人开始数不能为小于1不然就没有意义 也不能从超过了人数的总和开始数 */
		if (firstBoy == null || startNo < 1 || startNo > sumBoy) {
    
			System.out.println("输入有误，请重新输入！！！");
			return;
		}
		//创建helperBoy辅助指针，并让其指向最后一个节点
		//我们需要创建一个辅助指针，指向整个环的最后一个节点，也就是firstBoy的后一个节点
		Boy helpBoy = firstBoy;
		//用循环去实现让helperBoy指向整个链表的最后一个节点
		while(true)
		{
    
			//此时说明已在最后一个节点
			if (helpBoy.getNext() == firstBoy) {
    
				break;
			}
			helpBoy = helpBoy.getNext();
		}
		
		//要知道是从第几个人开始报数，需要将firstBoy指针和helpBoy指针移向它，也就是移动startNo-1次，如果不太懂的话就去画一画图
		for (int i = 0; i < startNo-1; i++) {
    
			firstBoy = firstBoy.getNext();
			helpBoy = helpBoy.getNext();
		}
		
		//当小孩报数时让firstBoy和helpBoy同时移动countNum-1次
		//然后就处决点到的圈中人，此处使用循环操作直到链表中只剩下一个节点
		while(true)
		{
    
			//说明此时只剩下一个节点
			if (helpBoy == firstBoy) {
    
				break;
			}
			//否则我就要将firstBoy和helpBoy同时移动countNum-1次
			//也就相当于依次报数
			for (int i = 0; i < countNum-1; i++) {
    
				firstBoy = firstBoy.getNext();
				helpBoy = helpBoy.getNext();
			}
			System.out.printf("第%d个小孩出圈\n", firstBoy.getNo());
			//人被处决，也就是删除节点
			firstBoy = firstBoy.getNext();
			helpBoy.setNext(firstBoy);
		}
		System.out.println("圈中的最后幸存者是：" + firstBoy.getNo());
	}

出圈过程

4. 测试代码

public class joseph {
    

	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
		circleSingleLinkedList.addBoy(5);
// circleSingleLinkedList.showList();
		circleSingleLinkedList.countBoy(1, 2, 5);

	}

}