洛谷P1145 约瑟夫_洛谷p1145约瑟夫

题目描述
nn个人站成一圈，从某个人开始数数，每次数到mm的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人，kk个好人站在一起，kk个坏人站在一起。从第一个好人开始数数。你要确定一个最小的mm，使得在第一个好人被杀死前，kk个坏人先被杀死。

感谢yh大神指出样例数据的错误。

输入格式
一个k(0<k<14)k(0<k<14)

输出格式
一个mm

输入输出样例
输入 #1复制
3
输出 #1复制
5
输入 #2复制
4
输出 #2复制
30
说明/提示
0<k<140<k<14

思路： 暴力+模数

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

bool check(int x,int k)
{
    int now = 0;
    for(int i = 0;i < k;i++)
    {
        now = (now + x - 1) % (2 * k - i);
        if(now < k)//k以后的编号会变，但是之前的都不会动。
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int k;scanf("%d",&k);
    for(int i = k;;i++)
    {
        if(check(i,k))
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

约瑟夫问题的普通问法就是问最后一个幸存者的编号。
有直接模拟法和数学解法。

• 直接模拟法建立数组或者链表，模拟游戏过程中便当者的编号，你可以每次for m编，得到编号。或者一次走m步再取模确定下一次的编号，但是没想到怎样枚举通过剩下的编号得到答案。

附上约瑟夫环的数学解法，https://blog.csdn.net/doge__/article/details/82429348
对于n个人，报数为m的情况下，假设f(n,m)代表胜利者的编号，那么f(n,m) = (f(n - 1,m) + m) % n。比如n个人的时候胜者为x，那么进行完第一轮去掉了第m个人，实际上第m+1个人成为了第一个人，所有人的编号减去了m。

#include <stdio.h>

int main()
{
	int n, m, i, s = 0;
	printf ("N M = ");
	scanf("%d%d", &n, &m);
	for (i = 2; i <= n; i++)
	{
		s = (s + m) % i;
		printf("%d\n",s);
	}
	printf ("\nThe winner is %d\n", s+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14