pascal编程题目,求大师解答一下这道题到底是个什么算法,(不要去搜别的答案)或给程序。

2024-11-23 02:56:12
推荐回答(1个)
回答1:

program Project7;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;
const
  maxn=1000;
var
  n,m,i:longint;
  v:array[1..maxn,0..maxn]of boolean;
  u:array[1..maxn]of boolean;
  flag:boolean;
begin
  try
    { TODO -oUser -cConsole Main : Insert code here }
    fillchar(v,sizeof(v),false);
    fillchar(u,sizeof(u),true);
    i:=0; m:=0;
    readln(n);
    while True do
    begin
      inc(i);
      inc(m,i);
      if m>=n then m:=m mod n;
      if m=0 then m:=n;
      if not v[m,(i+1)mod n] then begin
        v[m,(i+1)mod n]:=true;
        u[m]:=false;
      end
      else break;
    end;
    flag:=true;
    for i := 1 to n do
      if u[i] then begin
        writeln(i);
        flag:=false;
      end;
    if flag then writeln(-1);
    readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.


(用Delphi写的,有些没用的头尾说明可以直接去掉)

不知道你的n有多大,这个是平方级算法,n<1000可解


再研究了一下,补充一个O(n)的算法,n<10E6可解

program Project7;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;
const
  maxn=1000000;
var
  n,m,i:longint;
  v:array[0..maxn]of boolean;
  u:array[1..maxn]of boolean;
  flag:boolean;
begin
//    while not eof do
  try
    { TODO -oUser -cConsole Main : Insert code here }
    fillchar(v,sizeof(v),false);
    fillchar(u,sizeof(u),true);
    u[1]:=false;
    i:=0; m:=0;
    readln(n);
    if n<1 then halt;
    while True do
    begin
      inc(i);
      inc(m,i);
      if m>=n then m:=m mod n;
      if m=0 then m:=n;
      if m=1 then
        if not v[(i+1)mod n] then begin
          v[(i+1)mod n]:=true;
         end
         else begin break; end
      else u[m]:=false;
    end;
    flag:=true;
    for i := 1 to n do
      if u[i] then begin
        writeln(i);
        flag:=false;
      end;
    if flag then writeln(-1);
    readln;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

两个程序的原理都是找寻环节,第二个优化的原理是发现了循环节必在第一个山洞处出现,所以可以直接抛弃无效的储存空间,同时发现循环节出现的规律:n为奇数时n+1步出现循环节,n为偶数时2n+1步出现循环节,所以可以证明效率是O(n)级别的。


至于为什么会出现这个规律,目前还不清楚。。