Оче­вид­но, из числа 1 нель­зя по­лу­чить чет­ное число. Пусть n  — не­чет­ное число, не пре­вос­хо­дя­щее 31. Обо­зна­чим R(n) ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее не­чет­ное число, крат­ное трем, не пре­вос­хо­дя­щее n. Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 31.

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

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

2.  Пусть n де­лит­ся на 3. Тогда R(n)  =  R(n : 3) + R(n – 2) (если n > 3).

При n  =  3 R(n)  =  2 (два спо­со­ба: при­бав­ле­ни­ем двой­ки или од­но­крат­ным умно­же­ни­ем на 3). По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех не­чет­ных чисел, крат­ных трем и не пре­вос­хо­дя­щих 31.

Имеем:

R(1)= 1;

R(3) = 2 = R(5)=R(7);

R(9) = R(3)+R(7) = 2+2 = 4 = R(11) = R(13);

R(15) = R(5)+R(13) = 2+4 = 6 = R(17) = R(19);

R(21) = R(7)+R(19) = 2+6 = 8 = R(23) = R(25);

R(27) = R(9)+R(25) = 4+8 =12 = R(29) = R(31).

Ответ: 12.

Дру­гой спо­соб ре­ше­ния.

Оче­вид­но, из числа 1 нель­зя по­лу­чить чет­ное число. Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 3, 5, …, 31 (то есть для каж­до­го из таких чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, обо­зна­чим R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, то есть даст число боль­ше 1. Зна­чит, R(1)  =  1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на три, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го не­чет­но­го числа с по­мо­щью ко­ман­ды при­бавь 2. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го не­чет­но­го числа: R(i)  =  R(i – 2). Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 2 и умножь на 3, тогда R(i)  =  R(i – 2) + R(i : 3). За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ве­ден­ным фор­му­лам слева на­пра­во:

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

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

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n)  =  R(n : 2) + R(n – 1)  =  R(n : 2) + R(n – 2) (если n > 2). При n  =  2 R(n)  =  2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и удво­е­ни­ем). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20.

Имеем:

R(3)  =  1;

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

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

R(8)  =  R(4) + R(6)  =  2 + 3  =  5  =  R(9);

R(10)  =  R(5) + R(8)  =  2 + 5  =  7  =  R(11);

R(12)  =  R(6) + R(10)  =  3 + 7  =  10  =  R(13);

R(14)  =  R(7) + R(12)  =  3 + 10  =  13  =  R(15);

R(16)  =  R(8) + R(14)  =  5 + 13  =  18  =  R(17);

R(18)  =  R(9) + R(16)  =  5 + 18  =  23  =  R(19);

R(20)  =  R(10) + R(18)  =  7 + 23  =  30  =  R(21);

R(22)  =  R(11) + R(20)  =  7 + 30  =  37.

Ответ: 37.

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

Для от­ве­та на за­да­чу нужно найти ко­ли­че­ство про­грамм, ко­то­рые из 2 по­лу­ча­ют 14, ко­ли­че­ство про­грамм, ко­то­рые из 14 по­лу­ча­ют 29, не про­хо­дя при этом через 25, и пе­ре­мно­жить най­ден­ные зна­че­ния. Сна­ча­ла найдём ко­ли­че­ство про­грамм, по­лу­ча­ю­щих 14.

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

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

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

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

Тогда R(n)  =  R(n : 2) + R(n – 1).

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

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

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

R(8)  =  R(4) + R(7)  =  2 + 3  =  5  =  R(9);

R(10)  =  R(5) + R(9)  =  2 + 5  =  7  =  R(11);

R(12)  =  R(6) + R(11)  =  3 + 7  =  10  =  R(13);

R(14)  =  R(7) + R(13)  =  3 + 10  =  13.

Про­грам­ма, по­лу­ча­ю­щая из числа 14 число 29, не про­хо­дя­щих через 25, одна: 21.

Таким об­ра­зом, всего про­грамм 13 · 1  =  13.

Ответ: 13.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n. За­ме­тим, что чет­ные числа мы никак по­лу­чить не можем.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить (25 - 1) / 2 = 12.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 2)= R(n / 3) + R(n - 6) (если n > 6).

При n = 3 R(n)) = 2 (два спо­со­ба: при­бав­ле­ни­ем двоек или од­но­крат­ным умно­же­ни­ем на 3).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 25: сна­ча­ла вы­чис­ля­ем R(1), затем R(3), R(9) и т. д.

Имеем:

R(1) = 1

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

R(9) = R(3) + R(7) = 2 + 2 = 4 = R(11) = R(13),

R(15) = R(5) + R(13) = 2 + 4 = 6 = R(17) = R(19),

R(21) = R(7) + R(19) = 2 + 6 = 8 = R(23) = R(25).

Дру­гая форма ре­ше­ния.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 3, 5,..., 25 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). За­ме­тим, что чётные числа мы никак по­лу­чить не можем. Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на три, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го с по­мо­щью ко­ман­ды при­бавь 2. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го воз­мож­но­го числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 2 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведённым фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 3, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го числа):

Ответ: 8.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 7 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 9, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 3.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить (72 - 6) / 3= 22.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 3)= R(n / 3) + R(n - 9) (если n > 9).

При n = 9 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем трой­ки).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 9 и не пре­вос­хо­дя­щих 72: сна­ча­ла вы­чис­ля­ем R(6), затем R(9), R(18) и т. д.

Имеем:

R(6)=1

R(9) = 1 = R(12) = R(15),

R(18) = R(6)+R(9)=1+1=2= R(21)=R(24),

R(36) = R(12) + R(27) =1 + 3 = 4 = R(39) = R(42),

R(45) = R(15) + R(36) =1 + 4 = 5= R(48) = R(51),

R(54) = R(18) + R(45) =1 + 4 = 5= R(48) = R(51),

R(63) = R(21) + R(54) =2 + 7 =9= R(66) = R(69),

R(72) = R(24) + R(63) =2 + 9 = 11.

Ответ: 11.

Дру­гая форма ре­ше­ния.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 6, 9, 12,..., 72 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). За­ме­тим, что мы можем по­лу­чить толь­ко числа крат­ные 3. Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 6 в число n, будем обо­зна­чать через R(n). Число 6 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 6. Зна­чит, R(6) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на три, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го с по­мо­щью ко­ман­ды при­бавь 3. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го воз­мож­но­го числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 3 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 9, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

align="center">

Ответ: 11.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 4 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 30.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 1)= R(n / 3) + R(n - 3) (если n > 3).

При n = 9 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем трой­ки).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 34: сна­ча­ла вы­чис­ля­ем R(4), затем R(6), R(9) и т. д.

Имеем:

R(4)=1

R(6) = R(9)=1 = R(5) = R(10)= R(11),

R(12) = R(4)+R(9)=1+1=2= R(13)=R(14),

R(15) = R(5) + R(12) =1 + 2 = 3= R(16) = R(17),

R(18) = R(6) + R(15) =1 + 3 = 4= R(19) = R(20),

R(21) = R(7) + R(18) =1 + 4 = 5= R(22) = R(23),

R(24) = R(8) + R(21) =1 + 5 =6= R(25) = R(26),

R(27) = R(9) + R(24) =1 + 6 =7= R(28) = R(29),

R(30) = R(9) + R(27) =1 + 7 =8= R(31) = R(32),

R(33) = R(10) + R(30) =1 + 8 =9= R(34).

Ответ: 9.

Дру­гая форма ре­ше­ния.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 4, 5, 6,..., 34 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на три, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го с по­мо­щью ко­ман­ды при­бавь 1. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го воз­мож­но­го числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 1 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 3, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 9.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 9, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 3.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить (93- 3) / 3= 31.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 3)= R(n / 3) + R(n - 9) (если n > 9).

При n = 9 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем трой­ки).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 9 и не пре­вос­хо­дя­щих 72: сна­ча­ла вы­чис­ля­ем R(3), затем R(9), R(18) и т. д.

Имеем:

R(3)=1=R(6)

R(9) = 2 = R(12) = R(15),

R(18) = R(6)+R(9)=1+2=3= R(21)=R(24),

R(27) = R(9) + R(18) =2 + 3 = 5 = R(30) = R(33),

R(36) = R(12) + R(27) =2 + 5 = 7= R(39) = R(42),

R(45) = R(15) + R(36) =2 + 7 = 9= R(48) = R(51),

R(54) = R(18) + R(45) =3 + 9 =12= R(57) = R(60),

R(63) = R(21) + R(54) =3 + 12 =15= R(66) = R(69),

R(72) = R(24) + R(63) =3 + 15 =18= R(75) = R(78),

R(81) = R(27) + R(72) =5 + 18 =23= R(84) = R(87),

R(90) = R(30) + R(81) =5 + 23 =28= R(93).

Ответ: 28.

Дру­гая форма ре­ше­ния.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 3, 6, 9,..., 93 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). За­ме­тим, что мы можем по­лу­чить толь­ко числа крат­ные 3. Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 6 в число n, будем обо­зна­чать через R(n). Число 3 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 3. Зна­чит, R(3) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на де­вять, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го с по­мо­щью ко­ман­ды при­бавь 3. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го воз­мож­но­го числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 3 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 9, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 28.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее не­чет­ное число, крат­ное трем, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 29.

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

1.  Если n не де­лит­ся на 3, то тогда R (n) = R(T(n)), так как су­ще­ству­ет

един­ствен­ный спо­соб по­лу­че­ния n из T(n) - при­бав­ле­ни­ем двоек.

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

Тогда R (n) = R(n/3)+R(n-2)= R(n/3)+R(n-6) (если n>6).

При n = 3 вы­пол­не­но: R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем двой­ки или

умно­же­ни­ем на 3).

По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех нечётных

чисел, крат­ных трём и не пре­вос­хо­дя­щих 59.

Имеем:

R(1)= 1

R(3) = 2 = R(5)=R(7)

R(9) = R(9/3) + R(9-6) = R(3) + R(3) =2+2 = 4 = R(11) = R(13)

R(15) = R(5)+R(9) =2+4 =6 = R(17)=R(19)

R(21) = R(7) + R(15) = 2+6 = 8 = R(23)=R(25)

R(27) = R(9) + R(21) =4+8 =12 = R(29) = R(31)

