约瑟夫斯问题一解


1994-07-29

        有N个人围成一个圆圈，按一个方向顺序给他们编上号码。然后从第S个人开始数起，数到M时，就让这个人出列，再从下一个人数起，再数到M时，那个人也出列。如此继续下去，直到全部出列为止。要求写一程序，按出列先后顺序打印出编号。N、S、M的值分别取12、6、4，则出列顺序为9、1、5、10、3、8、4、12、11、2、7、6。
        此问题的常见解法有两种。一种利用链表将这N个编号用N个结点链接起来，利用链表指针及结点的删除求解。二是利用数组模拟链表求解。本文给出的解法与前两种不同，它紧扣题目，巧用数字0、1进行计数，方法简单可行。源程序附后。
        程序说明：
        一、 出列与否的表示法
        A(I)=1表示编号为I的人没出列
        0表示编号为I的人已出列〗
        I=1、2、……、N。
        二、过程REPTBODY描述了出列的规则。其中计数语句不是常用的CN=CN+，而是CN=CN+A(I)。此语句中，因为A(I)=0表示出列，故等于不数。这是本程序的技巧之一。
        三、若S=1，语句REPTBODY(S，N，CN，COANT)可以省略。
        四、执行程序前，先设置常量N的值。本程序中N=12。
        五、本程序采用TURBO PASCAL 6.0版本，在AST286机上调试通过。
        program jo;
        const
        n=12;
        type
        Number=1..n;
        var
        a:array  of 0..1;
        cn,count,i,s,m:integer;
        procedure reptbody(fv,ev:integer; var cn,count:integer);
        begin
        for i:=fv to ev do
        begin
        cn:=cn+a;
        if cn=m then
        begin
        cn:=0;
        a:=0;
        write(i,' ');
        count:=count+1;
        end;
        end;
        end;
        begin
        for i:=1 to n do
        a:=1;
        write('from where?');
        readln(s);
        write('step=');
        readln(m);
        cn:=0;
        count:=0;
        reptbody(s,n,cn,count);
        repeat
        reptbody(1,n,cn,count);
        until count=n;
        end.
 
 