回 帖 发 新 帖 刷新版面

主题:pascal程序难题(答得好给分)

新年联欢会上,全班M名同学,围成一圈,按1——M顺序编号(要求M〈=40),然后从队头开始1,2,3报数,数3的出列,剩下的同学再从头开始1,2,3报数……直到剩下最后一名同学时,这名同学就是本年度的“幸运使者”,问这名同学原来的位置是多少?

回复列表 (共8个回复)

沙发

经典的约瑟夫问题,这个用模拟就可以了。

板凳

var
  a:array[1..10000] of integer;
  n,s,i,j:integer;
  begin
  read(m,n);
  for i:=1 to m do a[i]:=1;
  j:=0;
  for i:=1 to m do
  begin
  s:=0;
  while s<n do
  begin
  if j<m then inc(j)
  else j:=1;
  s:=s+a[j];
  end;
  write(j);
  a[j]:=0;
  end;
  end.

3 楼

数组直接模拟数据大会爆,建议改成链表,还有可以用数学方法O(1)

4 楼

同意LS。

5 楼

var m:integer;
    a:array[1..40]of 0..1;
    i,j,n,s:integer;
begin
  readln(m);
  for i:=1 to m do a[i]:=1;
  j:=0;
  repeat
  n:=0;
  repeat
    j:=j+1;
    n:=n+1;
    if a[n]=0 then j:=j-1;
    if (j=3) and (a[n]<>0) then
    begin
      a[n]:=0;
      j:=0;
    end;
    begin
      s:=0;
      for i:=1 to m do if a[i]=1 then s:=s+1;
    end;
  until (n=m) or (s=1);
  until s=1;
  for i:=1 to m do if a[i]=1 then writeln(i);
end.

6 楼

约瑟夫问题,用一个数组存放第i个人有没有出列,简单枚举

7 楼

这不就是猴子选大王吗,那本中学信息学书上有(蓝色的),自己去看!咩~给点分吧~咩~

8 楼


我这里有讲解
填空
[fly]加分吧!!![/fly]
约瑟夫问题:设有n个人编号分别为1~n,围坐在一个圆桌周围。现从第一个人开始报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m个人又出列,…,如此重复,直到所有人都出列为止。输入n和m,求出出列的顺序表。例如当n=8,m=5时,出列的顺序表是:5 2 8 7 1 4 6 3。
提示:程序中i表示人的编号,j表示已出列的人数,s表示当前所报的数字,布尔数组a[i]用来标记第i个人有没有出列。
var 
  a:array[1..10] of boolean;
  i,j,s,n,m:integer;
begin
  readln(n,m);
  for i:=1 to n do a[i]:=true;
  i:=0; j:=0; s:=0;
  repeat
    i:=i+1;
    if i>n then(     );
    if a[i] then begin
      (        );
       if s=m then begin
          (          );
           write(i:4);
          (          );
           j:=j+1;
       end;
    end;
  until(      );
end.

我来回复

您尚未登录,请登录后再回复。点此登录或注册