3. а) Напишите псевдокод декомпозиционного алгоритма для вычисления аn , где a>0, n – натуральное число.
б) Напишите и решите (для n=2k) рекуррентное соотношение для количества умножений, выполняемых алгоритмом.
в) Сравните созданный вами алгоритм с алгоритмом для решения указанной задачи, основанным на грубой силе.
5. Найдите порядок роста следующих рекуррентных соотношений.
а) T
=4T(n/2)+n, T(1)=1.
б) T=4T(n/2)+n2, T(1)=1.
в) T=4T(n/2)+n3, T(1)=1.
6. Примените сортировку слиянием для упорядочнения букв E, X, A, M, P, L, E в алфавитном порядке.
8. а) Решите рекуррентное соотношение для количества сравнений ключей, выполняемых сортировкой слиянием в наихудшем случае. (Можно считать, что n=2k.)
б) Напишите рекуррентное соотношение для количества сравнений ключей, выполняемых алгоритмом сортировки слиянием в наилучшем случае, и решите его при n=2k.
в) Напишите рекуррентное соотношение для количества перемещений ключей, выполняемых описанной в разделе 4.1 версией алгоритма сортировки слиянием. Изменится ли класс эффективности алгоритма, если учесть количество перемещений ключей?
9. Можно ли реализовать сортировку слиянием без рекурсии, начав со слияния соседних элементов данного массива, затем – отсортированных пар и т.д. Реализуйте такую восходящую версию алгоритма на своем любимом языке программирования.
10. Триомино – элемент мозаичного заполнения в форме L, образованный тремя квадратами шахматной доски. Задача состоит в покрытии триомино шахматной доски размером 2nЧ2n с одной вырезанной в произвольном месте клеткой. Триомино должны покрывать все клетки, за исключением вырезанной, без пропусков и перекрытий.
Разработайте декомпозиционный алгоритм для решения этой задачи.
Желательно на паскале
б) Напишите и решите (для n=2k) рекуррентное соотношение для количества умножений, выполняемых алгоритмом.
в) Сравните созданный вами алгоритм с алгоритмом для решения указанной задачи, основанным на грубой силе.
5. Найдите порядок роста следующих рекуррентных соотношений.
а) T
=4T(n/2)+n, T(1)=1.б) T
=4T(n/2)+n2, T(1)=1.в) T
=4T(n/2)+n3, T(1)=1.6. Примените сортировку слиянием для упорядочнения букв E, X, A, M, P, L, E в алфавитном порядке.
8. а) Решите рекуррентное соотношение для количества сравнений ключей, выполняемых сортировкой слиянием в наихудшем случае. (Можно считать, что n=2k.)
б) Напишите рекуррентное соотношение для количества сравнений ключей, выполняемых алгоритмом сортировки слиянием в наилучшем случае, и решите его при n=2k.
в) Напишите рекуррентное соотношение для количества перемещений ключей, выполняемых описанной в разделе 4.1 версией алгоритма сортировки слиянием. Изменится ли класс эффективности алгоритма, если учесть количество перемещений ключей?
9. Можно ли реализовать сортировку слиянием без рекурсии, начав со слияния соседних элементов данного массива, затем – отсортированных пар и т.д. Реализуйте такую восходящую версию алгоритма на своем любимом языке программирования.
10. Триомино – элемент мозаичного заполнения в форме L, образованный тремя квадратами шахматной доски. Задача состоит в покрытии триомино шахматной доски размером 2nЧ2n с одной вырезанной в произвольном месте клеткой. Триомино должны покрывать все клетки, за исключением вырезанной, без пропусков и перекрытий.
Разработайте декомпозиционный алгоритм для решения этой задачи.
Желательно на паскале