用python中的函数计算约瑟夫环问题,最简单的方法
时间: 2024-02-03 19:12:16 浏览: 46
最简单的方法是使用列表和循环来实现。具体步骤如下:
1. 创建一个包含所有人的列表,从1到n。
2. 定义一个变量m表示每次数到第m个人出圈。
3. 定义一个变量p表示当前数到的人的位置。
4. 在循环中,每次将p向前移动m个位置。
5. 如果p超过了列表的长度,则将p调整为p%列表长度。
6. 将位置p的人出圈,并将其从列表中删除。
7. 重复步骤4-6,直到只剩下最后一个人。
以下是Python代码实现:
```python
def josephus(n, m):
people = list(range(1, n + 1))
p = 0
while len(people) > 1:
p = (p + m - 1) % len(people)
print("出圈人的编号为:", people[p])
people.pop(p)
return people[0]
# 测试
print("最后一个留下的人的编号为:", josephus(10, 3))
```
输出结果:
```
出圈人的编号为: 3
出圈人的编号为: 6
出圈人的编号为: 9
出圈人的编号为: 2
出圈人的编号为: 7
出圈人的编号为: 1
出圈人的编号为: 8
出圈人的编号为: 5
出圈人的编号为: 10
最后一个留下的人的编号为: 4
```
相关问题
用python中的函数计算约瑟夫环问题
以下是Python代码,用于计算约瑟夫环问题:
```python
def josephus(n, k):
if n == 1:
return 1
else:
return (josephus(n - 1, k) + k-1) % n + 1
# 示例
n = 7
k = 3
print("最终剩下的人的编号为:", josephus(n, k))
```
输出:
```
最终剩下的人的编号为: 4
```
其中,`n`表示初始时人数,`k`表示每次报数的数目。函数`josephus(n, k)`返回最终剩下的人的编号。
具体思路是递归求解,假设`josephus(n-1, k)`是在已经减少一个人的情况下的最终结果,那么在初始状态下,第一个被删除的人的编号为`(k-1)%n+1`,因为编号从1开始,所以要加1。因此,可以得到递推式:`josephus(n, k) = (josephus(n-1, k) + k-1) % n + 1`。最终,当人数为1时,返回1。
用python计算约瑟夫环问题,不使用递归函数
约瑟夫环问题是一个经典的问题,可以使用python进行计算。下面给出一个不使用递归函数的解法:
```python
def josephus(n, k):
arr = list(range(1, n+1))
idx = 0
while len(arr) > 1:
idx = (idx + k - 1) % len(arr)
arr.pop(idx)
return arr[0]
n = 10
k = 3
print(josephus(n, k)) # 输出为4
```
这个算法的思路是,首先初始化一个数组,里面存储了所有的人的编号,然后从第一个人开始,每次数k个人,到达第k个人后将其从数组中删除。当只剩下一个人时,该人即为最后留下来的人。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)