约瑟夫环的4种解法（数学思维法详解）
约瑟夫环的4种解法（数学思维法详解）
约瑟夫环问题是一个经典的算法问题，源自犹太历史学家约瑟夫斯的传说。本文将详细介绍约瑟夫环问题的四种解法，包括循环队列、循环链表、模拟链表和数学思维法。通过对比不同解法的时间复杂度和实现效果，帮助读者深入理解这一问题的解决思路。
题目背景
据说著名犹太历史学家Josephus（弗拉维奥·约瑟夫斯）有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。
Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。（来源《百度百科》）
直接法编程
伪代码
int n,m；
int 数组
数组初始化；
while(1)
每m个删除一个，直到剩下一个跳出循环；
一、循环队列
循环队列程序最好设计，也是时间复杂度最高的，如果单纯使用队列的话，不知道要开多大的空间，但如果使用循环队列的话，只需要n个空间就好啦。
这里直接上代码，大家可以参考注释理解，其实和数组的方法大差不差。
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n,m,flag=1;
scanf("%d %d",&n,&m);//输入n，m
int s=n;//s记录剩余多少个人
int *q;//队列大小为n
q=(int*)malloc(n*sizeof(int));
int head = 0;//队头
int tail = n-1;//队尾
for (int i = 0; i <n; i++)//初始化
{
q[i]=i+1;
}
while(1)
{
//打印队首并将队首出队
if (flag%m!=0)//不需要淘汰，队头出队加入队尾
{
tail++;
tail=tail%n;//循环队列，防止溢出。
q[tail]=q[head];//队头加入队尾
}
else if (head==tail)
{
// printf("q[tail]=%d",q[tail]);
printf("%d",q[head]);
break;
}
else if (flag%m==0)//需要淘汰，队头出队
{
// printf("head=%d\n",q[head]);
s--;//剩余人数减一
flag=(m/s)*s;//减少循环
}
head++;//队头出队
flag++;
head=head%n;//循环出队，防止溢出
// if (head==0)head++;
//先将新队首的数添加到队尾
//再将队首出队
// head++;
}
free(q);
return 0;
}
二、循环链表
循环链表，在淘汰部分与队列有些许不同，在淘汰的时候，链表需要指向需淘汰的data前一个，这与链表，只能单方向寻找有关，其实就是链表的删除。
注意当需要删除的时候，就不需要指向下一个结点了，因为删除已经算一次了。
#include<stdio.h>
#include<stdlib.h>
struct node //定义链表
{
int data;
struct node *next;
};
int main()
{
struct node *head=NULL, *p=NULL, *q=NULL, *t=NULL,*tail=NULL;
int i,n,m,flag=1;
scanf("%d %d",&n,&m);
head =NULL;
for ( i = 0; i < n; i++) //初始化
{
p=(struct node *)malloc(sizeof(struct node)); //分配动态内存，给p分配一个地址
p ->data=i+1; //将a存入这个地址
p->next=NULL; //分配下一个节点
if (head ==NULL)
{
head=p;
}
else
q->next=p;
q=p;
if (i==n-1)
{
tail=q;
q->next=head;
}
}
t=tail; //指向末尾
while(t!=NULL) //将数据存入链表
{
if (flag%m==0)//需要删除
{
p=t->next;
t->next=t->next->next;//删除
// free(p);//释放删除节点空间
n--;
flag=(m/n)*n;//减少循环
if (n==1)//剩余一个
{
printf("%d",t->next->data);
break;
}
}
else//不需要删除
t=t->next; //指向下一个节点
flag++;
}
free(p);
p=NULL;
return 0;
}
三、模拟循环链表
模拟链表的思路和循环链表一模样，只不过是通过数组下标模拟地址罢了，这里直接贴上代码，其实这三种写出来一种，其它的就没问题啦。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
int n,m;
int flag=1;
scanf("%d%d",&n,&m);
int *data;//存储数据
int *right;//模拟地址
data=(int *)malloc((n+1)*sizeof(int));
// msmset(data,0,n*sizeof(int));
right=(int *)malloc((n+1)*sizeof(int));
// msmset(right,0,n*sizeof(int));
int k=n;
for (int i = 1; i <= n; i++)//初始化
{
data[i]=i;
if (i==n)//最后一个指向第一个，构成循环链表
right[i]=1;
else
right[i]=i+1;
}
while (1)
{
if (flag%m==0)
{
// printf("out_> %d\n",data[right[k]]);
right[k]=right[right[k]];//指向下一个的下一个
// flag++;
n--;
flag=(m/n)*n;//减少循环
if (n==1)
{
printf("%d",data[right[k]]);
break;
}
}
else
{
k=right[k];//下一个结点；
}
flag++;
}
free(data);
free(right);
return 0;
}
数学思维
首先，本套代码我们要达成几个共识：
- 把约瑟夫环看成下标从0开始排的一个序列。
- 每删除一个数之后，形成新的约瑟夫环，删除数的下一个数下标为0。
- 最后剩余一个数，在本轮约瑟夫环的下标为0。
根据这些共识，再采用逆向思维来解决这道题，既然最后肯定是剩余一个，那我们就从它出发，从它在本轮约瑟夫环的下标推导出上一轮约瑟夫环中的下标，然后依次推导出它在第一轮约瑟夫环的下标，就得到了我们想要的结果。
下面我们举一个例子，输入“10 3”。（如图为正向推导过程）
可以很直观的看到，最后一轮剩余的那个数在第一轮中的下标为3，故它的编号为4。
伪代码
函数（）
{
if（为最后一个约瑟夫环）
return 0；
else
return 第一轮约瑟夫环的下标递推公式
}
首先，我们来找一下递归函数终止的条件，即"为最后一个约瑟夫环",这里采用的方法是用一个参数a来代表，即函数（int a）；
然后就是下标递推公式，通过上边的例题，首先可以发现对于一些初始下标大的数，它们追寻下一轮的下标比上一轮小3个。
而对哪些初始下标下的数，例如0，它减3个则为-3，而它的实际是7，那么是怎么来的呢，第一个约瑟夫环有10个数，而第二个就只剩下9个，我们把这9个数形成一个环，类似于补码，便可得到，0-3=7（0，9，8，7）。到这里我们便找到了规律。
用公式可以表示为：f（a-1）=((f（a）-m)+a)%a;
通过这个公式，我们便能得到，上一个环的下标经过变换得到下一个环的下标值。但是我们并不知道哪一个值能走到最后，我们只能保证最后只有一个值，所以我们要得到逆推的公式，即：
f(a)=(f(a-1)+m)%a。
在递归函数里，我们正向得到函数式，让逆向得到结果，代码如下：
#include<stdio.h>
int n,m;
int jr(int a)//Joseph Ring 约瑟夫环问题（数学思维和逆向思维）
{
if (a==1)//为jr（1，m）即这个数在新的约瑟夫环中一定下标为零
{
return 0;
}
return (jr(a-1)+m)%a;//重点
}
int main()
{
scanf("%d%d",&n,&m);
printf("%d",jr(n)+1);
return 0;
}
总结
本文描述了常见的四种解法，其中，在直接法编程中，时间复杂度的排序为：循环队列>循环链表>模拟链表，所以模拟链表的时间复杂度是最低的，但是在蓝桥杯的这道约瑟夫环中，依然只能通过33.3%，尽管用flag=(m/n)*n进行了优化。
而用数学思维做，则快了好多，能够100%通过。