Информация о задаче

Задача 76269

Тема:

[

Индуктивные функции

]

Сложность: 2
Классы:

Прислать комментарий

Условие

(Сообщил Д. В.Варсанофьев) Даны две последовательности целых чисел 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. Функция $\langle$ x[1]...x[n1] $\rangle$ $\mapsto$ [максимальное k1, для которого y[1]...y[k1] есть подпоследовательность x[1]...x[n1]] индуктивна.

Источники и прецеденты использования


книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	3
Название	Индуктивные функции (по А.Г.Кушниренко)
задача
Номер	1.3.2