Контрольная Теория алгоритмов вариант 3, номер: 172747

"Вариант 3
1. Найдите f(2), f(3), f(4), f(5) для следующих рекурсивных функций

2. Найдите явные выражения для f(n), исключив рекурсию из следующих определений
а) ; б)
3. Вычислите значение функции Аккермана: Аккер(4,4)
4. Сколько нужно выполнить перемещений в задаче о Ханойской башне, если число дисков равно 12?
5.Назвать число выигрышных номеров в задаче Иосифа Флавия для отряда из 48 воинов.
6. Рассортируйте последовательность х,а,ж,у,р,п,з,ф,т,м,ю,б,д,н,с, используя:
а) сортировку выбором;
б) пузырьковую сортировку;
в) сортировку слиянием;
г) быструю сортировку;
д) сортировку вставками.
7. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;
например: 2?| | , 5 ? | | | | | , 0 ? <пустое слово>.
а) A={a,b,c}. Заменить на а каждый второй сомвол в слове P.
б) A={a,b}. Удвоить слово Р.
8. Пусть для слов в алфавите А= заданы следующие марковские подстановки:
; c ; ; ; ; ; ; ; ; ;
Примените каждую из данных подстановок к слову bcabcabcabca.
9. Нормальный алгоритм в алфавите А= задается схемой: ; . Примените его к слову а) ааа б)ааbbb11.

Литература
1. Кнут Д. Искусство программирования для ЭBM. Основные алгоритмы: т. 1, M.: Мир, 1976.
2. Кнут Д. Искусство программирования для ЭBM. Сортировка и поиск: т. 3, М.: Мир, 1978.
3. Лекции лауреатов премии Тьюринга. М.: Мир, 1985.
4. Бауэр Ф.Л., Гнац Р., Хилл У. Информатика. Задачи и решения. М.: Мир, 1978 г.
5. Бауэр Ф.Л., Гооз Г. Информатика. T. 1, М.: Мир, 1990 г.
6. Бауэр Ф.Л., Гооз Г. Информатика. T. 2, М.: Мир, 1990 г.

"