资源描述：
《约瑟夫问题及变种》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、“约瑟夫”问题及若干变种例1、约瑟夫问题（Josephus）[问题描述]M只猴了要选大王，选举办法如下：所有猴了按1...M编号围坐一圈，从第1号开始按顺序1,2,N报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。M和N由键盘输入，1SN,MS1OOOO,打印出最后剩下的那只猴子的编号。例如，输入83,输出:7。[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而來的，所以通常称为Josephus（约瑟夫）问题。在确定程序设计方法之前首先來考虑如何组织数据，山于要记录m只猴子的状态，可利用含
2、m个元索的数组monkey來实现。利用元素下标代表猴了的编号，元素的值表示猴了的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。程序采用模拟选举过程的方法,设变Scount表示计数器,开始报数前将count置为0,设变量current衣示当前报数的猴子编号，初始时也置为0,设变量out记录出圈猴子数，初始时也置为0。每次报数都把monkey[current]值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对•应的monkey[current]值为0）,当count=n时，就对当前报数的猴子作岀圈处理，即：monk
3、ey[current]：=0,count：=0,out：=out+lo然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-l）。参考程序如下：programjosephusla｛模拟法，丿II数组下标农示猴子的编号｝constmaxm=10000;varm,n,count,current,out,i:integer;monkey:array[l..maxm]ofinteger;beginwrite（'Inputreadln（mzn）;fori:=ltomdomonkey[i]:=l;out:=0;count:=0;current:=0;whilecountvndobeginif
4、currentvmthencurrent:=current+1elsecurrent:=1;count:=count+monkey[current];end;monkey[current]:=O;out:=out+l;count:=0end;fori:=ltomdoifmonkey[i]=lthenwriteln('Themonkeykingisno.；i);readInend.[运行结果]下划线农示输入Inputm,n:83Themonkeykingisno.7｛时间：0秒｝Inputm,n:100001987Themonkeykingisno.8544｛时间：3秒｝[反思]时间复
5、杂度很人O(M*N),对丁•极限数据会超时。这已经是优化过的程序，大家可以去看未做任何优化的程序josephuslb.pas,这个程序的时间复杂度为0(M*N*K),K是一个不确定的系数，对应着程序中的repeat循环花费的时间。空间复杂度为O(M)。programjosephuslb;｛模拟法，用数组下标表示猴子的编号｝constmaxm=10000;varm,n,countzcurrentzoutzi:integer;monkey:array[l..maxm]ofinteger;beginwrite('Inputm,n:');readln(m,n);fori:=ltomdomon
6、key[i]:=l;out:=0;cou=current:=l;begjnwhilecountvndobeginrepeat｛寻找圈上的下一只猴子｝current:=cuirent+1;ifcurrent=m+lthencurrent:=luntilmonkey[current]=l;count:=count+1end;monkey[current]:=O;out:=out+l;count:=0end;fori:=ltomdoifmonkey[i]=lthenwriteln(‘Themonkeykingisno.：i);readInend・[问题分析2]在组织数据时，也可以考虑只记录
7、仍在圈中的猴子的情况。用一个线性表按编号由小到人依次记录圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元索减少一个。程序中用变量rest表示圈中剩余的猴子数，即线性表中元素的总数。参考程序如下：programjosephus2a;｛模拟法，用数组元索的值表示猴犷的编号｝constmaxm=10000;varm,n,currentzrestzi:integer;monkey:array[l..maxm]ofinteger;beginwr
