Нужно найти ко­ли­че­ство про­грамм, ко­то­рые ⁠ по­лу­ча­ют 10, ко­ли­че­ство про­грамм, ко­то­рые из 10 по­лу­ча­ют 21, ко­ли­че­ство про­грамм, ко­то­рые из 21 по­лу­ча­ют 30 и пе­ре­мно­жить най­ден­ные зна­че­ния. Сна­ча­ла найдём ко­ли­че­ство про­грамм, по­лу­ча­ю­щих 10 из 1.

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1.  Если n не де­лит­ся на 2, то тогда R(n)  =  R(n – 1), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из n – 1  — при­бав­ле­ние еди­ни­цы.

2.  Пусть n де­лит­ся на 2.

Если n > 1, то R(n)  =  R(n : 2) + R(n – 1).

Если n  =  1, то R(n)  =  1 (два спо­со­ба: при­бав­ле­ние еди­ни­цы и удво­е­ние).

Те­перь можно по­сте­пен­но вы­чис­лить все зна­че­ния:

R(2)  =  R(1) + R(1)  =  1 + 1  =  2  =  R(3);

R(4)  =  R(2) + R(3)  =  2 + 2  =  4  =  R(5);

R(6)  =  R(3) + R(5)  =  2 + 4  =  6  =  R(7);

R(8)  =  R(4) + R(7)  =  4 + 6  =  10  =  R(9);

R(10)  =  R(5) + R(9)  =  4 + 10  =  14.

Про­грамм, по­лу­ча­ю­щих из числа 10 число 21, до­ста­точ­но мало, можно их про­сто пе­ре­чис­лить: 21, 11111111111.

А про­грам­ма, по­лу­ча­ю­щая из числа 21 число 30, всего одна (один спо­соб: до­бав­ле­ние еди­ниц).

Таким об­ра­зом, на­хо­дим ответ:

Ответ: 28.

При­ведём дру­гое ре­ше­ние на языке Python.

Нужно найти ко­ли­че­ство про­грамм, ко­то­рые из 1 по­лу­ча­ют 12, ко­ли­че­ство про­грамм, ко­то­рые из 12 по­лу­ча­ют 25, ко­ли­че­ство про­грамм, ко­то­рые из 25 по­лу­ча­ют 40, и пе­ре­мно­жить най­ден­ные зна­че­ния. Сна­ча­ла найдём ко­ли­че­ство про­грамм, по­лу­ча­ю­щих 12 из 1.

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1.  Если n не де­лит­ся на 2, то тогда R(n)  =  R(n – 1), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из n − 1  — при­бав­ле­ние еди­ни­цы.

2.  Пусть n де­лит­ся на 2.

Если n > 1, то R(n)  =  R(n : 2) + R(n – 1).

Если n  =  1, то R(n)  =  1 (два спо­со­ба: при­бав­ле­ние еди­ни­цы и удво­е­ние).

Те­перь можно по­сте­пен­но вы­чис­лить все зна­че­ния:

R(2)  =  R(1) + R(1)  =  1 + 1  =  2  =  R(3);

R(4)  =  R(2) + R(3)  =  2 + 2  =  4  =  R(5);

R(6)  =  R(3) + R(5)  =  2 + 4  =  6  =  R(7);

R(8)  =  R(4) + R(7)  =  4 + 6  =  10  =  R(9);

R(10)  =  R(5) + R(9)  =  4 + 10  =  14  =  R(11);

R(12)  =  R(6) + R(11)  =  6 + 14  =  20.

Про­грамм, по­лу­ча­ю­щих из числа 12 число 25 до­ста­точ­но мало, можно их про­сто пе­ре­чис­лить: 21, 1111111111111.

А про­грам­ма, по­лу­ча­ю­щая из числа 25 число 40, всего одна (один спо­соб: до­бав­ле­ние еди­ниц).

Таким об­ра­зом, на­хо­дим ответ:

Ответ: 40.

При­ведём дру­гое ре­ше­ние на языке Python.