chain.pas

本光盘是《国际大学生程序设计竞赛例题解（一）》的配套光盘

program chain;
type
  tp=array[1..2000] of integer;
const
  in_f='chain.dat';out_f='chain.out';
var
  f:text;
  a,b:tp;
  an,n:longint;

procedure init;
begin
  assign(f,in_f);
  reset(f);

  readln(f,an);

  close(f);
end;

procedure trial(m:integer);
var i:integer;
begin
  if m>n then exit;
  if a[m-1]=an then
  begin
    n:=m-1;
    b:=a;
    exit;
  end;

  for i:=m-1 downto 1 do
    if a[i]+a[m-1]<=an then
    begin
      a[m]:=a[i]+a[m-1];
      if (n-m-1>=10) or (a[m]*(2 shl (n-m-1))>=an) then trial(m+1);
    end;
end;

procedure main;
var i:integer;
begin
  a[1]:=1;
  n:=2*trunc(sqrt(an)+0.5)+1;
  trial(2);

  assign(f,out_f);
  rewrite(f);
  writeln(f,n);
  for i:=1 to n do
    write(f,b[i],' ');
  writeln(f);
  close(f);
end;

begin
  init;
  main;
end.

10
4
1025

3
47
100
203
411
611
911
1000
993