约瑟夫环问题(循环链表)

题目描述：n只猴子要选大王，选举方法如下：所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。

输入数据：猴子总数n，起始报数的猴子编号k，出局数字m

输出数据：猴子的出队序列和猴子大王的编号

代码修改了一天才完成，第一次是用多个函数写的，但是发觉C语言没有引用参数这个特性，使得形参指针不能被直接修改，必须靠返回值来修改才行，这样太麻烦了...于是第二次写的时候就没有使用函数，直接在main()里完成了循环链表的操作，感觉应该没什么问题，哪位大牛看出问题跟我说下，thx...

 

 

/*
约瑟夫问题(猴子选大王)
循环链表C语言实现
Slyar 2009.3.31
http://www.slyar.com
*/
 
#include <stdio.h>
#include <stdlib.h>
 
/* 定义链表节点类型 */
typedef struct node
{
    int data;
    struct node *next;
}linklist;
 
int main()
{
    int i, n, k, m, total;
    linklist *head, *p, *s, *q;
    /* 读入问题条件 */
    printf("请输入猴子的个数:");
    scanf("%d", &n);
    printf("请输入要从第几个猴子开始报数:");
    scanf("%d", &k);
    printf("请输入出局数字:");
    scanf("%d", &m);
    /* 创建循环链表，头节点也存信息 */
    head = (linklist*) malloc(sizeof(linklist));
    p = head;
    p->data = 1;
    p->next = p;
    /* 初始化循环链表 */
    for (i = 2; i <= n; i++)
    {
        s = (linklist*) malloc(sizeof(linklist));
        s->data = i;
        s->next = p->next;
        p->next = s;
        p = p->next;
    }
    /* 找到第 k 个节点 */
    p = head;
    for (i = 1; i < k; i++)
    {
        p = p->next;
    }
    /* 保存节点总数 */
    total = n;
    printf("\n出局序列为:");
    q = head;
    /* 只剩一个节点时停止循环 */
    while (total != 1)
    {
        /* 报数过程，p指向要删除的节点 */
        for (i = 1; i < m; i++)
        {
            p = p->next;
        }
        /* 打印要删除的节点序号 */
        printf("[%d] ", p->data);
        /* q 指向 p 节点的前驱 */
        while (q->next != p)
        {
            q = q->next;
        }
        /* 删除 p 节点 */
        q->next = p->next;
        /* 保存被删除节点指针 */
        s = p;
        /* p 指向被删除节点的后继 */
        p = p->next;
        /* 释放被删除的节点 */
        free(s);
        /* 节点个数减一 */
        total--;
    }
    /* 打印最后剩下的节点序号 */
    printf("\n\n猴子大王为第 [%d] 号\n\n", p->data);
    free(p);
    //system("pause");
    return 0;
}

 

第二种解法：

约瑟夫环问题是一道经典的数据结构题目
问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
一般我们采用一个循环队列来模拟约瑟夫环的求解过程，但是如果n比较大的时候，采用模拟的方式求解，需要大量的时间来模拟退出的过程，而且由于需要占用大量的内存空间来模拟队列中的n个人，并不是一个很好的解法。
在大部分情况下，我们仅仅需要知道最后那个人的编号，而不是要来模拟一个这样的过程，在这种情况下，可以考虑是否存在着一种数学公式能够直接求出最后那个人的编号。

我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
我们先看第一个人出列后的情况，显而易见，第一个出列的人的编号一定是m%n-1,这个人出列后，剩下的n-1个人组成了一个新的约瑟夫环，这个约瑟夫环的第一个人在最开始的环中的编号是k=m%n（就是第一个出列的人的下一个）
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
事实上，可以把这个环又映射成为一个新的环：
k  --- 0
k+1 --- 1
k+2 --- 2
...  ....
k-2 -- n-1
可以看出，这就是原问题中把n替换成n-1的情况，假设我们已经求出来在这种情况下最后胜利的那个人的编号是x，那个倒推回去的那个人的编号就正好是我们要求的答案，显而易见，这个编号应该是(x+k)%n
那么如何知道n-1个人下面的这个x呢，yes，就是n-2个人情况下得到的x'倒推回去，那么如何知道n-2情况下的x'呢，当然是求n-3个人，这就是一个递归的过程
f(1) = 0（f(1)就是现在还剩下1个人，那么无论m为几，这个人总会出列，因此f(1)=0)
f(n) = (f(n-1)+m)%n
那么我们要求f(n)，就从f(1)倒推回去即可

01.int JosephusProblem_Solution4(int n, int m) 02.{ 03. if(n < 1 || m < 1) 04. return -1; 05. 06. vector<int> f(n+1,0); 07. for(unsigned i = 2; i <= n; i++) 08. f[i] = (f[i-1] + m) % i; 09. 10. return f[n]; 11.}