Наш любимый Стив попал в волшебные шахты. Пробыв там совсем немного, он обнаружил закономерность нахождения алмазных блоков: они были выстроены в пирамиду, причем ширина каждой следующей полосы пирамиды была равна сумме широт двух предыдущих. Например, первые 8 полос пирамиды имеют следующую ширину ему рассчитать, сколько блоков алмазов будет в полосе с номером N.
В данной задаче необходимо использовать рекурсию.
Формат входных данных
На вход ваша программа получает одно число — N (1 ≤ N ≤ 25)
Формат выходных данных
Выведите количество блоков в полосе с номером N.
Вычитание выполнено в шестеричной системе счисления.
Объяснение:
Мы видим в данном выражении цифры до 4. Из этого следует, что система счисления использует не менее 5 цифр. То есть, она как минимум - пятиричная. Будем подбирать по порядку системы счисления и вычислять их значения.
Пятиричная система счисления:
1. Переводим в десятичную систему счисления:
102 = 25 * 1 + 5 * 0 + 1 * 2 = 25 + 0 + 2 = 27
14 = 5 * 1 + 1 * 4 = 5 + 4 = 9
2. Вычисляем в десятичной системе счисления:
27 - 9 = 18
3. Переводим в пятиричную систему счисления:
18 = 33
Вывод: данная система счисления не подходит.
Шестеричная система счисления:
1. Переводим в десятичную систему счисления:
102 = 36 * 1 + 6 * 0 + 1 * 2 = 36 + 0 + 2 = 38
14 = 6 * 1 + 1 * 4 = 6 + 4 = 10
2. Вычисляем в десятичной системе счисления:
38 - 10 = 28
3. Переводим в шестеричную систему счисления:
28 = 44
Вывод: данная система счисления подходит.
УДАЧИ! ОБРАЩАЙТЕСЬ!