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。这个算法后来被我称为模拟算法，模拟算法的好处在于直观形象，容易想到，这个以数组模拟了整个过程始末的算法只要稍懂指针的人就能实现。按照这样的思想，我写了如下代码：
]#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;
4、我想问还有优化余地么？我的程序是优化一次上传一次，上传一次红一次，尤其最后一次优化，就是“2”中的优化，非常兴奋地交上程序说这次定能AC结果又一次的大地红让我对模拟算法彻底绝望了。可是就在这时，一个神奇的人物出现了，他告诉我你还记得register吗。我说，啊！然后我的程序中的定义就成了这样：
]intmain(){registerintk;registerintm=1;……}…Joseph(…){registerinticount1=0;registerintjcount0=0;registerintlimiticount1=0;registerint*p_num=num;…}]#include<stdio.h>intnum[26]={0};intJoseph(intk,intm);intmain(){ intk; registerintm=1; while(1) { scanf("%d",&k); if(k==0)break; for(m=k;Joseph(k,m)==0;m++); printf("%d\n",m); } return0;}intJoseph(intk,intm){ registerinticount1=0; registerintjcount0=0; registerintlimiticount1=0; registerint*p_num=num; for(icount1=0;icount1<2*k;icount1++)num[icount1]=1; while(jcount0<k) { icount1=0; if(!(limiticount1=m%(2*k-jcount0)))limiticount1=2*k-jcount0; while(icount1<limiticount1) { if(*p_num++==1)icount1++; if(p_num==num+2*k)p_num=num; } { if(p_num-1>=num) { if(p_num-1-num<=k-1) { return0; } *(p_num-1)=0; } else { num[2*k-1]=0; } jcount0++; } } return1;}