К(N). Таким образом,
К(N). Таким образом, для решения задачи достаточно последовательно вычислить значения К(i) для всех значений i от 1 до N.
В силу условия задачи, для вычисления значения К(i+1) достаточно использовать предыдущие значения К(j), j=1,...i, причем только те из них, для которых выполняется условие А[i+1] mod A[j] = 0. Таким образом,
К(i+1)=max{ К(j) }+1
j=1,...i,
А[i+1] mod A[j] = 0
или равно 1, если (i+1)-й элемент не делится ни на один предыдущий. Для приведенного примера функции К будет соответствовать массив К
i 1 2 3 4 5
A 5 -3 6 0 -10
E 1 1 2 3 2
Из матрицы К видно, что максимальная длина подпоследовательности равна 3, при этом последним элементом такой последовательности является 4-й элемент. Для определения номера предпоследнего (а он является последним элементом подпоследовательности, длина которой на единицу меньше максимальной длины), достаточно найти такой индекс j, для которого выполняются соотношения j=1,...i, А[i] mod A[j] = 0 и К[i] - К[j] =1.
Зная предыдущий элемент (элемент с индексом 2), аналогичным образом можно найти элемент, стоящий перед ним. Процесс заканчивается тогда, когда будет найден элемент, который является начальным элементом подпоследовательности (для которого значение функции К равно 1).
Нетрудно заметить, что элементы подпоследовательности (структура решения) восстанавливается точно в обратном порядке, в котором происходило заполнение матрицы, соответствующей подзадачам решаемой задачи.
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
