admin

Решение заданий С3.

Recommended Posts

№1. У исполнителя Утроитель две команды, которым присвоены номера :

1. прибавь 1,

2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая - утраивает его.

Программа для Утроителя - это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 29 ?

Ответ обоснуйте.

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

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

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

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

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

R(2)=1

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

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

R(9)=R(3)+R(6)=2+3=5=R(10)=R(11)

R(12)=R(4)+R(9)=2+5=7=R(13)=R(14)

R(15)=R(5)+R(12)=2+7=9=R(16)=R(17)

R(18)=R(6)+R(15)=3+9=12=15=R(22)=R(23)

R(24)=R(8)+R(21)=3+15=18=R(25)=R(26)

R(27)=R(9)+R(24)=5+18=23=R(28)=R(29)

Ответ: 23

№2. У исполнителя Калькулятор две команды, которым присвоены номера :

1. прибавь 2

2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая - утраивает его.

Программа для Утроителя - это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 31 ?

Ответ обоснуйте.

Общая формула для нечетных R(n)=R(n-2) для кратных 3 - R(n)= R(n/3)+R(n-2) Ответ: 6

№3.У исполнителя Квадратор две команды, которыми присвоены номера:

1. возведи в квадрат,

2. прибавь 1.

Первая из них возводит число на экране в квадрат, вторая - увеличивает его на 1.

Программа для Квадратора - это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 100 ?

Ответ обоснуйте.

Share this post


Link to post
Share on other sites
Гость
This topic is now closed to further replies.

  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу