POJ 1012——又解一遍艰难的约瑟夫
POJ 1012——再解一遍艰难的约瑟夫
嗯我是个本科生新手，学C语言半年左右，这是我写的解北大OnlineJudge上的1012号问题的心得，刚写出来的，望各位高手斧正哈~~
POJ1012——再解一遍艰难的约瑟夫
历时三天，这个想得我脑袋都快想爆了的问题终于AC了……在一次次充满希望地提交代码却得到一个个大红的TimeLimitExceeded之后，终于得到四个天蓝的Accepted的我实在太高兴，太振奋~于是谨以此文记之~
在我这，这个Joseph衍生问题称得上艰难，而且一度令我感到束手无策。即使我已经先后成功设计、实现、优化了该问题的模拟算法和数学算法，各类问题却仍然层出不穷，就更别说设计数学算法的路走得有多泥泞多崎岖。
问题是这样的：
约瑟夫
时间限制：1000MS/10000MS运行内存限制：10000K
约瑟夫的问题是出了名的。从N个人中，编号为1，2，。。，N站在圈，每个m都会被枪决，只有最后剩下的人能够活命。约瑟夫是足够聪明的选择最后剩下的人的位置，从而拯救了他的生命，给我们的有关事件的消息。例如，当n=6，M=5，那么被杀的顺序是5，4，6，2，3，1
现在假设有k个好人和k个坏人。在圈内的前k个是好人好人和后k个是坏人。您必须确定一个最小的m，使得好人被杀前，坏人全部都被杀掉。
输入：k，输出m
因为约瑟夫环的程序我之前曾经写过，是在谭浩强那本书的8.5，于是我最初的想法是参照原来写的约瑟夫函数再写一个衍生函数，再加上遍历m去试的部分就OK。于是我写了一个返回值为bool型的Joseph函数，该函数的功能是：传入k、m，判断是否满足题述条件并返回判断结果。bool型是C99新增的逻辑变量，长度只有1字节，只有true或false两个取值。实际上就是1和0。而该函数的具体算法是：定义一个长度为2k的数组，用来代表每个人的活着（true）或被杀（false）状态，然后用一个指针变量p按顺序去数m个true（活着的人），将第m个true改写为false（杀死此人），而后检查此人是不是好人，如果好人被错杀，则函数立刻返回false。而这个判断显然是非常容易的，只需利用指针减法p–&a[0]<k就可判断此人是好人。若直至杀了第k个人还没有好人被错杀，函数就返回true，这样一来主函数中遍历m的循环体一旦得到了Joseph函数的true返回值就直接break掉，而m的当前值就是满足条件的最小的m。这个算法后来被我称为模拟算法，模拟算法的好处在于直观形象，容易想到，这个以数组模拟了整个过程始末的算法只要稍懂指针的人就能实现。按照这样的思想，我写了如下代码：
舍友也写了类似的程序，他比我先写完，并且告诉我他的程序算出k=10的情况可能需要一年。我不信，1、2、3……一切顺利，当我打到8的时候，他的窗口卡了一下，竟然给出了7632！我输入10，按回车，结果他的程序沉默了……我赶紧查了一下该问题的几个输出结果，当时我还没有意识到接下来的三天我会多么频繁地接触这些数据以至于可以将k<10的情况背下来：
93313！怪不得没反应了，7632都卡！……我赶紧写完了我的程序，期望一直坚守的比较谨慎的代码风格能够让我不卡死在10上。1，2、2,7……9，1740、10……………………………………
而终于我的程序也卡在了10上，过了好半天才给出正确的数值。现在问题摆在眼前——不是算不出来，而是速度不行，我抱着试试看的态度提交进了POJ系统……什么？Compileerror？翻开错误信息，原来是POJ的C编译器不能理解bool变量，好吧……替换掉了bool变量之后再提交，TimeLimitExceeded。
下面该如何优化呢？
经过N长时间的思考以及他人的提醒和启发，我对模拟算法的优化主要总结成了以下几点：
1、 遍历m的循环不必从m=1开始，因为m<=k时都会第一个就杀好人，所以m至少也要从k+1算起。（遗憾的是当时未按照此思路想下去，事实上，只有满足m%(k+1)==0或m%(k+1)==1条件的m才可能满足题设条件，也就是说不满足这两个条件的m可以丢弃，后面还会提到，这是我最后数学算法的关键优化措施）
2、 我的模拟算法中，要数1(true)数到m才杀人，而上面那个结果表已经说明m可能是一个很大的数，那么如果m是100000，k是12，假设目前杀到了剩20个人，那么数100001个人就意味着指针把这个数组遍历了[100001/20]=5000次然后才动手杀人（[]在数学里表示取整）！杀一个人的成本如此之高，就更别说有那么多人要杀，一个m尚且如此，一堆上万、上十万的还要一个一个地遍历的m怎么办？这就是这个模拟算法致命的缺点。而优化掉这个缺点可以采用如下方式：将while(icount0<m)替换为while(icount0<limiticount0)，而limiticount0=m%(2*k–jcount0)，其中jcount0是目前已经被杀掉的人数。什么意思呢？2*k是总人数，2*k–jcount0就是还剩下的人数，指针要数活着的人，从1开始数到m，m很大的时候，指针做了许多无用功，这里采取的办法就是把无用功“滤掉”，有点类似数学里的弧度数，3π就是π，101π还是π，1000001π还是π。这样的处理就让指针每次遍历的元素数不超过当前总人数(2*k–jcount0)，而k的范围是:0<k<14，这就决定了指针每次顶多遍历26次。不过到这还没有完，如果limiticount0==0会怎样？循环体不运行，直接杀死指针当前指向的人，而指针还呆在上一次杀人的地方没动，难道还要把死人挖出来鞭尸吗？这显然不是我们的原意，而这里只有limiticount0==0是出错的，因为指针指着一个死人；只要limiticount0>0，指针不论怎么数，最后都一定停在活人身上。那limiticount0==0怎么办呢？我采取的办法是让limiticount0=(2*k–jcount0)，这样就一定能停在活人身上，至于停的正确性则大可不必怀疑，limiticount0==0只是让指针走不动而已，只要指针走起来，按照(2*k–jcount0)的周期，少走几周是无所谓的，而这里采用了最少的，让它走1周。好分析到此结束，优化代码最终是这样的：if(!(limiticount1=m%(2*k-jcount0)))limiticount1=2*k-jcount0;
3、 第2条让程序效率翻了倍，再测试时，k=10的情况会秒杀，k=11稍显缓慢，12、13就要将近2秒的时间才能出，而这显然还没有达到1000ms的要求。怎么办？模拟算法还有前途吗？有还是有的，只是不那么无量。我优化掉了函数体里的定义数组intnum[2*k]，变成了全局数组inta[26]。每次运行函数都要定义这个数组变成了只需定义一次，这算是一点点改进；另外，我还试图优化掉Joseph函数开头的数组初始化，for(icount1=0;icount1<2*k;icount1++)num[icount1]=1;我尝试利用m的不同，即对于每个m，非m的值都代表此人活着，m值代表此人已被杀，但后来经证实这一做法是有很大隐患的，所以最终被舍弃，在此不赘述。
嗯我是个本科生新手，学C语言半年左右，这是我写的解北大OnlineJudge上的1012号问题的心得，刚写出来的，望各位高手斧正哈~~
POJ1012——再解一遍艰难的约瑟夫
历时三天，这个想得我脑袋都快想爆了的问题终于AC了……在一次次充满希望地提交代码却得到一个个大红的TimeLimitExceeded之后，终于得到四个天蓝的Accepted的我实在太高兴，太振奋~于是谨以此文记之~
在我这，这个Joseph衍生问题称得上艰难，而且一度令我感到束手无策。即使我已经先后成功设计、实现、优化了该问题的模拟算法和数学算法，各类问题却仍然层出不穷，就更别说设计数学算法的路走得有多泥泞多崎岖。
问题是这样的：
约瑟夫
时间限制：1000MS/10000MS运行内存限制：10000K
约瑟夫的问题是出了名的。从N个人中，编号为1，2，。。，N站在圈，每个m都会被枪决，只有最后剩下的人能够活命。约瑟夫是足够聪明的选择最后剩下的人的位置，从而拯救了他的生命，给我们的有关事件的消息。例如，当n=6，M=5，那么被杀的顺序是5，4，6，2，3，1
现在假设有k个好人和k个坏人。在圈内的前k个是好人好人和后k个是坏人。您必须确定一个最小的m，使得好人被杀前，坏人全部都被杀掉。
输入：k，输出m
因为约瑟夫环的程序我之前曾经写过，是在谭浩强那本书的8.5，于是我最初的想法是参照原来写的约瑟夫函数再写一个衍生函数，再加上遍历m去试的部分就OK。于是我写了一个返回值为bool型的Joseph函数，该函数的功能是：传入k、m，判断是否满足题述条件并返回判断结果。bool型是C99新增的逻辑变量，长度只有1字节，只有true或false两个取值。实际上就是1和0。而该函数的具体算法是：定义一个长度为2k的数组，用来代表每个人的活着（true）或被杀（false）状态，然后用一个指针变量p按顺序去数m个true（活着的人），将第m个true改写为false（杀死此人），而后检查此人是不是好人，如果好人被错杀，则函数立刻返回false。而这个判断显然是非常容易的，只需利用指针减法p–&a[0]<k就可判断此人是好人。若直至杀了第k个人还没有好人被错杀，函数就返回true，这样一来主函数中遍历m的循环体一旦得到了Joseph函数的true返回值就直接break掉，而m的当前值就是满足条件的最小的m。这个算法后来被我称为模拟算法，模拟算法的好处在于直观形象，容易想到，这个以数组模拟了整个过程始末的算法只要稍懂指针的人就能实现。按照这样的思想，我写了如下代码：
- C/C++ code
]#include<stdio.h>
#include<stdbool.h>
boolJoseph(intk,intm);
intmain()
{
intk;
intm=1;
scanf("%d",&k);
for(m=1;Joseph(k,m)==false;m++);
printf("%d\n",m);
getch();
return0;
}
boolJoseph(intk,intm)
{
inti;
inticount0=0;
intjcount1=0;
boolnum[2*k];
bool*p_num=num;
boolresult=true;
num[0]=true;
for(i=0;i<2*k;i++)num[code=C/C++]]=true;
while(jcount1<k)
{
icount0=0;
while(icount0<m)
{
if(*p_num++==true)icount0++;
if(p_num>&num[2*k-1])p_num=&num[0];
}
{
if(p_num-1>=&num[0])
{
if(p_num-1-num<=k-1)
{
returnfalse;
}
*(p_num-1)=false;
}
else
{
num[2*k-1]=false;
}
jcount1++;
}
}
returntrue;
舍友也写了类似的程序，他比我先写完，并且告诉我他的程序算出k=10的情况可能需要一年。我不信，1、2、3……一切顺利，当我打到8的时候，他的窗口卡了一下，竟然给出了7632！我输入10，按回车，结果他的程序沉默了……我赶紧查了一下该问题的几个输出结果，当时我还没有意识到接下来的三天我会多么频繁地接触这些数据以至于可以将k<10的情况背下来：
93313！怪不得没反应了，7632都卡！……我赶紧写完了我的程序，期望一直坚守的比较谨慎的代码风格能够让我不卡死在10上。1，2、2,7……9，1740、10……………………………………
而终于我的程序也卡在了10上，过了好半天才给出正确的数值。现在问题摆在眼前——不是算不出来，而是速度不行，我抱着试试看的态度提交进了POJ系统……什么？Compileerror？翻开错误信息，原来是POJ的C编译器不能理解bool变量，好吧……替换掉了bool变量之后再提交，TimeLimitExceeded。
下面该如何优化呢？
经过N长时间的思考以及他人的提醒和启发，我对模拟算法的优化主要总结成了以下几点：
1、 遍历m的循环不必从m=1开始，因为m<=k时都会第一个就杀好人，所以m至少也要从k+1算起。（遗憾的是当时未按照此思路想下去，事实上，只有满足m%(k+1)==0或m%(k+1)==1条件的m才可能满足题设条件，也就是说不满足这两个条件的m可以丢弃，后面还会提到，这是我最后数学算法的关键优化措施）
2、 我的模拟算法中，要数1(true)数到m才杀人，而上面那个结果表已经说明m可能是一个很大的数，那么如果m是100000，k是12，假设目前杀到了剩20个人，那么数100001个人就意味着指针把这个数组遍历了[100001/20]=5000次然后才动手杀人（[]在数学里表示取整）！杀一个人的成本如此之高，就更别说有那么多人要杀，一个m尚且如此，一堆上万、上十万的还要一个一个地遍历的m怎么办？这就是这个模拟算法致命的缺点。而优化掉这个缺点可以采用如下方式：将while(icount0<m)替换为while(icount0<limiticount0)，而limiticount0=m%(2*k–jcount0)，其中jcount0是目前已经被杀掉的人数。什么意思呢？2*k是总人数，2*k–jcount0就是还剩下的人数，指针要数活着的人，从1开始数到m，m很大的时候，指针做了许多无用功，这里采取的办法就是把无用功“滤掉”，有点类似数学里的弧度数，3π就是π，101π还是π，1000001π还是π。这样的处理就让指针每次遍历的元素数不超过当前总人数(2*k–jcount0)，而k的范围是:0<k<14，这就决定了指针每次顶多遍历26次。不过到这还没有完，如果limiticount0==0会怎样？循环体不运行，直接杀死指针当前指向的人，而指针还呆在上一次杀人的地方没动，难道还要把死人挖出来鞭尸吗？这显然不是我们的原意，而这里只有limiticount0==0是出错的，因为指针指着一个死人；只要limiticount0>0，指针不论怎么数，最后都一定停在活人身上。那limiticount0==0怎么办呢？我采取的办法是让limiticount0=(2*k–jcount0)，这样就一定能停在活人身上，至于停的正确性则大可不必怀疑，limiticount0==0只是让指针走不动而已，只要指针走起来，按照(2*k–jcount0)的周期，少走几周是无所谓的，而这里采用了最少的，让它走1周。好分析到此结束，优化代码最终是这样的：if(!(limiticount1=m%(2*k-jcount0)))limiticount1=2*k-jcount0;
3、 第2条让程序效率翻了倍，再测试时，k=10的情况会秒杀，k=11稍显缓慢，12、13就要将近2秒的时间才能出，而这显然还没有达到1000ms的要求。怎么办？模拟算法还有前途吗？有还是有的，只是不那么无量。我优化掉了函数体里的定义数组intnum[2*k]，变成了全局数组inta[26]。每次运行函数都要定义这个数组变成了只需定义一次，这算是一点点改进；另外，我还试图优化掉Joseph函数开头的数组初始化，for(icount1=0;icount1<2*k;icount1++)num[icount1]=1;我尝试利用m的不同，即对于每个m，非m的值都代表此人活着，m值代表此人已被杀，但后来经证实这一做法是有很大隐患的，所以最终被舍弃，在此不赘述。