PTA约瑟夫环之位标记
时间: 2024-06-16 21:08:22 浏览: 15
PTA约瑟夫环问题是一个经典的数学问题,由于它的应用广泛,因此在面试中也经常被提到。其问题描述为:已知n个人(用编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出圈;他的下一个人又从1开始报数,数到m的那个人又出圈;依此规律重复下去,直到圆桌周围的人全部出圈。
PTA约瑟夫环之位标记,指的是一个数组标记,用来记录每个人是否出圈。在具体实现上,我们可以用一个布尔类型的数组,将所有元素初始化为false表示未出圈,当某个人出圈时将其对应位置设为true。这样就可以避免重复报数和统计剩余人数时的错误。
相关问题
pta7-2 约瑟夫环
约瑟夫环是一个古老的数学问题,该问题最早由约瑟夫·弗拉维奥于1世纪通过犹太历史记载引入数学。问题的背景是:在古代,有一个40个人组成的团体,他们在围成一个圆圈坐下,从某个人开始报数,报到某个数的人将被淘汰。然后,从下一个人开始重新报数,再次报到某个数的人又被淘汰。如此循环,直到只剩下一个人为止。
这个问题可以用数学的方式进行求解。我们可以使用递归的方法来解决。假设初始位置为0,报到第m个人就出列,现在求剩下的最后一个人的位置。
首先,我们可以观察到,每次淘汰的人在他前任的基础上向前移动了m位,同时,由于圆圈的连续性,还需要将当前位置对总人数取余。因此,第一轮结束后,第一个出列的人的位置为m-1。接下来,我们可以继续观察,第二轮开始时,剩下的人的位置相当于前一轮剩下人的位置再向前移动m位取余,即为(m-1+m) mod n,其中n为前一轮剩下的人数,也就是总人数。
按照上述的计算逻辑和递归的方法,我们可以得到第k轮淘汰之后剩下的人的位置为:
f(1) = 0
f(k) = (f(k-1) + m) mod n
通过以上的递归关系,我们可以迭代求解,直到最后一轮淘汰,剩下的人的位置即为答案。
总结起来,约瑟夫环是一个经典的数学问题,通过构建递归关系并利用数学计算,我们可以求解出最后一个留下来的人在圆圈中的位置。
pta约瑟夫问题
PTA约瑟夫问题是一个经典的数学问题,假设有n个人围成一圈,从第1个人开始报数,报到m的人出圈,下一个人重新从1开始报数,直到所有人出圈为止。问最后剩下的人在原来的编号中是第几个。
具体的解题思路可以使用环形链表模拟这个过程,每次找到要出圈的人并将其从链表中移除,然后重新从下一个人开始继续报数。最后留下的那个人就是最终的答案。
以下是一个使用Python实现的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def josephus(n, m):
head = Node(1)
last = head
for i in range(2, n+1):
new_node = Node(i)
last.next = new_node
last = new_node
last.next = head
p = last
for i in range(n):
for j in range(m-1):
p = p.next
print("出圈:", p.next.data)
p.next = p.next.next
print("最后留下的人:", p.data)
n = 5
m = 3
josephus(n, m)
```
输出结果为:
```
出圈: 3
出圈: 1
出圈: 5
出圈: 2
最后留下的人: 4
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)