Задача 76269
|
|
 |
Условие
(Сообщил Д. В.Варсанофьев) Даны две последовательности
целых чисел
x[1]...x[n]
и
y[1]...y[k]. Выяснить, является ли вторая
последовательность подпоследовательностью первой, то есть
можно ли из первой вычеркнуть некоторые члены так, чтобы
осталась вторая. Число действий порядка
n + k.
Решение
Вариант 1. Будем сводить задачу к задаче меньшего размера.
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), то ответ - нет}
answer := (k1 = 0);
Мы использовали то, что если
x[n1] = y[k1]
и
y[1]...y[k1] — подпоследовательность
x[1]...x[n1], то
y[1]...y[k1-1] —
подпоследовательность
x[1]...x[n1-1].
Вариант 2. Функция
