(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 вариант) Функция x[1]..x[n1] |-< (максимальное k1, для которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) индуктивна.  8  Комментарии к статье  8 8  Обсудить в чате