R(33) = R(11)+R(27) = 4+12 = 16 = R(35) = R(37)

R(39) = R(13)+R(33) = 4+16 = 20 = R(41) = R(43)

R(45) = R(15)+R(39) = 6+ 20 = 26 = R(47) = R(51)

R(51) = R(17)+R(45) = 6 + 26 = 32 = R(53) = R(55)

R (57) = R(19)+R(51) = 6 + 32 = 38 = R(59)

Ответ: 38.

Дру­гой спо­соб ре­ше­ния

Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Оче­вид­но, если n - чётное, то R(n) = 0. По­это­му ниже будем рас­смат­ри­вать толь­ко нечётные числа n.

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 3, 5,..., 59 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го нечётного числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на 3, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го нечётного числа с по­мо­щью ко­ман­ды при­бавь 2. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го нечётного числа:

Если число на 3 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 2 и умножь на 3, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 3, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 38.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим t(n) наи­боль­шее число, крат­ное че­ты­рем, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 32.

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

1.  Если n не де­лит­ся на 4, то тогда R (n) = R(T(n)), так как су­ще­ству­ет

един­ствен­ный спо­соб по­лу­че­ния n из T(n) - при­бав­ле­ни­ем еди­ниц.

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

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 вы­пол­не­но: R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем трех еди­ниц или

од­но­крат­ным умно­же­ни­ем на 4).

По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех нечётных

чисел, крат­ных че­ты­рем и не пре­вос­хо­дя­щих 32.

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29) = R(30) = R(31)

R(32) = R(8) + R(31) = 3 + 12 = 15

Ответ: 15.

Дру­гой спо­соб ре­ше­ния

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 2, 3,..., 32 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на 4, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го числа с по­мо­щью ко­ман­ды при­бавь 1. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го числа:

Если число на 4 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 1 и умножь на 4, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 4, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 15.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n. Обо­зна­чим T(n) наи­боль­шее чет­ное число, крат­ное че­ты­рем, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 28.

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

1.  Если n не де­лит­ся на 4, то тогда R (n) = R(T(n)), так как су­ще­ству­ет

един­ствен­ный спо­соб по­лу­че­ния n из T(n) - при­бав­ле­ни­ем еди­ниц.

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

Тогда R (n) = R(n/4)+R(n-1)= R(n/4)+R(n-4) (если n>4).

При n = 4 вы­пол­не­но: R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем трех еди­ниц или

од­но­крат­ным умно­же­ни­ем на 4).

По­это­му до­ста­точ­но по ин­дук­ции вы­чис­лить зна­че­ния R(n) для всех чётных

чисел, крат­ных че­ты­рем и не пре­вос­хо­дя­щих 29.

Имеем:

R(1)= R(2) = R(3) = 1

R(4) = 2 = R(5) = R(6) = R(7)

R(8) = R(2) + R(7) = 1 + 2 = 3 = R(9) = R(10) = R(11)

R(12) = R(3)+R(11) = 1 + 3 = 4 = R(13)= R(14) = R(15)

R(16) = R(4) + R(15) = 2 + 4 = 6 = R(17) = R(18) = R(19)

R(20) = R(5) + R(19) = 2 + 6 = 8 = R(21) = R(22) = R(23)

R(24) = R(6) + R(23) = 2 + 8 = 10 = R(25) = R(26) = R(27)

R(28) = R(7) + R(27) = 2 + 10 = 12 = R(29)

Ответ: 12.

Дру­гой спо­соб ре­ше­ния

Будем ре­шать по­став­лен­ную за­да­чу по­сле­до­ва­тель­но для чисел 1, 2, 3,..., 29 (то есть для каж­до­го из чисел опре­де­лим, сколь­ко про­грамм ис­пол­ни­те­ля су­ще­ству­ет для его по­лу­че­ния). Ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 1 в число n, будем обо­зна­чать через R(n). Число 1 у нас уже есть, зна­чит, его можно по­лу­чить с по­мо­щью «пу­стой» про­грам­мы. Любая не­пу­стая про­грам­ма уве­ли­чит ис­ход­ное число, т. е. даст число, боль­ше 1. Зна­чит, R(1) = 1. Для каж­до­го сле­ду­ю­ще­го числа рас­смот­рим, из ка­ко­го числа оно может быть по­лу­че­но за одну ко­ман­ду ис­пол­ни­те­ля. Если число не де­лит­ся на 4, то оно может быть по­лу­че­но толь­ко из преды­ду­ще­го числа с по­мо­щью ко­ман­ды при­бавь 1. Зна­чит, ко­ли­че­ство ис­ко­мых про­грамм для та­ко­го числа равно ко­ли­че­ству про­грамм для преды­ду­ще­го числа:

Если число на 4 де­лит­ся, то ва­ри­ан­тов по­след­ней ко­ман­ды два: при­бавь 1 и умножь на 4, тогда За­пол­ним со­от­вет­ству­ю­щую таб­ли­цу по при­ведёным фор­му­лам слева на­пра­во:

При этом ячей­ки, от­но­ся­щи­е­ся к чис­лам, ко­то­рые не де­лят­ся на 4, можно в ре­ше­нии и опу­стить (за ис­клю­че­ни­ем пер­во­го и по­след­не­го чисел):

