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

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

2. Найдите явные выражения для f(n), исключив рекурсию из следующих определений
а) {?(f(0)=1@f(k)=2f(k-1) )?; б) {?(f(0)=2@f(k)=f(k-1)!/k!)?

3. Вычислите значение функции Аккермана: Аккер(3,4)
4. Сколько нужно выполнить перемещений в задаче о Ханойской башне, если число дисков равно 10?
5.Назвать число выигрышных номеров в задаче Иосифа Флавия для отряда из 48 воинов.
7. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;
например: 2?| | , 5 ? | | | | | , 0 ? <пустое слово>.
а) A={a,b,c}. Приписать слева к слову P символ b (P ? bP);
б) A={a,b}. Заменить в P каждое вхождение a на bb.
8. Пусть для слов в алфавите А={a,b,c} заданы следующие марковские подстановки:
b?a; c?b; ab?bc; bc?ca; ca?ab; abc??; bca??; cab??; abca?a; bcab??; a?b
Примените каждую из данных подстановок к слову bcabcabcabca.
9. Нормальный алгоритм в алфавите А={a,b,1} задается схемой: a?1; b?1. Примените его к слову а) ababaa; б) abaabbb.
Литература

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


"