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

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

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.

Leave a Comment

16 − = 7