Ответ: 12.

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

По­стро­им пол­ное де­ре­во ре­ше­ний и под­счи­та­ем ко­ли­че­ство ва­ри­ан­тов. Рас­смот­рим сна­ча­ла ветвь, где пер­вая ко­ман­да умно­же­ние:

1)  3 → 6 → 12 → 13 → ... → 23

2)  6 → 7 → 14 → ... → 23

3)  7 → 8 → 16 → ... → 23

4)  8 → 9 → 18 → ... → 23

5)  9 → 10 → 20 → ... → 23

6)  10 → 11 → 22 → ...23

7)  11 → 12 → ... → 23

Те­перь рас­смот­рим ветвь, где пер­вая ко­ман­да сло­же­ние, вто­рая умно­же­ние:

8)  3 → 4 → 8 → 16 → ... → 23

9)  8 → 9 → 18 → ... → 23

10) 9 → 10 → 20 → ... → 23

11) 10 → 11 → 22 → ...23

12) 11 → 12 → ... → 23

Ветвь, где пер­вая и вто­рая ко­ман­да сло­же­ние:

13) 3 → 4 → 5 → 10 → 20 → ... → 23

14) 10 → 11 → 22 → .. → 23

15) 11 → 12 → ... → 23

Пер­вые три и более ко­манд сло­же­ние:

16) 3 → 4 → 5 → 6 → 12 → ... → 23

Ещё 6 про­грамм будут иметь такой же конец, как про­грам­мы 2  — 7.

Всего 22 про­грам­мы.

Ответ: 22.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

Обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число, по­это­му ко­ли­че­ство ко­манд не может пре­вос­хо­дить 20 − 2= 18.

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

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

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

Тогда R(n) = R(n / 2) + R(n - 1)= R(n / 2) + R(n - 2) (если n > 2).

При n = 3 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20.

Имеем:

R(4)= 2 = R(5)

R(6) = 2 + 1= 3 = R(7),

R(8) = R(4)+R(6)= 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10= R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30.

Ответ: 30.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

Обе ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число, по­это­му ко­ли­че­ство ко­манд не может пре­вос­хо­дить 20 − 1 = 19.

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

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

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

Тогда R(n) = R(n / 2) + R(n - 1)= R(n / 2) + R(n - 2) (если n > 2).

При n = 2 R(n) = 2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и удво­е­ни­ем).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20.

Имеем:

R(2) = 2 = R(3)

R(4) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(4) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(6) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(8) = 4 + 10 = 14 = R(11),

R(12) = R(6) + R(10) = 6 + 14 = 20 = R(13),

R(14) = R(7) + R(12) = 6 + 20 = 26 = R(15),

R(16) = R(8) + R(14) = 10 + 26 = 36 = R(17),

R(18) = R(9) + R(16) = 10 + 36 = 46 = R(19),

R(20) = R(10) + R(18) = 14 + 46 = 60.

Ответ: 60.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко n, крат­ные 2.

Верно сле­ду­ю­щее со­от­но­ше­ние: R(n) = R(n / 2) + R(n − 2) (если n > 2).

При n = 4 R(n)) = 2 (один спо­соб: при­бав­ле­ни­ем двой­ки, вто­рой спо­соб: умно­же­ни­ем на два). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 42. R(n) для лю­бо­го не­чет­но­го n равно 0.

Имеем:

R(4)= 2,

R(6) = R(3) + R(4) = 0 + 2 = 2,

R(8) = R(4) + R(6) = 2 + 2 = 4,

R(10) = R(5) + R(8) = 0 + 4 = 4,

R(12) = R(6) + R(10) = 2 + 4 = 6,

R(14) = R(7) + R(12) = 0 + 6 = 6,

R(16) = R(8) + R(14) = 4 + 6 = 10,

R(18) = R(9) + R(16) = 0 + 10 = 10,

R(20) = R(10) + R(18) = 4 + 10 = 14.

R(22) = R(11) + R(20) = 0 + 14 = 14.

R(24) = R(12) + R(22) = 6 + 14 = 20.

R(26) = R(13) + R(24) = 0 + 20 = 20.

R(28) = R(14) + R(26) = 6 + 20 = 26.

R(30) = R(15) + R(28) = 0 + 26 = 26.

R(32) = R(16) + R(30) = 10 + 26 = 36.

R(34) = R(17) + R(32) = 0 + 36 = 36.

R(36) = R(18) + R(34) = 10 + 36 = 46.

R(38) = R(19) + R(36) = 0 + 46 = 46.

R(40) = R(20) + R(36) = 14 + 46 = 60.

R(42) = R(21) + R(40) = 0 + 60 = 60.

Ответ: 60.

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

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

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

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

2.  Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 2).

До­ста­точ­но вы­чис­лить все зна­че­ния R(n). За­ме­тим, что R от чет­но­го числа все­гда равно нулю. R от числа, ко­то­рое после вы­чи­та­ния 1 не крат­но 2, тоже равно нулю.

R(2) = 0,

R(3) = 2 (можно умно­жить еди­ни­цу на 3 или при­ба­вить 2 к еди­ни­це),

R(4) = R(2) = 0,

R(5) = R(3) = 2,

R(6) = R(4) + R(2) = 0,

R(7) = R(5) = 2,

R(8) = R(6) = 0,

R(9) = R(7) + R(3) = 2 + 2 = 4,

...

R(12) = R(10) + R(4) = 0 + 0 = 0,

...

R(15) = R(13) + R(5) = 4 + 2 = 6,

...

R(18) = R(16) + R(6) = 0 + 0 = 0,

...

R(21) = R(19) + R(7) = 6 + 2 = 8,

...

R(24) = R(22) + R(8) = 0 + 0 = 0,

...

R(27) = R(25) + R(9) = 8 + 4 = 12,

...

R(30) = R(28) + R(10) = 0 + 0 = 0,

...

R(33) = R(31) + R(11) = 12 + 4 = 16,

...

R(36) = R(34) + R(12) = 0 + 0 = 0,

...

R(39) = R(37) + R(13) = 16 + 4 = 20,

...

R(42) = R(40) + R(14) = 0 + 0 = 0,

...

R(45) = R(43) + R(15) = 20 + 6 = 26,

...

R(48) = R(46) + R(16) = 0 + 0 = 0,

...

R(51) = R(49) + R(17) = 26 + 6 = 32,

...

R(54) = R(52) + R(18) = 0 + 0 = 0,

R(55) = R(53) = 32.

Ответ: 32.

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

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

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

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

2.  Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 2).

До­ста­точ­но вы­чис­лить все зна­че­ния R(n). За­ме­тим, что R от чет­но­го числа все­гда равно нулю. R от числа, ко­то­рое после вы­чи­та­ния 1 не крат­но 2, тоже равно нулю.

R(2) = 0,

R(3) = 2 (можно умно­жить еди­ни­цу на 3 или при­ба­вить 2 к еди­ни­це),

R(4) = R(2) = 0,

R(5) = R(3) = 2,

R(6) = R(4) + R(2) = 0,

R(7) = R(5) = 2,

R(8) = R(6) = 0,

R(9) = R(7) + R(3) = 2 + 2 = 4,

...

R(12) = R(10) + R(4) = 0 + 0 = 0,

...

R(15) = R(13) + R(5) = 4 + 2 = 6,

...

R(18) = R(16) + R(6) = 0 + 0 = 0,

...

R(21) = R(19) + R(7) = 6 + 2 = 8,

...

R(24) = R(22) + R(8) = 0 + 0 = 0,

...

R(27) = R(25) + R(9) = 8 + 4 = 12,

...

R(30) = R(28) + R(10) = 0 + 0 = 0,

...

R(33) = R(31) + R(11) = 12 + 4 = 16,

...

R(36) = R(34) + R(12) = 0 + 0 = 0,

...

R(39) = R(37) + R(13) = 16 + 4 = 20,

...

R(42) = R(40) + R(14) = 0 + 0 = 0,

...

R(45) = R(43) + R(15) = 20 + 6 = 26,

...

R(48) = R(46) + R(16) = 0 + 0 = 0,

R(49) = R(47) = 26.

Ответ: 26.

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

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

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

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

2.  Если n де­лит­ся на 1,5 и ре­зуль­тат де­ле­ния  — чётное число, тогда R(n) = R(n / 1,5) + R(n − 1). До­ста­точ­но вы­чис­лить все зна­че­ния R(n). За­ме­тим, что R от чет­но­го числа все­гда равно нулю. R от числа, ко­то­рое после вы­чи­та­ния 1 не крат­но 2, тоже равно нулю.

R(2) = 1,

R(3) = 2 (можно умно­жить двой­ку на 1,5 или при­ба­вить 1 к еди­ни­це),

R(4) = R(3) = 2,

R(5) = R(4) = 2,

R(6) = R(4) + R(5) = 4,

...

R(9) = R(6) + R(8) = 4 + 4 = 8,

...

R(12) = R(8) + R(11) = 4 + 8 = 12,

...

R(15) = R(10) + R(14) = 8 + 12 = 20,

...

R(18) = R(12) + R(17) = 12 + 20 = 32,

...

R(20) = R(19) = 32.

Ответ: 32.

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

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

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

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

2.  Если n де­лит­ся на 1,5 и ре­зуль­тат де­ле­ния  — чётное число, тогда R(n) = R(n / 1,5) + R(n − 1). До­ста­точ­но вы­чис­лить все зна­че­ния R(n). За­ме­тим, что R от чет­но­го числа все­гда равно нулю. R от числа, ко­то­рое после вы­чи­та­ния 1 не крат­но 2, тоже равно нулю.

R(2) = 1,

R(3) = 2 (можно умно­жить двой­ку на 1,5 или при­ба­вить 1 к еди­ни­це),

R(4) = R(3) = 2,

R(5) = R(4) = 2,

R(6) = R(4) + R(5) = 4,

...

R(9) = R(6) + R(8) = 4 + 4 = 8,

...

R(12) = R(8) + R(11) = 4 + 8 = 12,

...

R(15) = R(10) + R(14) = 8 + 12 = 20,

...

R(18) = R(12) + R(17) = 12 + 20 = 32,

...

R(21) = R(14) + R(7) = 12 + 32 = 44.

R(22) = R(19) + R(7) = 44.

Ответ: 44.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 3) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 6). При n = 6 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ниц). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 37.

