ditui.pas

用来对一个给定数列求其递推公式。 第一行输入n

{$N+}
program ditui;
type
     dengshi=record
     xs:array[0..200] of extended;
     ans:extended;
     end;
var
a:array[1..200] of dengshi;
ans:array[0..200] of extended;
shulie:array[0..200] of extended;
i,j,k,n,num:longint;

function solve(n:longint):boolean;
var
i,j,k,t:longint;
tt:dengshi;
begin
fillchar(ans,sizeof(ans),0);
for k:=1 to n do
     begin
     i:=k;
     while (a[i].xs[i]=0) and (i<=n) do inc(i);
     if i=n+1 then exit(false);
     if i<>k then
          begin
          tt:=a[i];
          a[i]:=a[k];
          a[k]:=tt;
          end;
     for i:=k+1 to n do
          a[k].xs[i]:=a[k].xs[i]/a[k].xs[k];
     a[k].ans:=a[k].ans/a[k].xs[k];
     a[k].xs[k]:=1;
     for i:=k+1 to n do
          begin
          for j:=k+1 to n do
               a[i].xs[j]:=a[i].xs[j]*a[k].xs[k]-a[i].xs[k]*a[k].xs[j];
          a[i].ans:=a[i].ans*a[k].xs[k]-a[k].ans*a[i].xs[k];
          a[i].xs[k]:=0;
          end;
     end;
for i:=n downto 1 do
     begin
     if abs(a[i].ans)<1e-6 then
          begin ans[i]:=0; continue; end;
     ans[i]:=a[i].ans;
     for j:=i+1 to n do
          ans[i]:=ans[i]-a[i].xs[j]*ans[j];
     ans[i]:=ans[i]/a[i].xs[i];
     end;
exit(true);
end;

function check(k:longint):boolean;
var
i:longint;
zhi:extended;
begin
zhi:=0;
for i:=1 to n do
     zhi:=zhi+shulie[k-i]*ans[i];
if abs(zhi-shulie[k])<1e-6 then exit(true) else exit(false);
end;

function success:boolean;
var
i:longint;
begin
for i:=n+1 to num do
     if not check(i) then exit(false);
exit(true);
end;

begin
assign(input,'ditui.in');
assign(output,'ditui.out');
reset(input);
rewrite(output);
readln(num);
for i:=1 to num do
     read(shulie[i]);
for n:=1 to num-1 do
     begin
     fillchar(a,sizeof(a),0);
     for i:=1 to n do
          begin
          a[i].ans:=shulie[i+n];
          for j:=1 to n do
               a[i].xs[n-j+1]:=shulie[i+j-1];
          end;
     if not solve(n) then continue;
     if success then
     begin
     write('f(n)=');
     i:=1;
     while abs(ans[i])<1e-6 do inc(i);
     if ans[i]<0 then write('-');
     write(abs(ans[i]):0:6);
     write('f(n-',i,')');
     for i:=i+1 to n do
          begin
          if abs(ans[i])<1e-6 then continue;
          if ans[i]>0 then write('+') else write('-');
          write(abs(ans[i]):0:6);
          write('f(n-',i,')');
          end;
     break;
     end;
     end;
close(input);
close(output);
end.