N个人排成一圈,指定第一个人,去除他,然后跳着一人去除第3人,以次类推,最后
的那一人获胜。给定这N个人和第一个人的位置,你该如何选取位置才会获胜。
让你写最优算法,并计算时间和空间复杂度。不要求写出代码,解释算法即可。
Joseph问题的数学方法
无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅
程序写起来比较烦,而且时间复杂度高达O(nm),当n,m非常大(例如上百万,上
千万)的时候,几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要
求出最后的胜利者的序号,而不是要读者模拟整个过程。因此如果要追求效率,
就要打破常规,实施一点数学策略。
为了讨论方便,先把问题稍微改变一下,并不影响原意:
问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继
续从0开始报数。求胜利者的编号。
我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的
约瑟夫环(以编号为k=m%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
k-1 --> n-1
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:
例如x是最终的胜利者,那么根据上面这个表把这个x变回去不刚好就是n个人情况
的解吗?!!变回去的公式很简单,相信大家都可以推出来:x‘=(x+k)%n
如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)
个人的解呢?当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题!好了,思
路出来了,下面写递推公式:
令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]
递推公式:
f[1]=0
f[i]=(f[i-1]+m)%i; (i>1)
有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。因
为实际生活中编号总是从1开始,我们输出f[n]+1,由于是逐级递推,不需要保存每
个f[i],程序也是异常简单:
#include
int main()
{
int n, m, i, s=0;
printf ("N M = ");
scanf("%d%d", &n, &m);
for (i=2; i
int mod(int x,int n)
{ return (x%n+n)%n; }
int f(int n,int m,int t) {
if(n==2) return mod(t,n)==1?2:1;
else if(mod(t,n)!=mod(m,n))return mod(f(n-1,m,mod(t-m-1,n)+1)+m-1,n)+1;
else return mod(f(n-1,m,n-1)+m,n)+1;
}
int main(int arg, char* args[])
{
int k,n,m,t;
freopen(args[1], "r",stdin);
scanf("%d",&k);
while( k-- ) {
scanf("%d%d%d",&n,&m,&t);
printf("%d\n",f(n,m,t));
}
return 0;
}
分享到:
相关推荐
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
OpenCV 3 Blueprints - Joseph Howse,可以使用电子书,或者用sumatraPDF等工具打开。
Art Gallery Theorems and Algorithms - Joseph O'Rourke 计算几何算法中,美术馆问题的专题选讲
ANDCURRENCYFORECASTING(跨国公司财务管理-Joseph.pptx
django-unit-project-joseph-dylan-greg:django-unit-project-joseph-dylan-greg由GitHub Classroom创建
约瑟夫环的实现之数组方式,C实现源码,更多内容请见http://blog.csdn.net/zhongkelee
The source code is created using matlab
Joseph排列问题。 Joseph问题可以描述如下:设有n个人排列成一圈,再任意给定一个正整数m≤n。从指定的第一个人开始,沿着这个圈,顺序移出第m个人。当某个人被移出后,计数从下一个开始,继续移出第m个人。这个过程...
CRM-Joseph-Amsellem
背景:血友病是一种体质性出血病,在马达加斯加一直存在,考虑到在包皮环切术后死亡的儿童,这在确诊患者的家族史中已有报道。 血友病是严重的,因为潜在的致命出血风险。 这项研究的目的是评估塔那那利佛JRA医院...
对于初学FPGA,Verilog编程的人,可以去仔细学习一下。
5-20-cv-02332-JWH-KK-Joseph-Diaz-Jr.-v.-Ralph-Heredia-
进行了分析研究,以研究磁场对... Beavers-Joseph条件应用于两层之间的界面。 分析了哈特曼数和流体动力学各向异性对对流现象的影响。 发现磁场,各向异性渗透率和多孔衬里的厚度ε对地热对流和传热速率有很大的影响。
运动学问题解答 Resolva o Problema da mochila conformo o enuciado em sala de aula。 Ache umasoluçãoque testa todas ascombinaçõespossíveise seleciona a melhor,aplicandodivisão-e-conquistaounão;...
利用经典李群方法,得到(2+1)维Kadomtsov-Pet-viashvili-Joseph-Egri方程的经典李点对称,并利用对称得到该方程的一些相似约化,通过求解约化方程,得到了该方程的很多精确解,包括双曲函数解,雅可比椭圆函数解,...
The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed ...
wiki.ros上2017年唯一一本书 ROS.Robotics.Projects 2017-Lentin Joseph 在KINDLE上阅读的azw3格式 不要下错了
joseph环joseph环joseph环joseph环joseph环joseph环joseph环joseph环joseph环joseph环joseph环joseph环
快速样板! 这是用于启动新项目的样板项目!设置完成以下步骤以开始一个新项目(NEW-PROJECT-NAME): 将此存储git clone BOILERPLATE-URL NEW-PROJECTS-NAME到本地计算机上git clone BOILERPLATE-URL NEW-PROJECTS-...
2017年目前出版的唯一 一本 ROS 的书,作者Lentin Joseph