链表的实际应用：约瑟夫问题

朱雀 2021-05-10 11:33 617阅读 0赞

## 今天要解决的是约瑟夫问题 ##

### 1 .链表的基本概念 ###

#### 1.1 什么是链表 ? ####

如下图所示 :

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]  
**SingleLinkedList代表单向链表** , 每一个结点含有 :

1.  data域 : 用于保存数据
2.  next域 : 用于保存指向下一个结点的指针

**DoubleLinkedList代表双向链表** , 每一个结点含有 :

1.  prev域 : 用于保存指向前一个结点的指针
2.  data域 : 用于保存数据
3.  next域 : 用于保存后一个数据的指针

##### 对于头结点的说明 : #####

头结点表示一个单链表第一个含有有效数据结点之前的结点, 它一般不保存数据, 用作链表的前驱

**使用头结点和不使用头结点的不同 :**

使用头结点方便在第一个位置进行插入, 删除操作时和其它位置的插入删除操作的代码保持一致性 , 因为带上头结点之后 , 头指针永远不需要移动 , 而不带上头结点时 , 在第一个位置进行插入或删除操作时, 头指针需要移动 , 较为麻烦 , 有兴趣的读者可以尝试一下 , 这里不再详述…

#### 1.3 单向循环链表(不带头结点) ####

![在这里插入图片描述][20190711002147677.png]

单向循环链表就是单向链表的升级版 , 尾结点的指针不再指向空 , 而是指向**第一个结点**

## 约瑟夫问题(也称"丢手帕问题") ##

![timg_image_quality_80_size_b9999_10000_sec_1562775796416_di_a7bc151dd485871bda13d88f36f0c95e_imgtype_0_src_http_3A_2F_2Ftxt15.book118.com_2F2016_2F1231_2Fbook78535_2F78534873.jpg][]

### 约瑟夫问题起源 : ###

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。**然而Josephus 和他的朋友并不想遵从**。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

为什么约瑟夫一开始就知道站在16和31就一定能躲过自杀呢?**这就是数学的魅力所在, 真香~**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 1]

**外圈表示第几个自杀, 内圈表示每个人的序号**

--------------------

### 单向循环链表解决约瑟夫问题 ###

#### 问题重述 : ####

设有n个人围成一圈 , 编号从1到n , 约定从编号为k(1 <= k <= n)的人从1开始报数 , 数到 m 的那个人被淘汰 , 接着下一个人重新从1开始报数 , 数到 m 再淘汰一人 , 如此反复 , 直至剩下最后一个人为止

#### 思路 : ####

① 为什么使用单向循环链表 ?

我们可以知道约瑟夫问题是一个不断循环而且数据不断减少的过程 , 使用单向循环链表可以很方便地对数据进行删除 , 而且遍历链表方便

② 理清过程 , 首先一个带有n个结点地单循环链表 , 从第k个人开始从1报数 , 那么首先需要将头指针指向第k个人 , 辅助删除指针指向第(k-1)个人 , 定义辅助删除指针的意义是为了方便当第k个人淘汰时 , 可以很方便的将第(k-1)的next指针指向第(k+1)个人, 当人数剩下一个人时 , 则认为这场游戏已经结束了 , 最后剩下的那个人就是胜利者  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 3]

### 代码实现(JAVA版) : ###

#### 1.定义小孩的结点 ####

//定义一个Child结点, 每一个Child对象就是一个结点
    public class Child{ 
    	//编号
    	public Integer no;
    	//指向下一个结点
    	public Child next;
    	
    	public Child(Integer no) { 
    		super();
    		this.no = no;
    	}
    	
    	public Integer getNo() { 
    		return no;
    	}
    
    	public void setNo(Integer no) { 
    		this.no = no;
    	}
    
    	@Override
    	public String toString() { 
    		return "Node [no=" + no + "]";
    	}
    }

#### 2.定义单向循环链表 ####

//定义SingleLinkedList来管理我们的Child结点
    class CircleLinkedList{ 
    	
    	//第一个结点
    	private Child first = null;
    	//当前的最后一个结点
    	private Child rear = null;
    	
    	//添加结点到单向链表
    	public void add(Child child){ 
            //判断当前链表是否为空
    		if(first == null){ 
    			first = child;
    			child.next = first;
    			rear = child;
    		}else{ 
    			rear.next = child;
    			child.next = first;
    			rear = child;
    		}
    	}
    	
    	/** * 核心代码 * @param m 数到几出圈 * @param n 共有n个孩子玩游戏 * @param k 从第k个孩子开始报数 */
    	//开始游戏, 小孩出圈
    	public void play(int k, int m, int n){ 	
    		int count = 1;
    		//使first指针和deleteNode指针指向第k个孩子和(k-1)个孩子
    		for(int i = 1; i<=n; i++){ 	
    			if(i==k){ break;}
    			first = first.next;
    			rear = rear.next;
    		}
    		//辅助删除指针, 需要删除元素时使用, 所以初始化时应该指向最后一个结点
    		//因为一开始第一个结点开始报数, 有可能报的是1, num也为1, 则首结点被淘汰
    		Child deleteNode = rear;
    		if(n==1){ 
    			System.out.println("你自己一个人玩, 你逃不掉了, 人数过少,无法开始游戏");
    			return ;
    		}
    		System.out.println("被淘汰的小孩的编号为:");
    		count = 1;
    		while(true){ 
    			//只剩下一个人了
    			if(n==1){ 
    				System.out.println();
                    System.out.println("存活的玩家是:"+first.getNo());
    				break;
    			}
    			//判断是否数到m, 如果是则删除该结点
    			if(count == m){ 
    				System.out.print(deleteNode.next.getNo()+" ");
    				first = first.next;
    				deleteNode.next = first;
    				count = 1;
                    //人数减少
    				n--;
    				continue;
    			}
                //头指针与辅助删除指针都往后移一位
    			deleteNode = deleteNode.next;
    			first = first.next;
    			count++;
            }
    	}
    }

#### 3. 代码运行 ####

public class JosephuSolution { 
    
    	public static void main(String[] args) { 
    		
    		CircleLinkedList circleLinkedList = new CircleLinkedList();
    		int i = 1;
    		int n = 41;
            //生成小孩
    		while(i<=n){ 
    			Child child = new Child(i);
    			circleLinkedList.add(child);
    			i++;
    		}
            // k=1, m=3, n=41
    		circleLinkedList.play(1, 3, n);
    	}
    	
    }
    输出结果:
    被淘汰的小孩的编号为:
    3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 
    28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 
    存活的玩家是:31

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210509/37deaa802f0242c2878a6e73be344150.png
[20190711002147677.png]: /images/20210509/387165619a284fe08f1dcbe4e6991ced.png
[timg_image_quality_80_size_b9999_10000_sec_1562775796416_di_a7bc151dd485871bda13d88f36f0c95e_imgtype_0_src_http_3A_2F_2Ftxt15.book118.com_2F2016_2F1231_2Fbook78535_2F78534873.jpg]: https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1562775796416&di=a7bc151dd485871bda13d88f36f0c95e&imgtype=0&src=http%3A%2F%2Ftxt15.book118.com%2F2016%2F1231%2Fbook78535%2F78534873.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 1]: /images/20210509/9f6d938edda3465f96e63e21f8531b3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 2]: /images/20210509/4c96643621914ff2a828dcf8db81363e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70 3]: /images/20210509/f37a7f02c176415787f75dede8c8930b.png