C++經典演算法題-約瑟夫問題

• 2020 年 2 月 13 日
• 筆記

26.Algorithm Gossip: 約瑟夫問題（Josephus Problem）

說明

據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人佔領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人到，於是決定了 一個自殺方式，41個人排成一個圓圈，由第1個人 開始報數，每報數到第3人該人就必須自殺， 然後再由下一個重新報數，直到所有人都自殺身亡為止。

然而Josephus 和他的朋友並不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡遊戲。

解法

約瑟夫問題可用代數分析來求解，將這個問題擴大好了，假設現在您與m個朋友不幸參與了這個遊戲，您要如何保護您與您的朋友？只要畫兩個圓圈就可以讓自己與朋友免於死亡遊戲，這兩個圓圈內圈是排列順序，而外圈是自殺順序，如下圖所示：

使用程式來求解的話，只要將陣列當作環狀來處理就可以了，在陣列中由計數1開始，每找到三個無資料區就填入一個計數，直而計數達41為止，然後將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列，41個人而報數3的約琴夫排列如下所示：

14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12  22 33 13 29 23

由上可知，最後一個自殺的是在第31個位置，而倒數第二個自殺的要排在第16個位置，之前的人都死光了，所以他們也就不知道約琴夫與他的朋友並沒有遵守遊戲規則了。

#include<stdio.h>  #include<stdlib.h>  #define N 41  #define M 3        int main(void) {          int man[ N] ={              0          } ;          int count = 1;          int i = 0, pos = -1;          int alive = 0;            while (count <= N) {              do {                  pos = (pos + 1) % N; // 環狀處理                    if (man[pos] == 0) i++;                    if (i == M) {    //  報數為3了                      i = 0;                      break;                  }              } while (1);                man[pos] = count;              count++;          }            printf("n約琴夫排列：");          for (i = 0; i < N; i++)              printf("%d ", man[i]);          printf("nn您想要救多少人？");          scanf("%d", & alive);            printf("nL表示這%d人要放的位置：n", alive);          for (i = 0; i < N; i++) {              if (man[i] > alive) printf("D");              else printf("L");              if ((i + 1) % 5 == 0) printf("	");          }          printf("n");          return 0;      }