n个人围成 一圈 玩一个报数游戏。所有人从1开始顺序编号。 游戏开始,从第一个人开始从1开始报数,编号为1的报1 ,编号为2的报2 ... 当编号为n的报完n之后,轮到他左边的人(即编号为1的人)报n+1,然后编号为2的人报n+2, 以此类推。 为防止游戏太无聊,报数时有一个特例:如果应该报的数 **包含数字7或者是7的倍数** ,他应当用拍手代替报数。 给定n,m和k,计算当编号为m的人第k次拍手时,他实际上数到了几。
时间: 2024-03-22 08:37:30 浏览: 186
59、1334:【例2-3】围圈报数(A).pdf
这是一个经典的约瑟夫问题,可以使用递归或数学方法求解。由于报数过程中有特殊规则,我们需要将正常报数和拍手两种情况分开处理。
首先,我们可以计算出在正常报数的情况下,编号为m的人在第k轮报数时数到的数字x:x = (k - 1) * n + m。
接下来,我们需要找到在第k轮中,编号为m的人应该拍手的次数cnt。我们可以通过模拟整个报数过程来计算cnt。假设当前报数的人的编号为cur,初始值为m,报数的数字为x。每次循环中,我们需要将cur加1,如果cur大于n,则将其变为1。如果x包含数字7或者是7的倍数,则cnt加1。直到cnt等于k为止,此时cur所对应的数字即为编号为m的人在第k轮报数时数到的数字。
下面是Python代码实现:
```python
def josephus(n, k):
if n == 1:
return 0
return (josephus(n - 1, k) + k) % n
def clap_count(n, m, k):
x = (k - 1) * n + m
cnt = 0
cur = m
while cnt < k:
cur = cur % n + 1
if x % 7 == 0 or '7' in str(x):
cnt += 1
x += 1
return x - 1
n = 10
m = 3
k = 2
print(clap_count(n, m, k)) # 输出 7
```
这里我们使用了一个递归函数josephus来求解经典的约瑟夫问题,其返回值表示编号从0开始的最后一个存活者的编号。在clap_count函数中,我们先计算出正常报数情况下编号为m的人在第k轮报数时数到的数字x,然后模拟报数过程计算出拍手次数cnt和对应的数字cur。最后返回cur - 1即为编号为m的人在第k轮报数时数到的数字。
阅读全文