首页 > 代码库 > 约瑟夫问题

约瑟夫问题

 T2437 对刚!(模拟题)(入门难度)

https://www.luogu.org/problem/show?pid=T2437

题目背景

hwh在军训。教官一言不合就想干人!

题目描述

教官让n个同学按照编号1至n顺时针围成一圈,从一号开始顺时针报数,报到t的人直接被教官干掉,拖到圈子外面。然后从他的下一位同学开始接着报数,hwh为了伸张正义,决定搞个大新闻,他要和教官对刚,,为了有充分时间准备,他决定站在最后一个被教官干掉的地方,你需要求出这是第几个位置。

输入输出格式

输入格式:

 

一行两个数 n,t。

 

输出格式:

 

一行一个数表示答案。

 

输入输出样例

输入样例#1:
3 2
输出样例#1:
3

说明

①对于 30% 的数据,满足n ≤ 100

②对于 100% 的数据,满足n ≤ 100000,1 ≤ t ≤ 100

我们知道第一个人(编号一定是(m-1)) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m mod n的人开始):
k k+1 k+2 ... n-2,n-1,0,1,2,... k-2
并且从k开始报0。
我们把他们的编号做一下转换:
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x‘=(x+k) mod n
如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:
令f表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]
递推公式
f[1]=0;
f[i]=(f[i-1]+m) mod i; (i>1)
有了这个公式,我们要做的就是从1-n顺序算出f的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,我们输出f[n]+1
由于是逐级递推,不需要保存每个f,程序也是异常简单:
#include<cstdio>int main(){    int n,m,f = 0;    scanf("%d%d",&n,&m);    for (int i = 1; i <= n; i++) f = (f + m) % i;    printf("%d",f+1);}

 

约瑟夫问题