Имеем:

R(6)= 1 = R(7) = R(8),

R(9) = 2 = R(10) = R(11),

R(12) = R(4) + R(11) = 1 + 2 = 3 = R(13) = R(14),

R(15) = R(5) + R(14)= 1 + 3 = 4 = R(16) = R(17),

R(18) = R(6) + R(17) = 1 + 4 = 5 = R(19) = R(20),

R(21) = R(7) + R(20) = 1 + 5 = 6 = R(22) = R(23),

R(24) = R(8) + R(23) = 1 + 6 = 7 = R(25) = R(26),

R(27) = R(9) + R(26) = 2 + 7 = 9 = R(28) = R(29),

R(30) = R(10) + R(29) = 2 + 9 = 11 = R(31) = R(32),

R(33) = R(11) + R(32) = 2 + 11 = 13 = R(34) = R(35),

R(36) = R(12) + R(35) = 3 + 13 = 16 = R(37).

Ответ: 16.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 3) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 6). При n = 6 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ниц). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 36.

Имеем:

R(6)= 1 = R(7),

R(9) = 2 = R(10),

R(12) = R(4) + R(11) = 1 + 2 = 3 = R(13),

R(15) = R(5) + R(14)= 1 + 3 = 4 = R(16),

R(18) = R(6) + R(17) = 1 + 4 = 5 = R(19),

R(21) = R(7) + R(20) = 1 + 5 = 6 = R(22),

R(24) = R(8) + R(23) = 1 + 6 = 7 = R(25),

R(27) = R(9) + R(26) = 2 + 7 = 9 = R(28),

R(30) = R(10) + R(29) = 2 + 9 = 11 = R(31),

R(33) = R(11) + R(32) = 2 + 11 = 13 = R(34),

R(36) = R(12) + R(35) = 3 + 13 = 16 = R(37).

Ответ: 16.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 3) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 6). При n = 6 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ниц). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 33.

Имеем:

R(6)= 1 = R(7),

R(9) = 2 = R(10),

R(12) = R(4) + R(11) = 1 + 2 = 3 = R(13),

R(15) = R(5) + R(14)= 1 + 3 = 4 = R(16),

R(18) = R(6) + R(17) = 1 + 4 = 5 = R(19),

R(21) = R(7) + R(20) = 1 + 5 = 6 = R(22),

R(24) = R(8) + R(23) = 1 + 6 = 7 = R(25),

R(27) = R(9) + R(26) = 2 + 7 = 9 = R(28),

R(30) = R(10) + R(29) = 2 + 9 = 11 = R(31),

R(33) = R(11) + R(32) = 2 + 11 = 13.

Ответ: 13.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2 или 3.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 6). При n = 4 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 24.

Имеем:

R(4)= 1 = R(5),

R(6) = 2 = R(7),

R(8) = R(4)+R(6)= 1 + 2 = 3 = R(9),

R(10) = R(5) + R(8) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(10) = 2 + 4 = 6= R(13),

R(14) = R(7) + R(12) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(14) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(16) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(18) = 4 + 14 = 18 = R(21),

R(22) = R(11) + R(20) = 4 + 18 = 22 = R(23),

R(24) = R(12) + R(22) = 6 + 22 = 28.

Ответ: 28.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 2 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 21.

Имеем:

R(2)= 2 = R(3),

R(4)= 2 + 2 = 4 = R(5),

R(6) = 2 + 4 = 6 = R(7),

R(8) = R(4)+R(6) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(8) = 4 + 10 = 14 = R(11),

R(12) = R(6) + R(10) = 6 + 14 = 20 = R(13),

R(14) = R(7) + R(12) = 6 + 20 = 26 = R(15),

R(16) = R(8) + R(14) = 10 + 26 = 36 = R(17),

R(18) = R(9) + R(16) = 10 + 36 = 46 = R(19),

R(20) = R(10) + R(18) = 14 + 46 = 60 = R(21).

Ответ: 60.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 4). При n = 3 R(n)) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы), при n = 4 R(n)) = 2. По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 22.

Имеем:

R(3)= 1,

R(4)= 2 = R(5),

R(6) = R(3)+R(4)= 1 + 2 = 3 = R(7),

R(8) = R(4)+R(6)= 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(20) = 7 + 30 = 37 = R(23).

Ответ: 37.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 1) = R(n / 3) + R(n − 3) (если n > 3). При n = 3 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 34. Имеем:

R(6)= 2 = R(7),

R(9) = 1 + 2 = 3 = R(10),

R(12) = R(4) + R(11) = 1 + 3 = 4 = R(13),

R(15) = R(5) + R(14)= 1 + 4 = 5 = R(16),

R(18) = R(6) + R(17) = 2 + 5 = 7 = R(19),

R(21) = R(7) + R(20) = 2 + 7 = 9 = R(22),

R(24) = R(8) + R(23) = 2 + 9 = 11 = R(25),

R(27) = R(9) + R(26) = 3 + 11 = 14 = R(28),

R(30) = R(10) + R(29) = 3 + 14 = 17 = R(31),

R(33) = R(11) + R(32) = 3 + 17 = 20 = R(34).

Ответ: 20.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 1) = R(n / 3) + R(n − 3) (если n > 3). При n = 6 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 34. Имеем:

