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

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

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

Упражнение 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

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

Решение

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

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

Делиться
ru_RURU
%d такие блоггеры, как: