python用匿名函数求约瑟夫环问题
时间: 2024-05-29 09:06:20 浏览: 17
约瑟夫问题是一个经典的问题,也称为约瑟夫置换。问题描述如下:假设有n个人坐成一个圆圈,从第1个人开始报数,数到m的那个人出列,它的下一个人又从1开始报数,数到m的那个人又出列,依次类推,直到所有人都出列为止。通常将这个问题描述为(n,m)- Josephus问题。请问最后一个出列的人是原来在圆圈中的第几号位置?
下面是用Python实现该问题的匿名函数:
```
n, m = 10, 3
people = list(range(1, n+1))
i = 0
while len(people) > 1:
i = (i + m - 1) % len(people)
print('出列人员为:', people.pop(i))
print('最后一个出列的人员为:', people)
```
这个程序使用了列表来存储所有人员的编号。在每次循环中,我们计算出下一个要出列的人员的编号,并将其从列表中删除。当只剩下最后一个人员时,程序输出其编号。
相关问题
用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)
![](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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)