循环排座位问题------西方的约瑟夫环

本文主要是介绍循环排座位问题------西方的约瑟夫环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

著名历史学家Josephus（约瑟夫）经历过以下故事：在罗马人占领乔塔帕特后，40个犹太人和Josephus躲在一个山洞中。40个犹太人决定宁死也不被敌人抓到，于是决定集体自杀。大家经过讨论决定了一个自杀方式，41个人围成一个圆圈，由第1个人开始报数，每报数到3的人就必须自杀，然由再由下一个人重新开始报数，直到所有人都自杀身亡为止。然而Josephus并不想遵从这个规则，不想自杀。于是，Josephus先假装同意该方案，然后坐到大家围成圆圈的第31个位置，最后逃过了这场死亡游戏。

那么，为什么Josephus坐在第31位置就可逃过该死亡游戏呢？

首先将41个人排成一个圆圈，并编好序号，如图5-17中圆内的编号（圆圈内的编号是座位序号，圆圈外的数字是每个人报到3的顺序）。然后从编号1的人开始报数，报到3就表示该人是第1个该自杀的人，序号为3的人首先数到3（将序号为3的人排除到圆圈之外），接下来序号为4的人又从1开始报数，……，这样不停地循环，序号为31的人将是最后剩下的一个人。由于前面的人都已自杀，没法监督到最后这个人是否遵守游戏规则了。下面借用一张图来示意一下：

下面上代码：

#include <iostream>using namespace std;void josephus(int &n, int *p, int *p1)
{int i = 1, k = 1, n1 = n, yu, shang;while (1){while(i <= n){if(!(i % 3)){p[i] = 0;}i++;}break;}shang = n / 3;yu = n % 3;n = n - shang;if(yu){for (int j = n1 - yu + 1; j <= n1; j++){p1[k] = p[j];p[j] = 0;k++;}}for (int j = 1; j <= n1; j++){if(p[j]){p1[k] = p[j];k++;}}while (k){p[k] = p1[k];k--;}
}int main()
{int survive[42], survive1[42], n = 41;for (int i = 0; i < 42; i++){survive[i] = i;survive1[i] = 0;}while(n > 2){josephus(n, survive, survive1);}cout << "Josephus 站在第 " << survive[1] << " 或者 " << survive[2] << " 的位置。\n";return 0;
}

结果：