约瑟夫环

约瑟夫环实验报告约瑟夫环是一个经典的数学问题，它涉及到一个有趣的游戏。

这个游戏的规则是：有N个人站成一圈，从某个人开始，每报数到第M个人，就将该人从圈中移出去，再从下一个人开始重新报数，如此循环，直到只剩下一个人为止。

那么，我们将通过实验来探究一下约瑟夫环的性质和一些有趣的现象。

首先，我们设定了一组实验条件。

假设有10个人，从1到10编号，报数为3。

我们选择从编号为1的人开始报数，然后每次报数到第3个人。

接下来，我们按照约瑟夫环的规则进行实验。

实验开始后，我们可以观察到一系列有趣的现象。

首先，被淘汰的人并不会立即离开圈子，而是继续留在原位，但不再参与后续的报数和淘汰。

当每次报数到达M的倍数时，即到了第3个人、第6个人、第9个人等等，这些人就会被逐渐淘汰出圈。

在实验过程中，我们发现了一个有趣的规律。

剩下的人似乎总是固定按照一定的顺序被淘汰。

为了更好地观察这个规律，我们进行了多组实验，并记录了淘汰顺序。

首先，在报数为3的情况下，我们记录了当有10个人时的淘汰顺序。

开始时，第1轮淘汰的是第3个人，然后是第6个人，之后是第9个人。

接着，轮到第2个人被淘汰，然后是第7个人，最后是第1个人。

可见，在这个实验条件下，被淘汰的顺序是3、6、9、2、7、1。

我们可以看到，在最后几轮淘汰时，被淘汰的顺序逐渐回到了初始的编号1。

接着，我们将实验条件略作改变，观察是否会出现相似的淘汰顺序。

这次，我们依然有10个人，报数为4。

开始时，第1轮淘汰的是第4个人，然后是第8个人，之后是第2个人。

接着，轮到第5个人被淘汰，然后是第10个人，最后是第6个人。

通过这次实验，我们可以观察到一些不同之处。

尽管淘汰的顺序在最后几轮回到了初始的编号1，但淘汰的间隔变得更长了，而且整体的淘汰顺序也有了一定的变化。

通过对约瑟夫环实验的多次观察和记录，我们可以总结出一些结论。

首先，淘汰的顺序呈现出周期性，并在最后几轮回到了初始的编号。

其次，在不同的实验条件下，淘汰的规律可能会有所不同。

约瑟夫环的知识点总结约瑟夫环这个问题不仅在古代受到了广泛的关注，而且在现代数学中也有着重要的地位。

它涉及到了排列、递推、循环和递归等多个数学概念，并且有着一些有趣的数学特性。

因此，学习约瑟夫环不仅能够增加我们对于数学问题的理解，而且也可以提高我们的数学思维能力。

接下来，我们将从几个方面对约瑟夫环进行深入的讨论。

1. 约瑟夫环的历史约瑟夫环最早出现在约瑟夫斯的《犹太古记》中，他描述了犹太人在与罗马军队的战斗中围攻马萨达城的情景。

根据《犹太古记》的记载，当罗马军队攻陷了马萨达城后，大约960名男子决定宁死不从。

于是，他们站成一个圈，每隔两个人就有一个杀掉，直到最后只剩下一个人。

而这个幸存者恰恰就是约瑟夫斯本人。

因此，这个问题就得名为约瑟夫环。

除了这个故事之外，约瑟夫环在古代数学文献中也有着多次的提及。

例如，中国古代数学家秦九韶在其著作《数书九章》中也提到了这个问题。

他利用递推的方法解出了约瑟夫环的一般解，并推广到了更一般的情况。

自古代以来，约瑟夫环一直受到数学家们的关注，他们提出了很多不同的方法来解决这个问题。

而到了现代，约瑟夫环在计算机科学和密码学中也有着广泛的应用。

因此，约瑟夫环问题可以说是一个古老而又具有重要意义的数学问题。

2. 约瑟夫环的一般解在数学中，我们可以用递推的方法对约瑟夫环进行求解。

假设有N个人站成一圈，编号从0到N-1，而每隔M个人就有一个人出列。

那么一个简单直接的方法就是用递归来求解。

具体来说，我们可以定义一个递归函数f(n, m)，表示N个人中最后存活下来的那个人的编号。

那么这个函数的递归关系可以如下定义：f(n, m) = (f(n-1, m) + m) % n其中f(1, m) = 0，表示只有一个人时的情况。

通过递归的方法，我们可以得到约瑟夫环的一般解。

而根据这个递归关系，我们还可以得到一些有趣的数学性质。

例如，我们可以求解约瑟夫环在给定N和M的情况下的解，而不需要实际模拟整个过程。

约瑟夫环知识点总结1. 约瑟夫环的数学模型约瑟夫环可以用数学的方式进行建模和解决。

通常情况下，我们把约瑟夫环的问题理解为一个数学公式的求解。

假设n个士兵分别编号为1、2、3、...、n，m为出列的间隔数。

首先，我们可以得到第一个出列的士兵编号为(m-1)%n+1，例如当n=7，m=3时，第一个出列的士兵为(3-1)%7+1=3。

之后，每次出列后的编号变换规律为：下一个出列士兵的编号为前一个出列士兵编号加上m在n取模后的结果，并且再对n取模，即f(i)=f(i-1)+m)%n。

以上公式是解决约瑟夫环问题的核心，因为根据这个公式可以有效地计算出每一轮出列的士兵的编号。

然后我们只需要循环迭代这个公式，直到最后只有一个士兵为止，这个士兵的编号就是最后的结果。

2. 约瑟夫环的递归解法除了上述的数学模型，还可以使用递归的方法来解决约瑟夫环的问题。

递归是一种非常高效的解决问题的方法，适用于很多数学问题，包括约瑟夫环的计算。

递归方法的求解思路是：先假设已知了n-1个士兵的约瑟夫环问题的解f(n-1, m)，那么我们要求的n个士兵的约瑟夫环的解f(n, m)可以通过以下方式推导得到。

首先，第一个出列的士兵编号为(m-1)%n+1，之后剩下的n-1个士兵重新排列成一个圆圈，编号重新从1到n-1。

将这n-1个士兵的解f(n-1, m)映射到n个士兵的解f(n, m)上，此时，再回到上述的数学模型进行计算，找到最终的结果。

递归的思路虽然清晰，但是在实际求解的过程中，由于递归的不断嵌套，计算量会非常庞大，不适合解决大规模的约瑟夫环问题。

3. 约瑟夫环的迭代解法在解决实际问题的时候，我们更多地使用迭代的方法来求解约瑟夫环的问题。

迭代的思路是从最简单的情况开始，然后不断迭代得到更加复杂的情况的解。

对于约瑟夫环问题，迭代的思路是逐步得出每一轮出列的士兵的编号并记录下来，直到剩下最后一个士兵为止。

通常情况下，我们会使用一个数组或者链表来保存每一轮出列的士兵的编号，最后得出最后一个士兵的编号。

实验1 约瑟夫环问题背景约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

原题：用户输入M,N值，N个人围成一个环，从0号人开始数,数到M,那个人就退出游戏游戏，直到最后一个人求最后一个剩下的人是几号？问题描述：设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从开始顺时针报数．报m的人(m为正整数)．令其出列。

然后再从他的下一人开始，重新从1顺时针报数，报m的人，再令其出列。

如此下去，直到圈中所有人出列为止。

求出列编号序列。

基本要求：需要基于线性表的基本操作来实现约瑟夫问题需要利用数组来实现线性表测试数据：输入：10,3输出：3 6 9 2 7 1 8 5 10 4选做内容：（1）使用单链表来实现之（2）使用循环链表来实现之实验中使用了数组以及链表的操作，来实现对约瑟夫环的解答。

一、先来讲一讲对数组的实现的思路：数组的实现是一种很常规的方法。

这里必须要设置一个临时变量t，在第一轮的循环中，t=0而且在这一轮中要出列的数字是（t+m-1）%i，举例来说：当n=10,m=3时，t=2,4,6,1,3,0,1,1,0,那么就可以知道最后剩下的是4了。

二、再来讲一讲链表的实现方式：在链表的改写中使用到了这几个函数：append（），next（），remove（）和prve（）;这里实现的思路还是比较简单的。

当输入了n个数据后，使用append（）函数连接起来，然后用一number来记录这个节点的代表次数。

约瑟夫环问题⼩结⼀问题描述约瑟夫环问题的基本描述如下：已知n个⼈(以编号1，2，3...n分别表⽰)围坐在⼀张圆桌周围。

从编号为1的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，要求找到最后⼀个出列的⼈或者模拟这个过程。

⼆问题解法在解决这个问题之前，⾸先我们对⼈物进⾏虚拟编号，即相当于从0开始把⼈物重新进⾏编号，即⽤0,1,2,3,...n-1来表⽰⼈物的编号，最后返回的编号结果加上1，就是原问题的解(为什么这么做呢，下⽂有解释)。

⽽关于该问题的解通常有两种⽅法：1.利⽤循环链表或者数组来模拟整个过程。

具体来讲，整个过程很明显就可以看成是⼀个循环链表删除节点的问题。

当然，我们也可以⽤数组来代替循环链表来模拟整个计数以及出列的过程。

