redund.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program E1_4; {redund}
type TFSet=set of 'A'..'Z';
     TFD=record
         set1,set2:TFSet;
         end;
var n:byte;
    flag:boolean;
    fd:array[1..100] of TFD;
    input,output:text;
procedure inputdata;
 var i:byte;
     s:string;
 procedure GetFieldSet(t:string; var s:TFSet);
 begin
 s:=[];
 while t<>'' do
  begin
   include(s,t[length(t)]);
   dec(t[0]);
  end;
 end;
begin
 assign(input,'redund.in');
 reset(input);
 readln(input,n);
 for i:=1 to n do
  begin
   readln(input,s);
   GetFieldSet(copy(s,1,pos('->',s)-1),fd[i].set1);
   delete(s,1,pos('->',s)+1);
   GetFieldSet(s,fd[i].set2);
  end;
  close(input);
end;

procedure find;
var k:byte;
    s:string;
 function search(p:byte):string;
 var ss:array[1..100] of TFSet;
     FDPath:array[1..100] of byte;
     i,depth,mindepth:byte;
     s,t:string;
 begin
 s:='';
 ss[1]:=fd[p].set1;
 FDPath[1]:=0; depth:=1; mindepth:=255;
 while depth>0 do
  begin
   if fd[p].set2<=ss[depth] then
    if depth<mindepth then
      begin
      s:='';
      for i:=1 to depth-1 do
       begin
        str(FDPath[i],t);
        s:=s+' '+t;
       end;
       mindepth:=depth;
       end
      else dec(depth)
    else
     begin
      repeat inc(FDPath[depth])
      until (FDPath[depth]>n) or ((FDPath[depth]<>p)and
       (fd[FDPath[depth]].set1<=ss[depth]) and
       not(fd[FDPath[depth]].set2<=ss[depth]));
      if FDPath[depth]>n then dec(depth)
         else
          begin
          FDPath[depth+1]:=0;
          ss[depth+1]:=ss[depth]+fd[FDPath[depth]].set2;
          inc(depth);
          end;
     end;
    end;
    search:=s;
  end;
 begin {find}
  assign(output,'redund.out');
  rewrite(output);
  flag:=false;
  for k:=1 to n do
   begin
    s:=search(k);
    if s<>'' then
     begin
     writeln(output,'FD ',k,' is redundant using FDs:',s);
     flag:=true;
     end;
    end;
    if not flag then writeln(output,'No redundant FDs.');
    close(output);
 end;

begin {main}
 inputdata;
 find;
end.