Josephus problem（约瑟夫问题，丢手绢问题）

蔚落 2021-11-26 12:26 348阅读 0赞

## 约瑟夫问题 ##

--------------------

##### 约瑟夫环问题是一个数学应用题：已知n个人（以编号1，2，3.....，n)围坐在一张圆桌的周围。从编号为k的人开始报数，数到m的那个人出列：他的下一个人又从1开始报数，数到m的那个人又出列，以此规律重复下去，直到圆桌的人全部出列。通常解决这类问题时我们把编号从0-n-1，最后+1即为原问题的解。 #####

### >算法描述: ###

###### **约瑟夫环运作如下：** ######

**1、一群人围在一起坐成环状**

**2、从某个编号开始报数（如：K）**

**3、数到某个数（如：M）的时候，此人出列，下一个人重新报数**

**4、一直循环，直到所有人出列 ，约瑟夫环结束**

### >解决此类问题的解法 ###

##### C语言 模拟递归法 #####

##### 公式推导法 #####

#include <stdio.h>
    #include <stdlib.h>
    struct _Node
    {
       int data;
       struct _Node *next;
    };
    typedef struct _Node node_t;
    typedef struct _Linklist
    {
       node_t *phead;
       node_t *ptail;
       int len;
    } Linklist;
    static node_t *GetNode(int i) //新建并初始化节点
    {
       node_t *pNode;
       pNode = (node_t *)malloc(sizeof(node_t));
       if (!pNode)
       {
           printf("Error,thememoryisnotenough!\n");
           exit(-1);
       }
       pNode->data = i;
       pNode->next = NULL;
       return pNode;
    }
    void init_list(Linklist *plist) //用第一个节点初始化循环单链表
    {
       node_t *p;
       p = GetNode(1);
       //printf("TheNewNodeis:%d\n",p->data);//****TEST****
       plist->phead = p;
       plist->ptail = p;
       p->next = plist->phead;
       plist->len = 1;
    }
    static void Create_List(Linklist *plist, int n) //把其余数据添加到循环单链表中
    {
       int i = 0;
       node_t *pNew;
       for (i = 2; i <= n; i++)
       {
           pNew = GetNode(i);
           /********TEST********
           printf("TheNewNodeis:%d\n",pNew->data);
           ********TEST********/
           plist->ptail->next = pNew;
           plist->ptail = pNew;
           pNew->next = plist->phead;
           plist->len++;
       }
       printf("Completesthee-waycirculationchaintablethefoundation!\n");
    }
    void Print_List(Linklist *plist) //输出链表内容
    {
       node_t *pCur = plist->phead;
       do
       {
           printf("The%dperson.\n", pCur->data);
           pCur = pCur->next;
       } while (pCur != plist->phead);
       printf("ThelengthoftheList:%d\n", plist->len);
    }
     
    // 约瑟夫回环函数实现
     
    void joseph(Linklist *plist, int m) //约瑟夫回环函数实现
    {
       node_t *pPre = plist->ptail;
       node_t *pCur = plist->phead;
       int i;
       while (plist->len != 1)
       {
           i = 0;
           while (i < m - 1)
           {
               pPre = pPre->next;
               i++;
           }
           pCur = pPre->next;
           pPre->next = pCur->next;
           free(pCur);
           plist->len--;
       }
       printf("Thelastoneis:%d\n", pPre->data);
    }
    int main()
    {
       int n = 0;
       printf("PleaseinputtheLengthoftheCirclelist:");
       scanf("%d", &n);
       int m = 0;
       printf("PleaseinputtheStoppoint:");
       scanf("%d", &m);
       Linklist pList;
       init_list(&pList);
       Create_List(&pList, n);
       Print_List(&pList);
       joseph(&pList, m);
       return 0;
    }

## OJ 例题 ##

--------------------

# #

##### 题目描述 #####

![1632445-20190617141459679-302083649.png][]

### 解题思路： ###

#### 1<=n<1000发现数据量不大，直接模拟游戏求出最后一个人 ####

##### 下面是非递归使用for循环代码 #####

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        int n;
        while (scanf_s("%d", &n) == 1)
        {
            int len, i, j=1;
            int count = n;//当前存在的人数 当count == 1剩下最后一个人 即为答案
            int a[1002] = { 0 };//初始化模拟数组
            for (i = 0; i < n; i++)//人数从1~n数组标示从0~n-1
            {
                if (count == 1)
                    break;
                if (a[i] == 0)//a[i]==1表示这个人已经退出游戏
                {
                    if (j % 2 == 0)
                    {
                        a[i] = 1;
                        count--;//删掉一个人
                    }
                    else
                    {
                        if (i + 1 >= n)//数组循环即 当i往下大于人数n时需要从0开始 但是由于是for 循环i会++ 所以i置为-1
                            i = -1;
                    }
                    j++;
                }
                else
                {
                    if (i + 1 >= n)
                        i = -1;//同上
                }
                if (i == n-1)
                    i = -1;//同上
            }
            for (i = 0; i < n; i++)
                if (a[i]==0)
                    printf("%d\n", i + 1);
        }
    }

非递归使用while循环

#include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
       int n;
       while(scanf("%d",&n)==1)
       {
           int i=1,len,a[1006]={
        0};
           int flag=1;
           len=n-1;
           while(len)
           {
               if(a[i]==0)
               {
                   if(flag==1)
                   {
                       i++;
                       if(i>n)
                        i=1;
                       flag=2;
                   }
                   else
                   {
                       a[i]=1;
                       i++;
                       if(i>n)
                        i=1;
                       flag=1;
                       len--;
                   }
               }
               else
               {
                   i++;
                   if(i>n)
                      i=1;
               }
           }
           for(i=1;i<=n;i++)
            if(a[i]==0)
                printf("%d\n",i);
       }
    }

题目数字较大的时候可以采用公式推导法，参考下面链接的博客

[https://blog.csdn.net/u011500062/article/details/72855826][https_blog.csdn.net_u011500062_article_details_72855826]

转载于:https://www.cnblogs.com/1328497946TS/p/11038836.html

[1632445-20190617141459679-302083649.png]: /images/20211126/a25a1b4a0077486ca6a384ff4a3cb67d.png
[https_blog.csdn.net_u011500062_article_details_72855826]: https://blog.csdn.net/u011500062/article/details/72855826