小猪的数据结构辅助教程——2.5 经典例子：约瑟夫问题的解决

数据结构

约瑟夫问题的解析

关于问题的故事背景就不提了，我们直接说这个问题的内容吧：

一堆人，围成一个圈，然后规定一个数N，然后依次报数，当报数到N，这个人自杀，其他人鼓掌！啪啪啪，
接着又从1开始报数，报到N又自杀...以此类推，直到死剩最后一个人，那么游戏结束！

这就是问题，而我们用计算机模拟的话，用户输入:N(参与人数)，M(第几个人死)，结果返回最后一个人！
类似的问题有跳海问题，猴子选王等，下面我们就以N = 41和M = 3作为输入参数，使用不同的方法来
解决约瑟夫问题！

1.使用C语言的数组来解决

流程解析：

这里我们用数组来模拟报数的流程，使用一个标记数组，1代表人没死，0代表已经死了！

• Step 1：获取人数，第几个人死，初始化标记数组，将数组置为1
• Step 2：使用一个变量last来统计剩下没死的人数 > 1作为循环条件
  1）判断标记数组中的元素是不是1，1代表没死，没死继续循环，这里很巧妙地用了这段代码：
  if(!tag[i%n])continue; 如果执行这个说明tag[i%n] == 0说明这B前面已经死了，而不直接
  用i，而是用i % n是因为，可能出现n少于m的情况！
  2）判断是否移动了m个人，是的话把这个人杀掉，就是数组对应下标设置为0，同时打印输出，
  统计人数的变量 -1；否则：判断是否移动m个人的变量++;
• Step 3：使用循环链表遍历数组，找到不为0的元素，打印输出下标即可

代码实现：

#include <stdio.h>
int main()
{
    //参数: n(人数),m(第m个人死),last(剩余的人数)
    int i,j,n,m,last;
    int tag[100];
    printf("输入参加的人数:\n");  
    scanf("%d",&n);  
    printf("输入每隔多少死一个人:\n");  
    scanf("%d",&m);
    printf("\n准备报数！\n\n");     
    //初始化数组
    for(i = 0;i < n;i++)
    {
        tag[i] = 1; 
    } 
     //开始报数
    j = 1;
    last = n;
    for(i = 0;last > 1;i++)
    {
        if(!tag[i%n])continue;
        if(j == m)
        {
            j = 1;
            tag[i%n] = 0;
            printf("第%d个人自杀了，大家快鼓掌！啪啪啪！\n",(i%n)+1);
            last--;
        }
        else j++;   
    } 
    for(i = 0;i < n;i++)if(tag[i])break;
    printf("第%d个人活下来了！\n",i+1);
    return 0;
}

运行截图：

2.使用循环链表来解决

上面使用数组来模拟报数，好像不太容易理解，要不我们用上一节学到的循环链表来嗨一下，
循环链表是一个环，我们只要把报到的结点删除掉，然后重新报数...最后剩下的结点就是没死
的那个了！下面我们写代码来实现下！
PS：代码还是蛮简单的，有不理解，可以自己画下图~

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//定义循环链表的存储结构
typedef struct LNode
{
    int data;         //数据域
    struct LNode *next;   //指针域 
}LNode;  
typedef struct LNode *LinkList;
//定义循环链表的初始化方法
LinkList createList(int n)
{
    printf("\n初始化循环链表\n\n"); 
    LinkList head,s,p;
    int i = 1;
    head = (LinkList)malloc(sizeof(LNode));
    p = head;
    if(n != 0)
    {
        while(i <= n)
        {
            s = (LinkList)malloc(sizeof(LNode));
            s ->data = i++;  //为链表初始化，第一个结点值为1，第二个为2这样以此类推
            p ->next = s;
            p = s;
        }
         s->next = head->next;  
    }
    free(head);  
    return s->next;  
}
int main()
{
    int n,m,i;
    printf("输入参加的人数:\n");  
    scanf("%d",&n);  
    printf("输入每隔多少死一个人:\n");  
    scanf("%d",&m);
    LinkList p = createList(n);
    LinkList temp;
    m %= n;  //为了防止报数的人大于参与的人，求余可以理解为重头开始
    while(p != p ->next)
    {
        for(i = 1;i < m -1;i++)
        {
            p = p ->next; 
        }
        printf("第%d个人自杀了\t",p ->next->data);
        //删除第m个结点
        temp = p ->next;
        p ->next = temp ->next;
        free(temp);
        p = p ->next; 
    } 
    printf("\n第%d个人活下来了！\n\n", p->data );    
    return 0;  
}

