pythonn个人围成一圈(编号分别为1,2,3……n),从第一个人开始报数,数到k的人出圈。再由下一个人开始报数,数到k的人出圈……依次输出出圈人的编号。
时间: 2024-03-10 13:24:11 浏览: 33
这是一个经典的约瑟夫问题。可以用一个list来记录所有人的编号,然后依次遍历list,每次数到k时,将该人从list中删除,并记录下该人的编号,直到list中只剩下一人为止。下面是代码实现:
```python
n = int(input("请输入总人数n:"))
k = int(input("请输入报数的数字k:"))
nums = list(range(1, n+1))
result = []
i = 0
while len(nums) > 1:
i = (i + k - 1) % len(nums)
result.append(nums.pop(i))
result.append(nums[0])
print("出圈顺序为:", result)
```
输出结果为:
```
请输入总人数n:5
请输入报数的数字k:2
出圈顺序为: [2, 4, 1, 5, 3]
```
这个算法的时间复杂度为O(nk),因为每次删除一个元素需要O(k)的时间。如果使用一个队列来保存人的编号,每次取出队首元素再加入队尾,可以优化时间复杂度至O(n)。
相关问题
有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人原来的位置是多少号?用python写
好的,根据你的问题,我来为你编写一个Python程序来解决这个问题:
```python
def find_survivor(n):
people = list(range(1, n+1))
index = 0
while len(people) > 1:
index = (index + 2) % len(people)
people.pop(index)
return people[0]
n = int(input("请输入总人数:"))
survivor = find_survivor(n)
print("最后幸存者的编号是:", survivor)
```
运行程序后,输入总人数,即可得到最后幸存者的编号。程序的核心思路是使用一个列表来表示所有人,然后不断地按照规则报数并将报数到3的人从列表中剔除,直到只剩下一个人为止。最终剩下的那个人就是幸存者,其编号即为答案。
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))
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![apk](https://img-home.csdnimg.cn/images/20210720083646.png)