R(6)= 1 = R(7),

R(9) = 2 = R(10),

R(12) = R(4) + R(11) = 1 + 2 = 3 = R(13),

R(15) = R(5) + R(14)= 1 + 3 = 4 = R(16),

R(18) = R(6) + R(17) = 1 + 4 = 5 = R(19),

R(21) = R(7) + R(20) = 1 + 5 = 6 = R(22),

R(24) = R(8) + R(23) = 1 + 6 = 7 = R(25),

R(27) = R(9) + R(26) = 2 + 7 = 9 = R(28),

R(30) = R(10) + R(29) = 2 + 9 = 11 = R(31),

R(33) = R(11) + R(32) = 2 + 11 = 13 = R(34),

R(36) = R(12) + R(32) = 3 + 13 = 16 = R(38).

Ответ: 16.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 2). Таким об­ра­зом, до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 23. Имеем:

R(2)= 1 = R(3),

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7)= 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(15) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(17) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(19) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(21) = 7 + 30 = 37.

Ответ: 37.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 2). Таким об­ра­зом, до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 20. Имеем:

R(2)= 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 = R(13),

R(14) = R(7) + R(13) = 6 + 20 = 26 = R(15),

R(16) = R(8) + R(15) = 10 + 26 = 36 = R(17),

R(18) = R(9) + R(17) = 10 + 36 = 46 = R(19),

R(20) = R(10) + R(19) = 14 + 46 = 60.

Ответ: 60.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 4). Таким об­ра­зом, до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 22. Имеем:

R(4) = 1 = R(5),

R(6) = 2 = R(7),

R(8) = R(4) + R(7)= 1 + 2 = 3 = R(9),

R(10) = R(5) + R(9) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(11) = 2 + 4 = 6 = R(13),

R(14) = R(7) + R(13) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(15) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(17) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(19) = 4 + 14 = 18 = R(21);

R(22) = R(11) + R(21) = 4 + 18 = 22.

Ответ: 22.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 4). Таким об­ра­зом, до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 22. Имеем:

R(4) = 1 = R(5),

R(6) = 2 = R(7),

R(8) = R(4) + R(7)= 1 + 2 = 3 = R(9),

R(10) = R(5) + R(9) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(11) = 2 + 4 = 6 = R(13),

R(14) = R(7) + R(13) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(15) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(17) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(19) = 4 + 14 = 18 = R(21);

R(22) = R(11) + R(21) = 4 + 18 = 22 = R(23);

R(24) = R(12) + R(23) = 6 + 22 = 28 = R(25).

Ответ: 28.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 4). При n = 4: R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы), при n = 5: R(n) = 1. До­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 26.

Имеем:

R(4)= 1 = R(5),

R(6) = 2 = R(7),

R(8) = R(4) + R(6) = 1 + 2 = 3 = R(9),

R(10) = R(5) + R(8) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(10) = 2 + 4 = 6 = R(13),

R(14) = R(7) + R(12) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(14) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(16) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(18) = 4 + 14 = 18 = R(21),

R(22) = R(11) + R(20) = 4 + 18 = 22 = R(23),

R(24) = R(12) + R(22) = 6 + 22 = 28 = R(23),

R(26) = R(13) + R(24) = 6 + 28 = 34.

Ответ: 34.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 4 R(n)) = 2 (два спо­со­ба: при­бав­ле­ни­ем еди­ни­цы и умно­же­ни­ем на 2). До­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 22.

Имеем:

R(4) = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(20) = 7 + 30 = 37.

Ответ: 37.

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

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

Обо­зна­чим 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.

Итого ответ:

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 34.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 1)= R(n / 3) + R(n - 3) (если n > 3).

При n = 9 R(n)) = 2 (два спо­со­ба: утро­е­ни­ем трой­ки или при­бав­ле­ни­ем еди­ни­цы).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 37: сна­ча­ла вы­чис­ля­ем R(3), затем R(6), R(9) и т. д.

Имеем:

R(3)=1

R(6) = R(5) = R(4) = 1 = R(7) = R(8),

R(9) = R(3) + R(6) = 1 + 1 = 2 = R(10) = R(11),

R(12) = R(4)+ R(9)= 1 + 2 = 3 = R(13) = R(14),

R(15) = R(5) + R(12) = 1 + 3 = 4 = R(16) = R(17),

R(18) = R(6) + R(15) = 1 + 4 = 5 = R(19) = R(20),

R(21) = R(7) + R(18) = 1 + 5 = 6 = R(22) = R(23),

R(24) = R(8) + R(21) = 1 + 6 = 7 = R(25) = R(26),

R(27) = R(9) + R(24) = 2 + 7 = 9 = R(28) = R(29),

R(30) = R(10) + R(27) = 2 + 9 = 11 = R(31) = R(32),

R(33) = R(11) + R(30) = 2 + 11 = 13 = R(34) = R(35),

R(36) = R(12) + R(33) = 3 + 13 = 16 = R(37).

Ответ: 16.

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

Обо­зна­чим R(n)  — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 3 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 3, не пре­вос­хо­дя­щее n.

