文章
79
粉丝
221
获赞
46
访问
186.6k
#include <iostream>
using namespace std;
//公式f(n,m)=(f(n-1,m)+m)%n
int f2(int n, int m) {
if (n == 1)
return 0;
return (f2(n - 1, m) + m) % n;
}
int main() {
int n;
cin>>n;
cout << f2(n, 3) + 1<< endl;
return 0;
}
解决约瑟夫环问题,我们采用倒推,我们倒推出:最后剩下的这个数字,在最开始的数组中的位
置。
1.剩下最后一个数字(简称"它" )的时候,总个数为1,它的下标pos = 0。
2.那么它在上一轮也是安全的,总个数为2,它的下标pos= (0 + m)%2; (解释: 在上一轮
中,它前面的数字(即红色的数字,下标为m- 1)被移走了;因此它的下标是m;由于是
环,因此需要%2)
3.那么它在上上轮也是安全的,总个数为3,它的下标pos= ((0 + m)%2 + m)%3;
4.那么它在上上上轮也是安全的,总个数为4,它的下标
pos= (((0 + m)%2 + m)%3 + m)%4;
6.那么它在游戏开始的第一轮也是安全的,总个数为n,它的下标pos就是所求。
即如果从下向上反推的时候:假如它下-轮的下标为pos,那么当前轮次的下标就是:
(pos + m)%当前轮次的人数。
每杀掉一个人,下一个人成为头,相当于把数组向前移动M位。
若已知N-1个人时,胜利者的下标位置位f ( N − 1 , M ),则N个人的时候,就是往后移动M位,
(因为有可能数组越界,超过的部分会被接到头上,所以还要模N),既f ( N , M ) = ( f ( N − 1 , M ) + M ) % n
登录后发布评论
暂无评论,来抢沙发