此处只给出利⽤数组来模拟这个过程的解法，最终结果为最后⼀个出列的⼈的编号：#include<iostream>#include<unordered_map>#include<queue>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<sstream>#include<set>#include<map>using namespace std;int main(){int n,m;cin>>n>>m;vector<int>rs(n);for(int i = 0 ; i < n; i++)rs[i] = i + 1;//对⼈物重新进⾏编号，从0开始int cur_index = 0;//当前圆桌状态下的出列⼈的编号int out_cnt = 0;//⽤以表⽰出列的⼈数int cnt = n;//表⽰当前圆桌的总⼈数while(out_cnt < n - 1)//当out_cnt等于n-1时，循环结束，此时圆桌师⽣最后⼀个⼈，即我们要的结果{if(cur_index + m > cnt){if((cur_index + m) % cnt == 0)//这种情况需要单独考虑，否则cur_index就变成负值了cur_index = cnt - 1;elsecur_index = (cur_index + m) % cnt - 1;}elsecur_index = cur_index + m - 1;cnt--;out_cnt++;cout<<"当前出列的为："<<*(rs.begin() + cur_index)<<endl;rs.erase(rs.begin() + cur_index);//从数组中删去需要出队的⼈员}cout<<"最后⼀个出列的⼈物为："<<rs[0]<<endl;}该⽅法的时间复杂度为O(nm)，空间复杂度为O(n)，整个算法的基本流程还是⽐较清晰的，相当于每次循环更新cur_cnt、cnt和out_cnt这三个变量，当out_cnt == n-1时，此时出队的⼈数⼀共有n-1⼈，圆桌上只剩下⼀个⼈了，停⽌循环。

约瑟夫环实验报告约瑟夫环实验报告引言：约瑟夫环是一个经典的数学问题，它源自于古代传说。

根据传说，古代犹太人被罗马人围困在一个洞穴中，他们决定用一种特殊的方式来决定谁将成为首领。

他们站成一个圆圈，从一个人开始，每隔一个人杀掉一个，直到只剩下一个人。

这个问题被称为约瑟夫环问题，它在数学领域引起了广泛的研究和探讨。

实验目的：本实验旨在通过模拟约瑟夫环问题，探讨其数学规律和解法，并分析实验结果的意义和应用。

实验步骤：1. 首先，我们需要确定参与约瑟夫环的人数n和每次报数的间隔m。

在本次实验中，我们选择了n=10和m=3。

2. 接下来，我们将10个人按顺序排成一个圆圈，并给每个人编号，编号从1到10。

3. 实验开始时，从第一个人开始报数，每次报数到m的人将被淘汰出局。

4. 淘汰的人将离开圆圈，下一个人将从淘汰者的下一个人开始报数，继续进行报数和淘汰的过程，直到只剩下一个人为止。

实验结果：通过模拟实验，我们得到了以下结果：- 第一轮淘汰的人依次为：3、6、9、2、7、1、8、5、10。

- 第二轮淘汰的人依次为：4、9、2、8、5、1、7、6。

- 第三轮淘汰的人依次为：9、8、5、1、7、4、6。

- 第四轮淘汰的人依次为：1、7、4、6、9、5。

- 第五轮淘汰的人依次为：7、4、6、9、5。

- 第六轮淘汰的人依次为：4、6、9、5。

- 第七轮淘汰的人依次为：6、9、5。

- 第八轮淘汰的人依次为：9、5。

- 第九轮淘汰的人依次为：5。

结论：通过实验结果的分析，我们可以得出以下结论：1. 在本次实验中，最后幸存的人是编号为5的人。

2. 根据实验结果，我们可以总结出约瑟夫环问题的一般解法。

假设总人数为n，每次报数的间隔为m，最后幸存的人的编号可以通过递归公式f(n,m)=[f(n-1,m)+m]%n得到。

3. 约瑟夫环问题在数学中具有一定的研究价值和应用意义。

它涉及到递归、数论等数学概念和方法，可以帮助我们更好地理解和应用这些数学知识。

约瑟夫环问题详解很久以前，有个叫Josephus的⽼头脑袋被门挤了，提出了这样⼀个奇葩的问题：已知n个⼈（以编号1，2，3...n分别表⽰）围坐在⼀张圆桌周围。

从编号为k的⼈开始报数，数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规律重复下去，直到圆桌周围的⼈全部出列这就是著名的约瑟夫环问题，这个问题曾经风靡⼀时，今天我们就来探讨⼀下这个问题。

这个算法并不难，都是纯模拟就能实现的。

思路⼀：⽤两个数组，mark[10000]和num[10000],mark这个数组⽤来标记是否出队，num这个⽤来存值，然后每次到循环节点的时候就判断mark是否为0(未出队)，为0则输出num[i]，并标记mark[i]=1，直到所有的num都出队。

