На этой странице приведены несколько исправленных упражнений по алгоритмам, в частности по парадигме «разделяй и властвуй» и динамическому программированию.

Упражнение 1

Напишите псевдокод для разделяй и властвуй алгоритм нахождения позиции наибольшего элемента в массиве чисел. Напишите псевдокод алгоритма перебора, сравните с предыдущим. Покажите дерево процесса алгоритма «разделяй и властвуй». Каков максимальный уровень дерева для чисел?

исправлены алгоритмы упражнений Разделяй и властвуй парадигма динамического программирования

Алгоритм грубой силы тривиален: цикл.

На каждом уровне l полное бинарное дерево состоит из 2^(l-1) листьев. Таким образом, общее количество вершин равно 2 ^ l -1. Пусть l будет уровнем дерева, поэтому l=sup(log_2 (n)).

Упражнение 2

Напишите псевдокод для алгоритма «разделяй и властвуй» для задачи возведения в степень вычисления a^n, где a>0 и n — целое положительное число. Напишите псевдокод алгоритма перебора, сравните с предыдущим. Покажите дерево процесса алгоритма «разделяй и властвуй». Какой максимальный уровень дерева для n не задан? Проверить прекращение, правильность и полноту.

Упражнение 3

Вам дан массив с целыми числами (положительными, отрицательными, нулем), и вы должны найти максимальную непрерывную сумму в этом массиве. Следовательно, вам нужно найти подмассив, который дает наибольшую сумму. Пример, если данный массив: 5, -6, 7, 12, -3, 0, -11, -6

Предположим, что ваш входной массив называется A. Что вам нужно сделать, так это сформировать другой массив, скажем, B, в котором каждое значение i вычисляется с использованием рекурсивной формулы max(A[i], B[i-1]+A[i ])

Что вы делаете эффективно, так это то, что вы выбираете, продлить ли предыдущее окно или открыть новое. Вы можете сделать это, так как вы должны выбирать только непрерывные элементы как часть ваших подмножеств.

5, -6, 7, 12, -3, 0, -11, -6

Ответ будет 19 (из подмассива {7,12} )

Упражнение 4

Используйте самую длинную общую подстроку для: BDCABA и ABCBDAB

исправлены алгоритмы упражнений Разделяй и властвуй парадигма динамического программирования

Упражнение 5

Адаптировать самую длинную общую подпоследовательность к самой длинной общей подпоследовательности: BDCABA и ABCBDAB. Проблема самой длинной общей подпоследовательности (LCS) — это проблема нахождения самой длинной общей подпоследовательности для всех последовательностей в наборе последовательностей (часто всего двух последовательностей).

Он отличается от задач поиска общих подстрок: в отличие от подстрок, подпоследовательности не обязаны занимать последовательные позиции в исходных последовательностях.

Упражнение 6

Расстояние Левенштейна — это строковая метрика для измерения разницы между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (т. е. вставок, удалений или замен), необходимых для замены одного слова другим. Предложите динамическую программу для решения этой задачи. Тест с MEILENSTEIN и LEVENSHTEIN.

Делиться
ru_RURU