Обе ко­ман­ды ис­пол­ни­те­ля уве­ли­чи­ва­ют ис­ход­ное число, по­это­му общее ко­ли­че­ство ко­манд в про­грам­ме не может пре­вос­хо­дить 30.

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

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

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

Тогда R(n) = R(n / 3) + R(n - 1)= R(n / 3) + R(n - 3) (если n > 3).

При n = 6 R(n)) = 2 (два спо­со­ба: утро­е­ни­ем двой­ки или при­бав­ле­ни­ем еди­ниц).

По­это­му до­ста­точ­но по­сте­пен­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 32: сна­ча­ла вы­чис­ля­ем R(3), затем R(6), R(9) и т. д.

Имеем:

R(2) = R(3) = R(4) = R(5) = 1,

R(6) = R(5) + R(2) = 1 + 1 = 2 = R(7) = R(8),

R(9) = R(3) + R(6) = 1 + 2 = 3 = R(10) = R(11),

R(12) = R(4)+ R(9)= 1 + 3 = 4 = R(13) = R(14),

R(15) = R(5) + R(12) = 1 + 4 = 5 = R(16) = R(17),

R(18) = R(6) + R(15) = 2 + 5 = 7 = R(19) = R(20),

R(21) = R(7) + R(18) = 2 + 7 = 9 = R(22) = R(23),

R(24) = R(8) + R(21) = 2 + 9 = 11 = R(25) = R(26),

R(27) = R(9) + R(24) = 3 + 11 = 14 = R(28) = R(29),

R(30) = R(10) + R(27) = 3 + 14 = 17 = R(31) = R(32).

Ответ: 17.

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

Для от­ве­та на за­да­чу нужно найти ко­ли­че­ство про­грамм, ко­то­рые из 2 по­лу­ча­ют 16, ко­ли­че­ство про­грамм, ко­то­рые из 16 по­лу­ча­ют 33, не про­хо­дя через число 30, и пе­ре­мно­жить най­ден­ные зна­че­ния. Сна­ча­ла найдём ко­ли­че­ство про­грамм, по­лу­ча­ю­щих 16.

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

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

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

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

Тогда R(n) = R(n / 2) + R(n - 1).

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

R(2) = R(3) = 1,

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(15) = 5 + 13 = 18 = R(17).

То есть всего 18 про­грамм, по­лу­ча­ю­щих из числа 2 число 16.

Из числа 16, не про­хо­дя через 30, число 33 можно по­лу­чить толь­ко одним спо­со­бом: удво­е­ни­ем 16 и при­бав­ле­ни­ем еди­ни­цы.

Таким об­ра­зом, нуж­ных нам про­грамм: 18 · 1 = 18.

Ответ: 18.

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

Для от­ве­та на за­да­чу нужно найти ко­ли­че­ство про­грамм, ко­то­рые из 2 по­лу­ча­ют 15, ко­ли­че­ство про­грамм, ко­то­рые из 15 по­лу­ча­ют 31, не про­хо­дя через число 22, и пе­ре­мно­жить най­ден­ные зна­че­ния. Сна­ча­ла найдём ко­ли­че­ство про­грамм, по­лу­ча­ю­щих 15.

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

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

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

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

Тогда R(n) = R(n / 2) + R(n - 1).

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

R(2) = R(3) = 1,

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13 = R(15).

То есть всего 13 про­грамм, по­лу­ча­ю­щих из числа 2 число 15.

Из числа 15, не про­хо­дя через 22, число 31 можно по­лу­чить толь­ко одним спо­со­бом: удво­е­ни­ем 15 и при­бав­ле­ни­ем еди­ни­цы.

Таким об­ра­зом, нуж­ных нам про­грамм: 13 · 1 = 13.

Ответ: 13.

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

Для от­ве­та на за­да­чу нужно найти ко­ли­че­ство про­грамм, ко­то­рые из 3 по­лу­ча­ют 11, ко­ли­че­ство про­грамм, ко­то­рые из 11 по­лу­ча­ют 25, не про­хо­дя через число 20, и пе­ре­мно­жить най­ден­ные зна­че­ния.

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

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

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

2.  Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n - 1).

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

R(3) = 1

R(5) = R(4) = R(2) + R(3) = 0 + 1 = 1

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

R(9) = R(8) = R(4) + R(7) = 1 + 2 = 3

R(11) = R(10) = R(5) + R(9) = 1 + 3 = 4

За­ме­тим, что если число, ко­то­рое боль­ше 12 (то есть 13, 14, 15, ...), умно­жить на 2, ре­зуль­тат будет боль­ше 25. То есть если в ре­зуль­та­те ра­бо­ты про­грам­мы мы по­лу­чим число, ко­то­рое боль­ше 12, по­лу­чить из него 25 можно будет толь­ко с по­мо­щью опе­ра­ции при­бав­ле­ния. Но так как при­бав­лять мы можем лишь один, то в про­цес­се при­бав­ле­ний на тра­ек­то­рии попадётся число 20, что за­пре­ще­но. По­это­му из 11 по­лу­чить 25 можно толь­ко 2 спо­со­ба­ми: 11→22→23→24→25 и 11→12→24→25.

4 про­грам­мы для по­лу­че­ния из числа 3 число 11, 2 про­грам­мы для по­лу­че­ния из числа 11 число 25, всего про­грамм.

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