附上C++代码：#include<iostream>#include<cstring>#include<cstdio>#include<cstdlib>#include<cctype>#include<cmath>#include<algorithm>using namespace std;char num[1000];bool mark[1000];int main(){while(true){memset(mark,0,sizeof(mark));int n;int k,m;int i,j;int del=k-1;cin>>n>>k>>m;for(i=0;i<n;++i){cin>>num[i];}int cnt=n;for(i=cnt;i>1;--i){for(int j=1;j<=m;){del=(del+1)%n;if(mark[del]==0)j++;}cout<<num[del]<<" ";mark[del]=1;}for(i=0;i<n;++i){if(mark[i]==0)break;}cout<<endl<<"The final winner is:"<<num[i]<<endl;}return 0;}思路⼆：⽤⼀个数组就可，每次到了循环节点了就将num[i]输出，然后将后⾯的值往前移动⼀位，直到所有的节点出列。

0123456789 12345678910 4567891012 789101245 10124578 4578101
810145
45810
1045
104
4约瑟夫环——递推公式
递推公式：
f(N,M)=(f(N−1,M)+M)%N
f(N,M)表⽰，N个⼈报数，每报到M时杀掉那个⼈，最终
f(N−1,M)表⽰，N-1个⼈报数，每报到M时杀掉那个⼈，最终胜利者的编号
现在假设有10个⼈，报到3的⼈就会被杀掉，我们⽤数字给这⼗个⼈编号为
1 2 3 4 5 6 7 8 9 10
第·⼀⾏绿⾊那⾏是数组下标，第⼆⾏是每个⼈的编号
现在逆向推导
f(1,3):只剩最后⼀个⼈，胜利者的数组下标为0
f（2,3）=(f(1,3)+3)%2=1,只有两个⼈的时候，胜利者下标为1。

f（10,3）=3，因为我们数组下标是从0开始的，所以⼈的编号是下标+1，也就是4
那么这个公式是怎么推导的呢？
1.假设我们已经知道了10个⼈时，胜利者的下标为3，那下⼀次9个⼈时，胜利者的下标为多少？
其实就是10个⼈时杀掉了编号为3（即数组下标为2）的⼈后，后⾯的⼈都往前移动了3位，所以胜利者的下标由3变成了0
2.那我们倒过来我们知道9个⼈时，胜利者的下标为0，那10个⼈时胜利者的下标为多少？
其实这和上⾯的问题⼀样，这是这是上个问题的逆过程，就是把⼤家都往后移动3位，所以f(10,3)=f(9,3)+3,不过可能会出现数组越界所以要取模变成f（10,3）=（f（9,3）+3）%10
3.那么⼈数改为n报到m时就杀掉数组怎么移动呢
⼀样的，杀⼀⼈则后⾯的⼈的下标都往前移动m则，f（n，m）=（f（n-1，m）+m）%n。

约瑟夫环问题的三种解法约瑟夫问题是个著名的问题：N个⼈围成⼀圈，第⼀个⼈从1开始报数，报到k的⼈将被杀掉，接着下⼀个⼈⼜从1开始报，直到最后剩下⼀个，求最后留下的⼈的下标。

题⽬集合解法1：暴⼒可以直接暴⼒求解，时间复杂度为O(nk)解法2：递推设f(n,k)为当n个⼈围成⼀圈时，最后留下的⼈的下标。

对于f(n-1,k)来说，其结果相当于f(n,k)的结果向前移动k\%(n-1)位。

因为对于f(n,k)来说，去掉第⼀轮报的数(k\%n)后，现在就只剩下n-1个数，并且是以(k\%(n-1)+1)作为第⼀个数,即所有数向前移动k\%(n-1)位。

现在的结果就为f(n-1,k)对于f(5,3)来说,其结果为4。

当其去掉第⼀轮报的数后，其向前移动了(3\%4)位，以4为起始，f(4,3)结果为1，对应着f(5,3)的结果4向前移动了3位所以反过来看即为,即为f(n-1,k)的结果向后移动k\%(n-1)位即f(n+1,k)=(f(n,k)+k\%n)\%n (x下标从0开始,因为取模结果为[0,n-1])时间复杂度为O(n)ll josephus2(ll n,ll k){ll pos=0;for(int len=1;len<=n;len++){pos = (pos+k)%len;}return pos+1;}递推代码解法3：如果当前这⼀位⼈没被杀掉，则他可以放在幸存者的末尾，直到幸存者数量为1所以对于下标为i的⼈，如果在他前⾯已经被杀掉了q个⼈，那么他的新的下标为n+q(k-1)+x,(1\leq x <k)如下图所⽰，最后被淘汰的编号⼀定是n*k，所以幸存者最后的编号是n*k我们现在需要从幸存者最后的编号中恢复出最初编号假设幸存者这⼀次的编号为p os_{i}，在他后⾯包括他还有x位幸存者，则[pos_{i-1},pos_{i})间⼀定有x个不能被k整除的数这样才能使在他后⾯包括他还有x位幸存者。