你当前的位置:网站首页> 教育教学 > 科学教研

改选美猴王,请你帮忙

发布时间 :2003-11-16 00:00:00    发布人 : admin    浏览量 : 46次
——计算机数据结构之队列设计
重庆市铜梁中学校 高远洪 邮编:402560

     
     花果山美猴王随师傅唐僧西游取得真经后,决定潜心研究经书。为免除山上俗务的干扰,美猴王提出让贤。聪明的他为猴子猴孙们想出了一个选举办法:山上的N只猴子要选大王,从头到尾1、2、3报数,凡报3的退出。余下的猴子从尾到头1、2、3报数,凡报3的退出。留下来的猴子再从头到尾报数,依此类推,当剩下的猴子数少于3时,重新报数报1的为新一届美猴王。
     一、问题提出
     现在就请你根据这个选举方法,设计程序从N个猴子中选出新一届美猴王。
     二、变量说明
     M:最大猴子数;
     N:实际猴子数;
     I:循环变量;
     A:保存猴子排列顺序的数组;
     P:报数计数器;
     R:剩余猴子计数器;
     F:报数方向标志,F=0从左到右报数,F=1从右到左报数;
     三、程序的算法设计
     设置最大猴子数M=100,读入实际猴子数N;
     将N个猴子按1、2、3、……、N编号放入数组A[1]……A[N]中;
     设剩余猴子计数器R:=N,方向标志F:=1(保证N<3时结果正确);
     当R>=3时循环,R<3时,跳至8;
     报数计数器P:=0,从左到右开始报数,如果A[I]<>0,则P=P+1;
     当P=3时,A[I]:=0;P:=0;R:=R-1,F:=0;
     报数计数器P:=0;从右到左开始报数,如果A[I]<>0,则P=P+1;
      当P=3时,A[I]:=0;P:=0;R:=R-1;F:=1;
     返回4;
     判断F的值,如果F为0表示上一次为从左到右报数,则应输出从右到左的第一个不为0的数为符合题意的猴子大王;如果F为1表示上一次为从右到左报数,则应输出从左到右的第一个不为0的数为符合题意的猴子大王。
     四、参考程序(本程序在TURBO PASCAL 6.0中调试通过)
     PROGRAM FOUNDKING(INPUT,OUTPUT);
     CONST M=100;{设置最大猴子数为100,可以改为≤32767的数}
     VAR
     N,I,P,R,F:INTEGER;
     A:ARRAY[1..M]OF INTEGER;
     BEGIN
      WRITELN;
      WRITE('INPUT N=(N<=100)');
      READLN(N);{读入实际猴子数}
     FOR I:=1 TO N DO A[I]:=I;{使数组值与下标变量相同.}
     R:=N;
     F:=1;
      WHILE R>=3 DO
      BEGIN
      P:=0;{报数计数器清0}
      FOR I:=1 TO N DO{从左到右报数}
     IF A[I]<>0 THEN
      BEGIN
      P:=P+1;
      IF P=3 THEN
      BEGIN
      A[I]:=0;
     P:=0;
     R:=R-1;
     F:=0;
     END;
      END;
      P:=0;
      FOR I:=N DOWNTO 1 DO{从右到左报数}
     IF A[I]<>0 THEN
     BEGIN
     P:=P+1;
      IF P=3 THEN
      BEGIN
      A[I]:=0;
     P:=0;
     R:=R-1;
     F:=1;
     END;
      END;
      END;
     IF F=1 THEN
     BEGIN
     WRITE('THE KING IS:');
     {根据F的值打印符合题意的猴大王。}
     FOR I:=1 TO N DO
      IF A[I]<>0 THEN