Даны две последовательности целых чисел x[1] ... x[n] и y[1] ... y[k]. Определить, является ли вторая последовательность подпоследовательностью первой
Категория: Delphi/Pascal
2012-01-29 22:09:49
Т.е. можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка 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.
Поделиться: