python 7-9 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号? 输入格式: 测试数据有多组,处理到文件尾。每组测试输入一个整数n(5≤n≤100)。 输出格式: 对于每组测试,输出最后剩下那个人的编号。 输入样例: 10 28 69 输出样例: 4 23 68
时间: 2024-02-22 20:59:01 浏览: 39
好的,以下是Python的代码实现:
```python
while True:
try:
n = int(input())
if n == 0:
break
arr = [i for i in range(1, n + 1)]
idx = 0
while len(arr) > 1:
idx = (idx + 2) % len(arr)
arr.pop(idx)
print(arr[0])
except:
break
```
每次读取一个整数n,如果n为0则退出程序。生成一个1到n的列表arr,然后用idx来记录当前报数的人的下标,每次将idx加2,然后对列表长度求模,得到下一个报数的人的下标。弹出该下标对应的人,重复上述步骤直到只剩下一个人,输出该人的编号即可。
相关问题
7-3 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人
的编号是多少?
这是经典的约瑟夫环问题,可以使用递归或数学方法解决。
递归方法:
首先定义递归函数 Josephus(n, k),表示 n 个人围成一圈,每次报数 k,最后剩下的人的编号。则有:
Josephus(n, k) = (Josephus(n-1, k) + k - 1) % n + 1
其中 % 表示取模运算。
当 n=1 时,只剩下一个人,其编号为 1,因此可以作为递归的终止条件。
完整代码如下:
```python
def Josephus(n, k):
if n == 1:
return 1
else:
return (Josephus(n-1, k) + k - 1) % n + 1
n = int(input("请输入人数:"))
k = 3 # 报数为 3
print("最后剩下的人的编号是:", Josephus(n, k))
```
数学方法:
根据数学方法,最后剩下的人的编号为:
f(n, k) = (f(n-1, k) + k) % n
其中 f(1, k) = 0。
完整代码如下:
```python
def Josephus(n, k):
if n == 1:
return 1
else:
return (Josephus(n-1, k) + k - 1) % n + 1
n = int(input("请输入人数:"))
k = 3 # 报数为 3
print("最后剩下的人的编号是:", Josephus(n, k))
```
7-3 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号? 输入格式: 测试数据有多组,处理到文件尾。每组测试输入一个整数n(5≤n≤100)。 输出格式: 对于每组测试,输出最后剩下那个人的编号。
这是经典的约瑟夫环问题,可以使用循环链表或者数学公式来解决。下面给出使用数学公式的解法:
假设最终剩下的人的编号为 $f(n)$,则第一次报数后,编号为 $3$、$6$、$9$、$\cdots$ 的人出圈,剩下 $n_1=n-\lfloor\frac{n}{3}\rfloor$ 个人,且编号重新从 $1$ 开始。
对于剩下的 $n_1$ 个人,第二次报数后,编号为 $2$、$5$、$8$、$\cdots$ 的人出圈,剩下 $n_2=n_1-\lfloor\frac{n_1}{3}\rfloor$ 个人,且编号重新从 $1$ 开始。
对于剩下的 $n_2$ 个人,第三次报数后,编号为 $2$、$5$、$8$、$\cdots$ 的人出圈,剩下 $n_3=n_2-\lfloor\frac{n_2}{3}\rfloor$ 个人,且编号重新从 $1$ 开始。
以此类推,直到剩下一个人为止,即 $n_k=1$,此时剩下的那个人的编号就是 $f(n)$。因此,我们可以列出递推公式:
$$
n_{k}=n_{k-1}-\left\lfloor\frac{n_{k-1}}{3}\right\rfloor, \quad n_0=n \\
f(n)=3k-n_k+1
$$
根据递推公式,我们可以编写如下代码:
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)