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

约瑟夫问题

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

一、算法描述:

约瑟夫环运作如下：

一群人围在一起坐成环状
从某个编号开始报数（如：K）
数到某个数（如：M）的时候，此人出列，下一个人重新报数
一直循环，直到所有人出列，约瑟夫环结束

二、解决此类问题的解法

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(-);

   }

   pNode->data = i;

   pNode->next = NULL;

   return pNode;

}

void init_list(Linklist *plist) //用第一个节点初始化循环单链表

{

   node_t *p;

   p = GetNode();

   //printf("TheNewNodeis:%d\n",p->data);//****TEST****

   plist->phead = p;

   plist->ptail = p;

   p->next = plist->phead;

   plist->len = ;

}

static void Create_List(Linklist *plist, int n) //把其余数据添加到循环单链表中

{

   int i = ;

   node_t *pNew;

   for (i = ; 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 != )

   {

       i = ;

       while (i < m - )

       {

           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 = ;

   printf("PleaseinputtheLengthoftheCirclelist:");

   scanf("%d", &n);

   int m = ;

   printf("PleaseinputtheStoppoint:");

   scanf("%d", &m);

   Linklist pList;

   init_list(&pList);

   Create_List(&pList, n);

   Print_List(&pList);

   joseph(&pList, m);

   return ;

}

三、OJ 例题

题目描述

解题思路：

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

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

#include <stdio.h>

#include <stdlib.h>

int main()

{

    int n;

    while (scanf_s("%d", &n) == )

    {

        int len, i, j=;

        int count = n;//当前存在的人数 当count == 1剩下最后一个人 即为答案

        int a[] = {  };//初始化模拟数组

        for (i = ; i < n; i++)//人数从1~n数组标示从0~n-1

        {

            if (count == )

                break;

            if (a[i] == )//a[i]==1表示这个人已经退出游戏

            {

                if (j %  == )

                {

                    a[i] = ;

                    count--;//删掉一个人

                }

                else

                {

                    if (i +  >= n)//数组循环即 当i往下大于人数n时需要从0开始 但是由于是for 循环i会++ 所以i置为-1

                        i = -;

                }

                j++;

            }

            else

            {

                if (i +  >= n)

                    i = -;//同上

            }

            if (i == n-)

                i = -;//同上

        }

        for (i = ; i < n; i++)

            if (a[i]==)

                printf("%d\n", i + );

    }

}

非递归使用while循环

#include <stdio.h>

#include <stdlib.h>

int main()

{

   int n;

   while(scanf("%d",&n)==)

   {

       int i=,len,a[]={};

       int flag=;

       len=n-;

       while(len)

       {

           if(a[i]==)

           {

               if(flag==)

               {

                   i++;

                   if(i>n)

                    i=;

                   flag=;

               }

               else

               {

                   a[i]=;

                   i++;

                   if(i>n)

                    i=;

                   flag=;

                   len--;

               }

           }

           else

           {

               i++;

               if(i>n)

                  i=;

           }

       }

       for(i=;i<=n;i++)

        if(a[i]==)

            printf("%d\n",i);

   }

}

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

https://blog.csdn.net/u011500062/article/details/72855826

巴特西

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

约瑟夫问题

一、算法描述:

二、解决此类问题的解法

三、OJ 例题

最新文章

热门文章