Циклические башни

На дорогах Ханоя было введено одностороннее круговое движение, поэтому теперь диск со стержня 1 можно перекладывать только на стержень 2, со стержня 2 — на 3, а со стержня 3 — на 1.

Решите головоломку с учётом этих ограничений. Вам не нужно находить минимальное решение, но количество совершённых перемещений не должно быть больше 200000 при условии, что количество дисков не превосходит 10.

Входные данные

Задано натуральное число n≤10 — размер пирамидки.

Выходные данные

Программа должна вывести перекладывания пирамидки из данного числа дисков со стержня 1 на стержень 3.

Январь - 2 кролика(+2) - 1 пара.

Февраль - 2 кролика (+0) - 1 пара.

Март - 4 кролика (+2 от первой пары) - 2 пары.

Апрель - 6 кроликов (+2 от первой пары) - 3 пары.

Май - 10 кроликов (+2 от первой и +2 от второй пары) - 5 пар.

Июнь - 16 кроликов (+2 от первой, +2 от второй, +2 от третьей пары) - 8 пар.

ответ: 8 пар.

По факту количество пар совпадает с числами Фибоначчи т.к. единая формула для решения данной задачи начиная с февраля первого года такова:

N(пар кроликов в этом месяце)=N(пар в предыдущем)+N(пар 2 месяца назад)

Январь - 2 кролика(+2) - 1 пара.

Февраль - 2 кролика (+0) - 1 пара.

Март - 4 кролика (+2 от первой пары) - 2 пары.

Апрель - 6 кроликов (+2 от первой пары) - 3 пары.

Май - 10 кроликов (+2 от первой и +2 от второй пары) - 5 пар.

Июнь - 16 кроликов (+2 от первой, +2 от второй, +2 от третьей пары) - 8 пар.

ответ: 8 пар.

По факту количество пар совпадает с числами Фибоначчи т.к. единая формула для решения данной задачи начиная с февраля первого года такова:

N(пар кроликов в этом месяце)=N(пар в предыдущем)+N(пар 2 месяца назад)