约瑟夫问题
*问题分析和算法设计
约瑟夫问题并不难，但是有很多方法可以解决。题目的变化形式也很多。下面是一个实现方法。
题目里30个人围成一个圈，启发我们用循环链来表达。您可以使用结构数组来形成循环链。结构中有两个成员，一个是指向下一个人的指针，形成一个循环链；第二个是这个人是否已经被扔进海里的标记，是1，表示他还在船上。从第一个人开始数没被扔进海里的人，数到9的时候，把结构里的标记改成0，表示这个人已经被扔进海里了。如此循环计数，直到15人被抛入大海。
通式
约瑟夫问题是一个著名的问题:n个人围成一个圈，从第一个开始数，第m个会被杀死，剩下最后一个，剩下的也会被杀死。比如N=6，M=5，被杀的人的编号是5，4，6，2，3。最后剩下1。
假设圈里前k个是好人，后k个是坏人。你的任务是确定最小m，使所有的坏人都能在第一个好人之前被杀死。
C++代码示例:
# include & ltiostream & gt
使用命名空间std
void main()
{
int n，m，a[101]，k，I，j，num//计数器从1开始，所以100人用101。
cout & lt& lt请输入参加游戏的玩家人数(不超过100):
CIN & gt；& gtn；
cout & lt& lt“-”& lt；& ltendl
如果(n & gt100)
{
cout & lt& lt"玩家太多了，请重新登录这个程序！"& lt& ltendl
返回；
}
cout & lt& lt"输入游戏中要玩的号码:"；
CIN & gt；& gtm；
cout & lt& lt“-”& lt；& ltendl
for(I = 1；我& lt= n；i++)
{
ai = 1；//注意百度百科中不允许使用ASCII中的括号。这里是中文字符集的括号。
}
j = 0；
k = 0；
for(I = 1；我& lt= n+1；i++){
if(ai==1){
j = j+ai；
如果(j==m)
{
j = 0；
ai = 0；
k++；
}
if(k==n){
num = I；
打破；
}
}
if(i==n+1)
I = 0；
}
cout & lt& lt“最后赢的玩家是第一个玩家”
cout & lt& lt“-”& lt；& ltendl
}
写完密码，约瑟夫以为自己看到了一个约瑟夫问题的数学解，巧妙简单，但只能推导出最后一个出队列的人。
无论是用链表还是数组实现，都有一个* * *相似性:要模拟整个游戏过程，不仅程序写起来麻烦，而且时间复杂度高达O(nm)。当N和M很大的时候(比如几百万，几千万)，短时间内几乎不可能出结果。我们注意到，原问题只问了最后赢家的序号，而没有要求读者模拟整个过程。所以，要想追求效率，就必须打破常规，实施一些数学策略。
为了讨论方便，在不影响初衷的前提下，我们先把问题改一点:
问题描述:N人(0号~(n-1))，从0开始计数，签到(m-1)退出，其余从0继续计数。找出获胜者的号码。
我们知道，第一个人(其编号必须是m mod n-1)出列后，剩下的n-1人组成一个新的约瑟夫环(从编号为k=m mod n的人开始):
k k+1 k+2...n-2，n-1，0，1，2，...幼儿园二年级
从k开始，报告0。
现在让我们改变他们的数字:
k-& gt；0
k+1->；1
k+2 ->2
...
...
k-2 ->n-2
k-1->；n-1
变换后完全变成(n-1)个人报告的子问题。如果我们知道这个子问题的解:比如X是最终赢家，那么按照上表把这个X改回来不就正好是N个人情况的解了吗？！！换回的公式很简单，相信大家都能推导出来:x' = (x+k) mod n。
如何知道(n-1)个人号问题的解决方法？对，只要知道(n-2)个人的解。(n-2)个人解决方案呢？当然是先求(n-3)的情况——这明显是个后向问题！好了，思路出来了。让我们写一个递归公式:
设F表示我玩这个游戏，M退出最后赢家的号码。最后的结果自然是f[n]。
递推公式
f[1]= 0；
f =(f+m)mod I；(我& gt1)
有了这个公式，我们要做的就是从1-n的顺序计算f的值，最后的结果就是f[n]。因为现实生活中编号总是从1开始，所以我们输出f[n]+1。
因为是逐步递归，所以不需要保存每一个f，程序极其简单:
c++
# include & ltstdio.h & gt
int main()
{
int n，m，I，s = 0；
printf(" N M = ")；scanf("%d%d "，& ampn & amp；m)；
for(I = 2；我& lt= n；i++)s =(s+m)% I；
printf("赢家是%d\n "，s+1)；
}
帕斯卡
var n，m，I，s:整数；
开始
写(' N M = ')；
读(n，m)；
对于i:=2到n do
s:=(s+m)mod I；
writeln('胜者为'，s+1)；
结束。
该算法的时间复杂度为O(n)，与模拟算法相比有了很大的提高。计算n，m等于100万，1000万的情况不是问题。可见，恰当地使用数学策略，不仅可以使编程变得简单，还可以成倍地提高算法执行的效率。
约瑟夫问题10e100版(来自vijios)
描述描述
n个人围成一个圈。从一个人开始，顺时针编号。从编号为1的人开始，顺时针数“一二一”，报2的人退出圈子。如此循环下去，圈子里的人会越来越少。因为人数有限，最后会剩下一个人。开头问最后剩下的人的号码。
输入格式
正整数n，代表人数。输入数据确保数字n不超过100位。
输出格式输出格式
正整数。它代表“一二一”计数后剩下的最后一个人的数量。
样本输入样本输入
九
样本输出样本输出
三
时间限制
每个测试点1
注释提示
样本描述
当n=9时，退出圈子的人数为:
2 4 6 8 1 5 9 7
剩下的最后一个人是3号。
第一次看到这个问题，你可能会想到模拟。但是数据太大了！！
让我们先算一下，我们可以看到当n是1，2，3，4，5，6，7，8时...结果分别是1，1，3，1。...
有如下规则:从1到下一个1，每组都是从1递增的奇数，每组元素个数分别为1，2，4。...
这个很容易得到！！
大致思路如下:
①改为(a)
②b:=1，c:=1{b是某组中元素的个数，C是现在添加的个数}
③而c & ltA do (b:=b*2，c:=b+c){超过目标时停止添加}
⑥c:=c-b{回到上一组}
⑦x:=a-c{计算目标在组中的哪个元素}
⑧ans:=x*2-1{查找元素}
⑨写(ans)
有想法，加上精度高。我写的代码比较琐碎，因为是先把上面的思路打进去，再写流程，把一些简单的流程融入到主程序里，所以有点乱，有点琐碎。提供思路也可以~ ~ ~
变量a，b，c:数组[1..105]的整数；
la，lb，lc，I:整数；
s:字符串；
incc程序；
var i:整数；
开始
对于i:=1到105做c:= c+b；
for i:=1到104 do if c & gt；那就9
开始
c:= c+c div 10；
c:= c mod 10；
结束；
结束；
函数cxiaoa:布尔型；
var i:整数；
开始
c xiaoa:= false；
对于i:=105向下到1 do
如果c & lta then begin c xiaoa:= true；打破；结束
else if c & gt然后打破；
结束；
双重程序b；
var i:整数；
开始
对于i:=1到105做b:= b * 2；
for i:=1到104 do if b & gt；那就9
开始
b:= b+b div 10；
b:= b mod 10；
结束；
结束；
程序decc
var i，j:整数；
开始
对于i:=1到104 do
如果c & gt=b然后c:=c-b否则
开始
j:= I+1；
而c[j]= 0 do Inc(j)；
而j & gt我愿意
开始
c[j]:= c[j]-1；
c[j-1]:= c[j-1]+10；
第十届会议；
结束；
c:= c-b；
结束；
结束；
程序fua
var i:整数；
开始
对于i:=1到104 do
如果a & gtc那么a:=a-c否则
开始
a:= a-1；
a:= a+10；
a:= a-c；
结束；
结束；
程序输出；
var i，j:整数；
开始
对于i:=1到105做a:= a * 2；
for i:=1到104 do if a & gt；那就9
开始
a:= a+a div 10；
a:= a mod 10；
结束；
如果a[1]>0然后a[1]:=a[1]-1否则
开始
j:= 2；
而a[j]= 0 do Inc(j)；
而j & gt1 do
开始
a[j]:= a[j]-1；
a[j-1]:= a[j-1]+10；
第十届会议；
结束；
a[1]:= a[1]-1；
结束；
for I:= 105 down to 1 do if a & gt；0然后开始j:= I；打破；结束；
对于i:=j downto 1做写(a)；
结束；
开始
readln(s)；
la:=长度(s)；
for I:= la downto 1 do a:= ord(s[la+1-I])-ord(' 0 ')；
b[1]:= 1；
c[1]:= 1；
而cxiaoa呢
开始
doubleb
incc
结束；
decc
fua
outit
结束。
用笔算解决约瑟夫问题
当m较小时，可以通过笔算求解。
M=2
也就是说，n个人组成一个圈，1，2，1，2，向2报到死亡，直到只剩下一个人。
当n = 2 k时，第一个报数的人是最后一个死的。
对于任意自然数，n可以表示为n = 2 k+t，其中t
所以t人死了，就只剩下2 k人了，这2 k人中第一个死的就是最后一个。这2 k人中第一个报数的人是2t+1。
于是我找到了M=2时约瑟夫问题的解:
求最大的2的不大于n的整数次幂，记为2 k，最后死的人是2 (n-2 k)+1。
M=3
就是n个人组成一个圈，当1，2，3，1，2，3报数到3就死了，直到只剩下一个人。
这比M=2时要复杂得多。
我们以N=2009为例。
当N=2009，M=3时，最后被杀的人记为F(2009，3)，也可以简单记为F(2009)。
假设现在还剩n个人，那么下一轮会杀[n/3]个人，[]表示四舍五入，还剩n-[n/3]个人。
设n人为A1，A2，...，A (N-1)，An。
从a1开始报数。一圈下来，剩下的人分别是A1，A2，A4，A5，...A (n-n mod 3-1)，A (n-n mod 3+1)，...，安。
所以你可以得到:
1.a(n-n mod 3)是本轮最后一个死的，a(n-n mod 3+1)是下一轮第一个报数的。
2.如果3|n，最后死的人是新一轮的F(n-[n/3])人。
如果n mod 3≠0且f (n-[n/3])
如果n mod 3≠0且f(n-[n/3])& gt；N mod 3，最后死的人是新回合的F(n-[n/3])-(n mod 3)人。
3.新的第K个人对应原来的3 *[(K-1)/2]+(K-1)mod 2+1个人。
综合1，2，3，我们可以得到:
F(1)=1，F(2)=2，F(3)=2，F(4)=1，F(5)=4，F(6)=1，
当f (n-[n/3])时
当f (n-[n/3])>:在n mod 3处，k=F(n-[n/3])-(n mod 3)，F(n)= 3 *[(k-1)/2]+(k-1)mod 2+1。
这个算法需要计算[log(3/2)2009]次，数量不超过22，可以用笔计算。
所以:
第一圈，669人会被杀。这一圈最后一个被杀的人是2007年，剩下1340人。
第二圈，446人死亡，还剩894人。
第三圈，298人死亡，还剩596人。
第四圈198被杀，还剩398人。
第五圈132人阵亡，还剩266人。
第六圈杀了88人，剩下178人。
第七圈杀了59人，剩下119人。
第八圈，39人死亡，还剩80人。
第九圈，26人被杀，还剩54人。
第十圈18被杀，还剩36人。
十一圈，杀了12人，剩下24人。
十二圈，杀了8个人，剩下16个人。
十三圈，杀5人，剩下11人。
十四圈，死了三个人，剩下八个人。
十五圈，死了两个，还剩六个。
F(1)=1，F(2)=2，F(3)=2，F(4)=1，F(5)=4，F(6)=1，
然后推回去。
F(8)= 7 F(11)= 7 F(16)= 8 F(24)= 11 F(36)= 16 F(54)= 23 F(80)= 31 F(119)= 43 F(178
F(596)= 191 F(894)= 286 F(1340)= 425 F(2009