运行截图：

3.数学方法来解决

上面讲述的两种解决约瑟夫问题的方法都是模拟一个报数的流程，对付一些小的数据量
还可以，但是假如我们输入的数据量很大的时候，就会显得很笨重，我们需要使用一些
数学策略来解决这个问题，有这样一个递推公式：
f[ 1 ]=0;
f[ i ]=(f[ i-1 ]+m)%i; (i>1)
而我们根据上面这个递推公式，写出如下代码：

实现代码：

#include <stdio.h>  
int main()  
{  
  int n, m, i, s=0;  
  printf ("N M = "); 
  scanf("%d%d", &n, &m);  
  for (i=2; i<=n; i++)s=(s+m)%i;  
  printf ("最后一个剩下的人: %d\n", s+1);  
  return 0;  
}  

运行截图：

卧槽，这是何等的卧槽，就for(i=2; i<=n; i++)s=(s+m)%i; 这样一个东西就得出结果了？
我选择死亡....
好吧，又一次体会到数学的流弊之处，果然玩算法的数学必须得好，笔者的数学太屎，推导不出
k' = (k + m)%i这条公式...这里贴下网上别人的解释吧：

4.约瑟夫问题的增强版

题目：
假如现在是不固定报数，而是每人次优一个密码，从第一个持有密码的人开始，把他作为
报数的M值，从第一个数开始报数，当报数到M时候，报数的人出列，拿出他的密码，把密码
作为报数的M值，接着依次下去..直到全部人出列，游戏结束！

代码实现：

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100  
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
//定义循环链表的存储结构
typedef int Status; 
typedef struct LNode
{
    int id;         //第几个人
    int pawd;       //密码 
    struct LNode *next;   //指针域 
}LNode;  
typedef struct LNode *LinkList;
//1.定义一个创建结点的方法
LNode *GetNode(int pid,int ppawd)
{
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode));
    if(!p)return ERROR;
    p ->id = pid;
    p ->pawd = ppawd;
    p ->next = NULL;
    return p;
} 
//2.创建循环单链表
Status ListCreate(LinkList L,int n)
{
    int i,ppawd;
    LinkList p,q;
    for(i = 1;i <= n;i++)
    {
        printf("请输入第%d个人持有的密码：",i);
        scanf("%d",&ppawd);
        p = GetNode(i,ppawd);
        if(L == NULL)
        {
            L = q = p;
            q ->next = L;
        }else{
            p ->next = q ->next;
            q ->next = q;
            q = p;
        }
    }   
    printf("完成单向循环链表的创建!\n");
    return OK;
}  
//3.判断循环单链表是否为空
Status ListEmpty(LinkList L)
{
    if(!L)return TRUE;
    return FALSE;
} 
//4.打印循环链表当前的所有元素
void ListPrint(LinkList L)
{
    LinkList p = L;
    if(ListEmpty(L))return;
    do{
        printf("第%d个人的密码为：%d\n",p ->id,p ->pawd);
        p = p ->next;
    }while(p != L);
    getchar();
} 
//5.开始游戏
void StartGame(LinkList L,int startpawd)
{
    int i,isFlag = 1;
    LinkList p,q,r;
    p = q = L;
    //让p指向尾部结点，为删除做准备
    while(p ->next != L)p = p ->next;
    while(isFlag)
    {
        for(i = 1;i < startpawd;i++)
        {
            p = q;
            q = q ->next;
        }
        if(p == q)isFlag = 0;
        r = q;  //删除q指向的结点，有人出列
        p ->next = q ->next;
        q = q->next;
        startpawd = q ->pawd;
        printf("第%d个人出列，他手持的密码是：%d\n",r ->id,r ->pawd);
        free(r); 
    } 
    L = NULL;
    getchar();
} 
int main()
{
    int n, m;
    LinkList L = NULL;
    while(1)
    {
      printf("请输入人数n（最多%d个）: ", MAX_SIZE);  
        scanf("%d", &n);         
        printf("和初始密码m: ");  
        scanf("%d", &m);  
        if (n > MAX_SIZE)  
        {  
            printf("人数太多，请重新输入！\n");  
            continue;  
        }  
        else  
            break;      
    }
    ListCreate(L,n);
    printf("\n------------ 循环链表原始打印 -------------\n");  
    ListPrint(L);  
    printf("\n-------------删除出队情况打印 -------------\n");  
    StartGame(L, m);  
    return 0;
}

运行截图：

5.本节代码下载

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu1.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu2.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu3.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/List/yueshefu4.c