josephus问题c++找规律
时间: 2024-01-05 18:04:29 浏览: 81
Josephus问题是一个经典的数学问题,它的描述是:n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,直到剩下最后一个人。现在我们来分析一下这个问题的规律。
首先,我们假设 n=5, m=3,列出每一轮的出圈顺序:
第一轮:3出圈,剩下 1 2 4 5 第二轮:1出圈,剩下 2 4 5 第三轮:5出圈,剩下 2 4 第四轮:2出圈,剩下 4 第五轮:4出圈,剩下空
可以发现,每一轮出圈的人的编号都是连续的一段数,而且第一轮的起点是 m-1,以后每一轮的起点都是上一轮的出圈人的下一个人。因此,我们可以得出以下的规律:
设 f(n,m) 表示 n 个人报数,每报到 m 就出圈的最后剩下的人的编号。
当 n=1 时,f(n,m)=0。 当 n>1 时,f(n,m)=[f(n-1,m)+m]%n。
这个规律可以用递归或循环的方式实现,下面是 C++ 的代码实现:
int josephus(int n, int m) {
if (n == 1) {
return 0;
}
return (josephus(n-1, m) + m) % n;
}
值得注意的是,这个递归实现的时间复杂度为 O(n),因为每次都要递归调用 n-1 次,而且还有取模运算。如果想要更快的实现,可以改成循环实现,时间复杂度为 O(log n):
int josephus(int n, int m) {
int ans = 0;
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}