Даны две последовательности целых чисел x[1] ... x[n] и y[1] ... y[k]. Определить, является ли вторая последовательность подпоследовательностью первой

Т.е. можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n + k.

code: #pascal
program PascalGuru;
uses crt;
var x,y:array [1..50] of integer;
    i,n,k,n1,k1:integer;
    s,strx,stry:string;
 
begin
write('n= ');  readln(n);
write('k= ');  readln(k);
 
writeln('Vvedite elementy massiva massiva "X":');
for i:=1 to n do begin
write('X[',i,']= '); readln(X[i]); end;
 
writeln('Vvedite elementy massiva massiva "Y":');
for i:=1 to k do begin
write('Y[',i,']= '); readln(Y[i]); end;
 
clrscr;
writeln('Vot vvedenye vami massiv "X": ');
for i:=1 to n do write(X[i],', ');
writeln;
writeln('Vot vvedenye vami massiv "Y": ');
for i:=1 to k do write(Y[i],', ');
writeln;
writeln;
{--------------------------------------------------------------}
 n1:=n;
 k1:=k;
  {инвариант:  искомый ответ <=> возможность из x[1]..x[n1] по-
   лучить y[1]..y[k1] }
  while (n1 > 0) and (k1 > 0) do begin
   if x[n1] = y[k1] then begin
    n1 := n1 - 1;
    k1 := k1 - 1;
   end else begin
    n1 := n1 - 1;
   end;
  end;
  {n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 <>  0
   (и n1 = 0), то ответ - нет}
 
 if k1 = 0 then writeln('DA');
 if (k1<>0) and (n1=0) then writeln('NET');
{--------------------------------------------------------------}
 
 
readln;
end.      
Поделиться:

Похожие статьи: