當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

数据结构与算法--我们来玩丢手绢（约瑟夫环问题）

發布時間：2023/12/4 编程问答 35 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构与算法--我们来玩丢手绢（约瑟夫环问题）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

我們來玩丟手絹

昨天我們打撲克，今天我們丟手絹
丟手絹我們都知道這個游戲，他的由來由約瑟夫（Josephus）提出來的

據說著名猶太歷史學家Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中， 39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決。 Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

問題來了，我們就不殺呀殺了，還是丟手絹吧，讓n個人圍成一個環，編號從1 ~n，從1 開始數當數到第m個人時候，他從圈中離開，接著從m+1 個人數，繼續m個，在出局，依次復制這個過程，求最后一個出局的人是幾號？

方案一，環形鏈表

題目明顯提到了數字的圓圈，自然我們可以構造一個這樣類似的數據結構去模擬這種過程。在常用數據結構中，n個階段的環形鏈表很好的重現了這種模式
我們先構建n個節點的鏈表，每次刪除第m個元素，當環形鏈表中元素只剩下一個時候得到解
算法分析：
- 鏈表頭開始，指定位置position，鏈表尾指定位置before
- 循環m次，分別將position與before都前移m-1次，得到指定位置
- 刪除psition位置節點，讓position指向position.next，統計個數count = n-1
- 繼續以上步驟
以上步驟中循環次數（n-1）*m次因此時間復雜度應該是O(nm)，當m特別大40000 ，時間復雜度會異常的大，非常慢
優化：可以通過取余操作，直接計算出m次循環在鏈表中實際的步驟，將 m % count -1得到實際步驟，當m是大數時候，優化效果明顯
如上分析有如下代碼：

/*** 約瑟夫環問題：將0,1,2,3,4.....n 這n個數字排列成一個圈圈，從數字0 開始數m個數，刪掉他，* 接著從m+1 個開始數在來m個繼續刪除，一次類推，求出剩下的最后一個數據* @author liaojiamin* @Date:Created in 14:30 2021/7/7*/ public class JosephusForList {public static void main(String[] args) {System.out.println(delNodeForJosephus(40000,997));}/*** 環形鏈表方法* */public static Integer delNodeForJosephus(Integer n, Integer m){if(n <= 0|| m<=0){return null;}//構造環形隊列ListNode head = new ListNode(0);ListNode last = null;ListNode position = head;for (Integer i = 1; i < n; i++) {last = new ListNode(i);position.setNext(last);position = position.getNext();}last.setNext(head);ListNode before = position;position = position.getNext();//當需要移動的位置小于當前數據個數，直接移動指針Integer count = n;while (m <= count){for (Integer i = 0; i < m-1; i++) {before = position;position = position.getNext();}before.setNext(position.getNext());position = position.getNext();count--;}//當m 大于當前需要移動位置個數，取余計算最小移動值while (m > count && count > 1){int move = Math.abs(m%count - 1);for (Integer i = 0; i< move;i++){before = position;position = position.getNext();}before.setNext(position.getNext());position = position.getNext();count--;}position.setNext(null);return position.getValue();}}

以上算法時間復雜度O(nm)，空間復雜度O(n)

約瑟夫環問題

約瑟夫環問題最終還是一個數學問題（數學能救命），我們大概來推導一下
首先定義一個關于n 和 m的方法記為f(n, m)，表示每次在n個數字0~n-1中每次刪除第m個數字，最后剩下的數字
第一個刪除的數字用n，m表示：（m-1）% n , 當且僅當 m>0 n>1的時候，我們記為k =（m-1）% n 如下圖
接著下一次遍歷是從k+1 開始的現有數字總共 n-2個，k+1排第一，也就有如下圖所示的順序

我們記錄第一個刪除后的值是 d(n-1, m)，與之前的 f(n, m)是同一個規則刪除，那么他們最終的結果肯定是一樣的，那么就有 d(n-1, m) = f(n, m)
也就是我們將k+1當成是當前的第0 位置，k-1是當前最后的位置，也就是 n-2，那么我們依次推導出各個的位置，k+2是第一個位置
- n-2之后有n-1，在加上k個數 (n-2)-(k+2)+1=n-k-3
- n-2 之后有k1個數，(n-2)-(k+1)+1 = n-k+2
- 同理 0 則是 n-k+1
- 1 是 n-k
- k-1則是n-2
- 用下圖對應關系展示
如上圖，上部分是數據值，下部分是對應的位置，我們可以定義兩個集合：
- A集合是上部分數據值
- B集合是下部分位置值
- A,B為非空集, 若存在對應法則f(), 使得對每個 x∈y 都有唯一確 y∈B與之對應, 則稱對應法則f()為A到B的映射
如果我們找到了數據值與位置值的映射關系函數，是不是可以直接通過計算得到下一步中需要刪除的數據
此處，我們定義映射為p，推導出p(x) = (x-k-1)%n,映射的逆映射就是p(x) = (x+k+1)%n
根據以上映射規則，映射之前的寫中最后剩下的數字 d(n-1, m) = p[f(n-1)+m] = [f(n-1,m) +k +1]%n，將k=（m-1）%n 得到f(n,m) = d(n-1,m)= [f(n-1,m) +k +1]%n
那么我們得到一個遞推公式
- n =1 f(n, m) = 0
- n>1 f(n, m) = [f(n-1, m)+m ]%n
有了如上公式我們很自然直接遞歸就能得到第n次的結果
如上分析有如下代碼：

以上遞歸實現當n， m值非常大時候幾乎不可用，情況通之前文章斐波那契數量原因一樣

優化方案三

動態規劃解法：在以上推導基礎上用一個循環解決

package com.ljm.resource.math.myList;/*** 約瑟夫環問題：將0,1,2,3,4.....n 這n個數字排列成一個圈圈，從數字0 開始數m個數，刪掉他，* 接著從m+1 個開始數在來m個繼續刪除，一次類推，求出剩下的最后一個數據* @author liaojiamin* @Date:Created in 14:30 2021/7/7*/ public class JosephusForList {public static void main(String[] args) {System.out.println(fixJosephusForMath2(40000,997));}/*** 動態規劃實現* 數學方案：通過計算得出發f(n,m)* n=0 f(n,m) = 1* n>1 f(n,m) = [f(n-1,m)+m]%n** */public static Integer fixJosephusForMath2(Integer n, Integer m){if(n <= 0|| m<=0){return null;}int last = 0;for(int i=2;i<=n;i++){last = (last+m)%i;}return last;}}

可以看出，以上實現思路分析非常復雜，但是代碼簡單時間復雜度O(n)，空間復雜度O(1)，遠優于第一，第二解法

上一篇：數據結構與算法–判斷撲克牌是否順子
下一篇：數據結構與算法–這個需求很簡單怎么實現我不管（發散思維）

總結

以上是生活随笔為你收集整理的数据结构与算法--我们来玩丢手绢（约瑟夫环问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。