редица на Lichtenberg

Редицата на  Lichtenberg съдържа естествени числа, съответстващи на броя правилни хода при решаване на вид пъзел - китайски пръстени (Baguenaudier). Представена е в http://oeis.org/A051049 с рекурентна формула: a(n) = 2*(a(n-1)) + (n mod 2).

Съставете програма, чрез която се въвежда естествено число N от интервала [1..31] и се извеждат съответния брой последователни числа от редица на Lichtenberg. Програмата да използва две аналогични функции - рекурсия и итерация. Възможна рекурентна формула: a(n) = a(n-1) + 2*a(n-2) + 1. Формулата е подобна нa използваната при описание числа на Фибоначи.

Съществува и редица на Purkiss, която се свързва със същата игра. На графиката е представено примерно решение на пъзела с 5 пръстена.

Описание за примерно приложение на подобен алгоритъм може да намерите на адреси:  https://en.wikipedia.org/wiki/Baguenaudier;  http://mathworld.wolfram.com/Baguenaudier.html.

Разгледайте други основни типове примерни задачи, в чието решение се използват рекурсивни функции за работа с рекурентни редици. Прочетете допълнителен материал за ханойски кули, суми на Lichtenberg, фигури на Lichtenberg, редица на Purkiss.

Думата "baguenaudier" означава "time-waster" на френски език, а пъзелът се нарича китайски пръстени или игла на Дявола.

("Bague" означава също и "пръстен", но това изглежда е етимологично съвпадение. Интересното е, че дървото на пикочния мехур е също познато на френски като "baguenaudier".) Culin (1965) приписва пъзела на китайския генерал Hung Ming 181-234 г.), който го дал на жена си като подарък, за да я забавлява, докато бил далеч по войнски дела.

Решението на baguenaudier е тясно свързано с теорията за код на Грей, на база на която са построени абсолютните преобразуватели ъгъл-код.

1 - Извадете първия пръстен, за да получите 01111

2 - Премахнете третия пръстен, за да получите 01011

3 - Върнете първия пръстен, за да получите 11011

4 - Отстранете първите два пръстена, за да получите 00011

5 - Извадете петия пръстен, за да получите 00010

6 - Сложете първите два пръстена, за да получите 11010

7 - Отстранете отново първия пръстен, за да получите 01010

8 - Върнете третия пръстен, за да получите 01110

9 - Върнете отново първия пръстен, за да получите 11110

10 - Премахнете първите два пръстена, за да получите 00110

11 - Извадете четвъртия пръстен, за да получите 00100

12 - Върнете първите два пръстена, за да получите 11100

13 - Извадете първия пръстен, за да получите 01100

14 - Извадете третия пръстен, за да получите 01000

15 - Върнете първия пръстен, за да получите 11000

16 - Премахнете първите две, за да получите 00000