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

约瑟夫问题

---

 

约瑟夫环问题是一个数学应用题：已知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 例题

---

 

题目描述

 

解题思路：

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置为-1i = -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