Автоматическое устройство имеет 2 кнопки и экран. при включении на экране загорается число 0. при нажатии на одну кнопку число на экране удваивается (вместо х появляется 2х при нажатии на другую кнопку число увеличивается на 1 (вместо х появляется х+1). как надо нажимать на кнопки, чтобы на экране появилось число 99, если разрешается нажимать на кнопки не более 10 раз?

Идем с конца: 1) 99 - 1 = 98 2) 98 / 2 = 49 3) 49 - 1 = 48 4) 48 / 2 = 24 5) 24 / 2 = 12 6) 12 / 2 = 6 7) 6 / 2 = 3 8) 3 - 1 = 2 9) 2 / 2 = 1 10) 1 - 1 = 0 все получилось! ответ: 2121111212

Представим, что мы знаем ответ на вопрос "чему равна сумма всех выписанных чисел при выполнении вызова f(n)" для всех n < k. попробуем понять, как найти ответ для  n = k. что делает f(n)? читаем текст программы: сначала выводит n, а потом (если n > 0) запускает f(n - 1) и f(n - 3). обозначим s(n) - сумму всех чисел после вызова f(n), тогда (при n > 0)  s(n) = n + s(n - 1) + s(n - 3) для неположительных n получаем, что s(n) = n (т.к. f(n) просто выводит n и завершает работу, не запуская никаких других f). остается только расписать, чему равно s( s(-2) = -2 s(-1) = -1 s(0) = 0 s(1) = 1 + s(0) + s(-2) = 1 + 0 - 2 = -1 s(2) = 2 + s(1) + s(-1) = 2 -  1 - 1 = 0 s(3) = 3 + s(2) + s(0) = 3 + 0 + 0 = 3 s(4) = 4 + s(3) + s(1) = 4 + 3 - 1 = 6 s(5) = 5 + s(4) + s(2) = 5 + 6 + 0 = 11 ответ. 11. при исследовании рекурсивных алгоритмов бывает полезно понять, сколько вызовов функций делает программа (например, если рисовать дерево вызовов, это будет показывать количество "стрелочек" на этом дереве). представим себе, что мы стали выполнять алгоритм  на бумаге, попробуем понять, сколько чисел придется выписывать. если #(n) - число вызовов процедуры f при наивном вычислении f(n). понятно, что #(n) = #(n - 1) + #(n - 3) (при n < = 0 #(n) = 1).  не задаваясь целью получить точную формулу для #(n), получим только оценку (на самом деле, весьма показательную). очевидно, что #(n - 1) > = #(n - 3), тогда #(n) > = 2 *  #(n - 3). так как #(0) = 1, то #(3) > = 2 * #(0) = 2, #(6) > = 2 * #(3) > = 2^2, #(9) > = 2 * #(6) > = 2^3, и вообще #(3n) > = 2^n отсюда можно предположить, что #(n) растет не медленнее, чем 2^(n/3) > = 1.25^n. если 1,25^n кажется медленно растущей функцией - это вовсе не так, для n = 100 (это  немного, наверно? ) получим число, большее миллиарда. так что если не запоминать промежуточные результаты, результат будет считаться долго. s(n) также растет быстро, но это уже другая проблема.

Алфавитный (иначе, лексикографический) порядок - такой, при котором слово 1 стоит раньше в словаре, чем слово 2, если первые m  ≥  0 букв у этих слов , а (m + 1)-ая буква первого слова  стоит в алфавите раньше, чем (m + 1)-ая буква второго слова. будем записывать "стоит раньше" привычным значком < , тогда, например, для обычного алфавита a <   б <   в <   г < < я. посмотрим на первые буквы мишиных слов: из уже написанного можно сделать вывод, что a < б < з. сравним первые три буквы  слов, начинающихся на б: поскольку 2  первые буквы одинаковы, а слова, у которых на третьем месте стоит р, стоят раньше, чем слово, у которого н, получаем, что р < н. продолжаем исследовать слова баранка и барабан. выписывая первые буквы вплоть до первой отличающейся, получаем отсюда н < б. осталось разобраться с двумя словами, начинающимися на з. так как они начинаются на  то н < а . итак, требуется решить систему неравенств: a < б < з р < н н < б н < а легко понять, что в данном случае  р < н < а < б < з .