1556人阅读
计算机科学（3）
& & & & 思考这样一个问题：你和另外40个人被一个野蛮的部落包围了，酋长要求你们围成一个圆圈，从第1个位置上的人开始报数，报到3的人将会被杀掉。这个过程沿着圆圈一直继续，直到剩下最后一个人，这个人可以安全地离开。你要选择站在第几个位置才能成为那个幸运的幸存者呢？
& & & & 这就是有名的约瑟夫环问题。下面我们就来探讨一下几种解决方案。
& & & &&不难看出，这个问题非常适合使用循环链表求解。建立一个包含41个元素的循环链表，从表头开始进行循环遍历，模拟圆圈报数的过程，遇到报到3的元素就把这个元素删掉，直到链表中仅剩下最后一个元素。
& & & & C语言实现：
#include &stdio.h&
#include &stdlib.h&
#define TOTAL 41
#define COUNT 3
struct llist_t {
struct llist_t *pN
int main() {
struct llist_t *pHead = malloc(sizeof(struct llist_t) * TOTAL);
struct llist_t *pCurrent = pH
if (pHead == NULL) {
printf(&Malloc failed.\n&);
// Initialize the array.
for (i = 0; i & TOTAL; ++i) {
pHead[i].index = i + 1;
pHead[i].pNext = pHead + ((i + 1) % TOTAL);
// Run the process.
while (pCurrent-&pNext != pCurrent) {
for (i = 0; i & COUNT - 1; ++i) {
if (i == COUNT - 2)
pCurrent-&pNext = pCurrent-&pNext-&pN
pCurrent = pCurrent-&pN
printf(&The survivor is the person in position %d.\n&, pCurrent-&index);
free(pHead);
& & & & 在上面的链表法中，我们用到了链表结构，用到了动态内存，对于这个问题而言，有种“杀鸡用牛刀”的感觉。相对于链表和堆栈这些较为复杂的数据结构而言，数组具有轻便，安全，高效和操作简单的优点。在一些场合，数组可以作为链表和堆栈等高级数据结构的替代，产生巧妙的效果。
& & & &&建立数组arr[41]，其中元素的下标代表某个人的位置（注意：这里的位置从0开始，而不是1），而元素的值则是下一个还活着的人的位置。可以看出，初始的数组有这样的形式：a[0] = 1, a[1] = 2, ... a[39] = 40, a[40] = 0，实际上我们模拟出来了一个单向循环链表：a[0]-&a[1]-&...-&a[39]-&a[40]-&a[0]，元素的值相当于链表结构中的指针pNext。之后的操作跟链表法相似。
& & & & C语言实现：
#include &stdio.h&
#define TOTAL 41
#define COUNT 3
int main() {
int arr[TOTAL];
int cur = 0;
// current position
// Initialize the array
for (i = 0; i & TOTAL; ++i)
arr[i] = (i + 1) % TOTAL;
// Run the process
while (arr[cur] != cur) {
for (i = 0; i & COUNT - 1; ++i) {
if (i == COUNT - 2)
arr[cur] = arr[arr[cur]];
cur = arr[cur];
printf(&The survivor is the person in position %d.\n&, cur + 1);
& & & &&总结一下可以使用数组来代替链表的条件：
链表必须是单向（循环）的。
只需关心链表元素的序号，而不必关心它的内部情况（比如说它有哪些数据成员，以及每个数据成员的值是多少）。
数组法的另一种思路：
& & & &&建立数组arr[41]，其中元素的下标代表某个人的位置（同样的，这里的位置从0开始），对于还活着的人，元素的值设置为1；对于已经死了的人，元素的值设置为0。初始数组的所有元素的值均为1。我们要做的是，从第0个人开始，进行元素值的累加，累加到3时就杀掉一个人（把元素的值置为0），如此循环，直到数组中仅剩下一个1。
& & & & C语言实现：
#include &stdio.h&
#define TOTAL 100
#define COUNT 3
int main() {
int arr[TOTAL];
int survivors = TOTAL;
// number of survivors
// current position
int sum = 0;
// Initialize the array
for (cur = 0; cur & TOTAL; ++cur)
arr[cur] = 1;
// Run the process
for (cur = 0; survivors & 1; cur = (cur + 1) % TOTAL) {
sum += arr[cur];
if (sum == COUNT) {
arr[cur] = 0;
for (cur = 0; cur & TOTAL; ++cur)
if (arr[cur] == 1)
printf(&%d\n&, cur + 1);
& & & &&这个方法的妙处就是可以只用一层循环来完成任务。对于圆圈报数，我们要做的就是报数的时候想办法跳过已经死掉的人，我们巧妙地使用了“0不影响累加的结果”这样一个性质，从而只用了一层循环就完成了工作。
& & & &&但是需要注意到的是，这个方法用到了较多的加法运算，这在一定程度上影响了循环的效率。
下面玩点儿数学吧：
& & & & 应该注意到的是，问题只是要求找出幸存者的位置，并没有让我们模拟整个运作过程。前面我们借助计算机的强大运算能力，把整个过程都模拟出来了。但这并不是上策，只要使用一些数学方法稍加分析，我们就能得到一个简洁且优美得多的实现方案。
& & & & 第一个人被杀之后，初始问题就变成了40个人报数的子问题。知道了40个人报数问题的幸存者在哪个位置，理论上我们就可以求得41个人报数问题的幸存者位置。这样层层递归下来，总可以规约到1个人报数的问题。很自然，1个人报数问题的幸存者当然就是这个人。设总共有n个人，报到k的人将被杀掉，幸存者的位置是f(n, k)，我们规定位置从0开始排列。如果f(n-1, k)是已知的，则f(n, k)可求，我们的任务就是找到从f(n-1, k)到f(n,
k)的映射。
& & & & 考虑n=5, k=3的情况，初始位置排列为：
& & & & & & & & 0, 1, 2, 3, 4
& & & & 杀掉第一个人之后，位置排列为：
& & & & & & & & 0, 1, x, 3, 4 & &(x 代表该位置的人被杀)
& & & & 把这个位置状态进行循环左移：
& & & & & & & & 3, 4, 0, 1
& & & & 记这个位置关系为g(s)，其中s代表某一个人，g(s)则代表这个人的位置，我们做一个转换，把位置状态转换为g'(s)：
& & & & & & & & 0, 1, 2, 3
& & & & 很容易求得，g'(s)=(g(s) - 3) % 5，g(s)=(g'(s) + 3) % 5。
& & & & 这样，现在的问题就变成了4个人报数的问题，记4人报数问题的幸存者是 s0, 则f(4, 3)=g'(s0)，从而f(5, 3)=g(s0)=(f(4,
3) + 3) % 5。于是我们有下面的映射关系：
& & & & & & & & f(n, k) = (f(n-1, k) + k) % n
& & & & 这里给出一个直观的图形，这个图形描述了5人报数问题的求解。最外层的环表示5人求解问题，向内依次递减，最内层的环表示1人报数问题。在最外层的环中报到3的人被杀，这个位置就变成不可用（图中用蓝色表示），之后进入第4环，从下一个可用位置开始标号。重复这一过程，直到进入最内层的环。把最内层环中幸存者位置映射到最外层，问题就解决了。5人报数问题的幸存者在位置3上。
& & & & 看看现在的程序：
#include &stdio.h&
#define TOTAL 41
#define COUNT 3
int main() {
int f = 0;
for (i = 2; i &= TOTAL; ++i)
f = (f + COUNT) %
printf(&The survivor is in position %d\n&, f + 1);
}& & & & 现在我们的程序既简洁优美，效率又高。
& & & & 关于约瑟夫环问题，我们就先讨论这么多。文章最后再给大家留一个问题：如果可以有多个幸存者，你能把他们的位置全都找出来吗？
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：5870次
排名：千里之外幸存者：约瑟夫环问题 - feber007的专栏 - CSDN博客
幸存者：约瑟夫环问题
计算机科学
& & & & 思考这样一个问题：你和另外40个人被一个野蛮的部落包围了，酋长要求你们围成一个圆圈，从第1个位置上的人开始报数，报到3的人将会被杀掉。这个过程沿着圆圈一直继续，直到剩下最后一个人，这个人可以安全地离开。你要选择站在第几个位置才能成为那个幸运的幸存者呢？
& & & & 这就是有名的约瑟夫环问题。下面我们就来探讨一下几种解决方案。
& & & &&不难看出，这个问题非常适合使用循环链表求解。建立一个包含41个元素的循环链表，从表头开始进行循环遍历，模拟圆圈报数的过程，遇到报到3的元素就把这个元素删掉，直到链表中仅剩下最后一个元素。
& & & & C语言实现：
#include &stdio.h&
#include &stdlib.h&
#define TOTAL 41
#define COUNT 3
struct llist_t {
struct llist_t *pN
int main() {
struct llist_t *pHead = malloc(sizeof(struct llist_t) * TOTAL);
struct llist_t *pCurrent = pH
if (pHead == NULL) {
printf(&Malloc failed.\n&);
// Initialize the array.
for (i = 0; i & TOTAL; ++i) {
pHead[i].index = i + 1;
pHead[i].pNext = pHead + ((i + 1) % TOTAL);
// Run the process.
while (pCurrent-&pNext != pCurrent) {
for (i = 0; i & COUNT - 1; ++i) {
if (i == COUNT - 2)
pCurrent-&pNext = pCurrent-&pNext-&pN
pCurrent = pCurrent-&pN
printf(&The survivor is the person in position %d.\n&, pCurrent-&index);
free(pHead);
& & & & 在上面的链表法中，我们用到了链表结构，用到了动态内存，对于这个问题而言，有种“杀鸡用牛刀”的感觉。相对于链表和堆栈这些较为复杂的数据结构而言，数组具有轻便，安全，高效和操作简单的优点。在一些场合，数组可以作为链表和堆栈等高级数据结构的替代，产生巧妙的效果。
& & & &&建立数组arr[41]，其中元素的下标代表某个人的位置（注意：这里的位置从0开始，而不是1），而元素的值则是下一个还活着的人的位置。可以看出，初始的数组有这样的形式：a[0] = 1, a[1] = 2, ... a[39] = 40, a[40] = 0，实际上我们模拟出来了一个单向循环链表：a[0]-&a[1]-&...-&a[39]-&a[40]-&a[0]，元素的值相当于链表结构中的指针pNext。之后的操作跟链表法相似。
& & & & C语言实现：
#include &stdio.h&
#define TOTAL 41
#define COUNT 3
int main() {
int arr[TOTAL];
int cur = 0;
// current position
// Initialize the array
for (i = 0; i & TOTAL; ++i)
arr[i] = (i + 1) % TOTAL;
// Run the process
while (arr[cur] != cur) {
for (i = 0; i & COUNT - 1; ++i) {
if (i == COUNT - 2)
arr[cur] = arr[arr[cur]];
cur = arr[cur];
printf(&The survivor is the person in position %d.\n&, cur + 1);
& & & &&总结一下可以使用数组来代替链表的条件：
链表必须是单向（循环）的。
只需关心链表元素的序号，而不必关心它的内部情况（比如说它有哪些数据成员，以及每个数据成员的值是多少）。
数组法的另一种思路：
& & & &&建立数组arr[41]，其中元素的下标代表某个人的位置（同样的，这里的位置从0开始），对于还活着的人，元素的值设置为1；对于已经死了的人，元素的值设置为0。初始数组的所有元素的值均为1。我们要做的是，从第0个人开始，进行元素值的累加，累加到3时就杀掉一个人（把元素的值置为0），如此循环，直到数组中仅剩下一个1。
& & & & C语言实现：
#include &stdio.h&
#define TOTAL 100
#define COUNT 3
int main() {
int arr[TOTAL];
int survivors = TOTAL;
// number of survivors
// current position
int sum = 0;
// Initialize the array
for (cur = 0; cur & TOTAL; ++cur)
arr[cur] = 1;
// Run the process
for (cur = 0; survivors & 1; cur = (cur + 1) % TOTAL) {
sum += arr[cur];
if (sum == COUNT) {
arr[cur] = 0;
for (cur = 0; cur & TOTAL; ++cur)
if (arr[cur] == 1)
printf(&%d\n&, cur + 1);
& & & &&这个方法的妙处就是可以只用一层循环来完成任务。对于圆圈报数，我们要做的就是报数的时候想办法跳过已经死掉的人，我们巧妙地使用了“0不影响累加的结果”这样一个性质，从而只用了一层循环就完成了工作。
& & & &&但是需要注意到的是，这个方法用到了较多的加法运算，这在一定程度上影响了循环的效率。
下面玩点儿数学吧：
& & & & 应该注意到的是，问题只是要求找出幸存者的位置，并没有让我们模拟整个运作过程。前面我们借助计算机的强大运算能力，把整个过程都模拟出来了。但这并不是上策，只要使用一些数学方法稍加分析，我们就能得到一个简洁且优美得多的实现方案。
& & & & 第一个人被杀之后，初始问题就变成了40个人报数的子问题。知道了40个人报数问题的幸存者在哪个位置，理论上我们就可以求得41个人报数问题的幸存者位置。这样层层递归下来，总可以规约到1个人报数的问题。很自然，1个人报数问题的幸存者当然就是这个人。设总共有n个人，报到k的人将被杀掉，幸存者的位置是f(n, k)，我们规定位置从0开始排列。如果f(n-1, k)是已知的，则f(n, k)可求，我们的任务就是找到从f(n-1, k)到f(n,
k)的映射。
& & & & 考虑n=5, k=3的情况，初始位置排列为：
& & & & & & & & 0, 1, 2, 3, 4
& & & & 杀掉第一个人之后，位置排列为：
& & & & & & & & 0, 1, x, 3, 4 & &(x 代表该位置的人被杀)
& & & & 把这个位置状态进行循环左移：
& & & & & & & & 3, 4, 0, 1
& & & & 记这个位置关系为g(s)，其中s代表某一个人，g(s)则代表这个人的位置，我们做一个转换，把位置状态转换为g'(s)：
& & & & & & & & 0, 1, 2, 3
& & & & 很容易求得，g'(s)=(g(s) - 3) % 5，g(s)=(g'(s) + 3) % 5。
& & & & 这样，现在的问题就变成了4个人报数的问题，记4人报数问题的幸存者是 s0, 则f(4, 3)=g'(s0)，从而f(5, 3)=g(s0)=(f(4,
3) + 3) % 5。于是我们有下面的映射关系：
& & & & & & & & f(n, k) = (f(n-1, k) + k) % n
& & & & 这里给出一个直观的图形，这个图形描述了5人报数问题的求解。最外层的环表示5人求解问题，向内依次递减，最内层的环表示1人报数问题。在最外层的环中报到3的人被杀，这个位置就变成不可用（图中用蓝色表示），之后进入第4环，从下一个可用位置开始标号。重复这一过程，直到进入最内层的环。把最内层环中幸存者位置映射到最外层，问题就解决了。5人报数问题的幸存者在位置3上。
& & & & 看看现在的程序：
#include &stdio.h&
#define TOTAL 41
#define COUNT 3
int main() {
int f = 0;
for (i = 2; i &= TOTAL; ++i)
f = (f + COUNT) %
printf(&The survivor is in position %d\n&, f + 1);
}& & & & 现在我们的程序既简洁优美，效率又高。
& & & & 关于约瑟夫环问题，我们就先讨论这么多。文章最后再给大家留一个问题：如果可以有多个幸存者，你能把他们的位置全都找出来吗？
我的热门文章
即使是一小步也想与你分享