有 � n 人围成一圈,按顺序编号。 从第 1 1 个人开始报数( 1 1 到 3 3 报数),凡报到 3 3 的人退出圈子,问最后留下的是原来的第几号。
时间: 2023-12-27 18:55:19 浏览: 37
根据约瑟夫问题的经典解法,最后留下的人的编号为:
$$
f(n,m) = \begin{cases}
0 & n = 1 \\
[f(n-1,m)+m] \bmod n & n > 1
\end{cases}
$$
其中,$n$ 表示初始时围成圈的人数,$m$ 表示报数到第几个人就出圈。将 $n=1000$,$m=3$ 代入上式,得到最终留下的人的编号为 661。
相关问题
有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问
最后留下的是原来第几号的那位?
这是一个经典的约瑟夫问题。根据引用中的解题思路,我们可以写一个函数来解决这个问题。具体步骤如下:
1. 定义一个大小为n的一维数组,初始化为从1到n。
2. 设一个计数器,按照题述条件,遍历每一个数组元素,并从1到3报数,若当前元素计数为3则将其从数组中删除(即标记该人出局),同时使计数器置0并记录出局人数。
3. 如果出局人数为n-1人(即只剩下1人)终止循环,否则由外层循环控制使得再次遍历数组,直到踢出n-1人。
4. 最后满足只剩1人的条件后,再次遍历数组,找出那个最终没有被踢出的人,并返回其序号。
因此,最后留下的是原来第几号的那位取决于n和报数的规则。如果n=5,报数规则为从1到3,则最后留下的是原来第3号的那位。如果n=10,报数规则为从1到2,则最后留下的是原来第5号的那位。
模拟报数游戏。有n个人围成一圈,从0到n-1按顺序编号,从第一个人开始从1到k报数,报
然后喊到k的人出圈,剩下的人继续从1开始报数。直到只剩下一个人为止。这个游戏叫做约瑟夫问题(Josephus Problem)。
这个问题的解可以用数学方法和递归方法来得到。对于数学方法,我们可以通过递推式来求解。假设f(n,m)表示有n个人围成一圈,每次数到m的人离开,最后剩下的人的编号。则f(n,m)可以表示为:f(n,m) = (f(n-1,m) + m) % n。其中,%表示求余数。
对于递归方法,我们可以将问题分解为一个个子问题。假设f(n-1,m)已知,表示n-1个人的约瑟夫问题,那么f(n,m)可以表示为:f(n,m) = (f(n-1,m) + m) % n。这个式子的意思是,第一次数到m的人下标是k=m-1,那么此时k+1到n-1的人经过了一次约瑟夫问题,剩下了[0, k)和(k+1, n-1)这两群人,此时我们需要对[n-1, k+1)这段下标重新映射到[0, n-k-2]的区间内,这样就转化成了f(n-1, m)的子问题。
约瑟夫问题是一道经典的算法问题,可以锻炼我们的递推能力和思维灵活性。同时,也是一道娱乐戏谑的小游戏,可以增加我们的娱乐价值。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)