約瑟夫問題 Josephus problem

又叫丟手絹問題，N個人圍成一圈，第K個人從1開始報數，數到M的人出圈，后一人接著從1開始報數，直到最后剩下一個。例如N=5，K=1，M=2，出圈的順序是：2，4，1，5，3

基本思路：

將最開始環形鏈表的第一位命名為first，并定義另一個指針helper幫助計算，helper指向最開始環形鏈表的最后一位。

first 和 helper 一起向前移動，每一次循環中被first指向的節點出圈

直到最終 helper = first，說明只剩下最后一個節點

遍歷法代碼如下：

//定義Node3，每一個Node就是一個節點 class Node3 {// 節點序號private int no;// 下一個節點private Node3 next;// 構造節點public Node3(int no) {this.setNo(no);}public Node3 getNext() {return next;}public void setNext(Node3 next) {this.next = next;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}}//利用單向鏈表創建一個環形鏈表 class CLinkedList {// 創建一個first節點private Node3 first = null;// 添加 n 個節點public void add(int n) {// 檢查 n 是否有效if (n < 1) {System.out.println("N is not valid!");return;}Node3 temp = null;// 創建環形鏈表for (int i = 1; i <= n; i++) {Node3 node = new Node3(i);if (i == 1) {first = node;first.setNext(first); // 形成環temp = first; // 讓 temp 指向第一個節點} else {temp.setNext(node);node.setNext(first);temp = node;}}}/*** 丟手絹游戲 int startNo 表示從第幾個小孩開始 int count 表示要數幾下 int nums表示開始總共有多少個小孩在圈內*/public void play(int startNo, int count, int nums) {// 先檢驗數據的有效性if (first == null || startNo < 1 || startNo > nums) {System.out.println("Please input the right numbers!");return;}// 創建 helper 變量幫助計算出圈，helper 指向環形鏈表的最后一位Node3 helper = first;while (true) {if (helper.getNext() == first) {break;}helper = helper.getNext();}// 如果不是從第一位小孩開始，就需要將 first 和 helper 向前移動，讓 first 指向開始的小孩for (int i = 0; i < startNo - 1; i++) {first = first.getNext();helper = helper.getNext();}// 當小孩開始報數時，first 和 helper 需要移動 count-1 次，然后出圈// 循環操作直到還剩最后一個小孩while (true) {// 當 helper 和 first 向遇，證明只剩最后一個小孩if (helper == first) {break;}// first 和 helper 向后移動 count+1 位for (int i = 0; i < count - 1; i++) {first = first.getNext();helper = helper.getNext();}// first 指向的小孩出圈System.out.println("第" + first.getNo() + "個小孩出圈");first = first.getNext();helper.setNext(first);}System.out.println("最后留在圈中的小孩是第" + first.getNo() + "個");}

相關章節
第一節 簡述
第二節 稀疏數組 Sparse Array
第三節 隊列 Queue
第四節 單鏈表 Single Linked List
第五節 雙向鏈表 Double Linked List
第六節 單向環形鏈表 Circular Linked List
第七節 棧 Stack
第八節 遞歸 Recursion
第九節 時間復雜度 Time Complexity
第十節 排序算法 Sort Algorithm
第十一節 冒泡排序 Bubble Sort
第十二節 選擇排序 Select Sort
第十三節 插入排序 Insertion Sort
第十四節 冒泡排序，選擇排序和插入排序的總結
第十五節 希爾排序 Shell’s Sort
第十六節 快速排序 Quick Sort
第十七節 歸并排序 Merge Sort

總結

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

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