Погода
Календарь
Январь 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123456
78910111213
14151617181920
21222324252627
28293031  
Страницы сайта

Анализ и построение алгоритмов для исполнителей.

Что может пригодиться для решения задания.

  • в задаче, для которой требуется определить все возможные результаты работы алгоритма какого-либо исполнителя, можно исходные данные обозначить переменными и вычислить алгоритм с этими переменными;
  • в задаче, для которой требуется найти оптимальную программу (или наиболее короткую), и которая с помощью заданного набора команд преобразует некоторое число в другое, лучше для решения строить дерево возможных вариантов; таким образом, вычисляя, какие результаты получатся после одного шага, после двух шагов и т.д. В результате найдется общее решение;
  • если среди заданных в задании команд исполнителя есть необратимая команда (например, исполнитель работает с целыми числами и есть команда возведения в квадрат – любое число можно возвести в квадрат, но не из любого числа можно извлечь квадратный корень, получив при этом целое), то дерево вариантов лучше строить с конца, т.е. в обратном порядке, двигаясь от конечного числа к начальному; тогда как получившаяся при этом в результате последовательность команд программы необходимо записать от начального числа к конечному.

ПРОВЕРКА ЧИСЛОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ НА СООТВЕТСТВИЕ АЛГОРИТМУ

  • для выполнения некоторых заданий необходимо повторить тему системы счисления;
  • максимальное значение суммы цифр десятичного числа — это 18, так как 9 + 9 = 18;
  • для проверки правильности переданного сообщения иногда вводится бит четности — дополнительный бит, которым дополняется двоичный код таким образом, чтобы в результате количество единиц стало четным: т.е. если в исходном сообщении количество единиц было четным, то добавляется 0, если нечетным — добавляется 1.
например:   310 = 112  после добавления бита четности: 110   
410 = 1002 после добавления бита четности: 1001
  • добавление к двоичной записи числа нуль справа увеличивает число в 2 раза:
 например:  1112 - это 710 добавим 0 справа: 11102 - это 1410

Задание 1. Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам. Вычисляются три числа – сумма старших разрядов заданных трехзначных чисел, сумма средних разрядов этих чисел, сумма младших разрядов.

Полученные три числа записываются друг за другом в порядке убывания (без разделителей).

Пример.  Исходные трехзначные числа:  835, 196. Поразрядные суммы: 9, 12, 11. Результат: 12119. Определите, какое из следующих чисел может быть результатом работы автомата.

1)  151303              2) 161410                   3) 191615                4) 121613

Решение:  Число строится из трех чисел, каждое из которых может быть однозначным (от 0 до 9) или двузначным (от 10 до 9 + 9 = 18).

Если в числе 6 цифр, значит, соединены три двузначных числа; в первом числе одно из них записывается как «03», что недопустимо (в этом случае правильное число было бы записано как 15133).

В третьем числе тоже 6 цифр: три двузначных числа, первое из которых равно 19, чего не может быть (никакие два однозначных числа не могут дать такую сумму). В четвертом числе тоже 6 цифр: три числа 12, 16 и 13 расположены НЕ в порядке убывания, поэтому этот вариант неверен.

Во втором варианте никаких противоречий с условием нет. Ответ: 2.

Задание 2. Предлагается некоторая операция над двумя произвольными трехзначными десятичными числами:

  1. Записывается результат сложения старших разрядов этих чисел.
  2.  К нему дописывается результат сложения средних разрядов по такому правилу: если он меньше первой суммы, то полученное число приписывается к первому слева, иначе – справа.
  3. Итоговое число получают приписыванием справа к числу, полученному после второго шага, сумму значений младших разрядов исходных чисел.

Какое из перечисленных чисел могло быть построено по этому правилу?

1) 141819    2) 171418          3) 141802       4) 171814

Решение:

  1. заметим, что сумма двух однозначных чисел – это число от 0 до 18 включительно
  2. все предложенные числа шестизначные, поэтому все суммы, из которых составлены числа, должны быть двузначными

1) 141819    2) 171418          3) 141802       4) 171814

  • поскольку числа 19 быть не может (его не получить суммой двух однозначных чисел), этот вариант не подходит
  • из условия (2) следует, что первые два двузначных числа должны быть расположены по возрастанию (неубыванию), поэтому вариант 2 не подходит
  • при записи числа 2 ноль впереди не добавляется (в условии про это ничего не сказано), поэтому третий вариант тоже не подходит
  • вариант 4 удовлетворяет всем условиям. Ответ: 4.

 

Задание 3. Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой нет на третьем месте. В середине – одна из бусин А, C, E, B, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу?

1) CBB         2) EAC              3)BCD            4) BCB

Решение (краткий вариант):

  1. проверяем первое условие: «В конце цепочки стоит одна из бусин A, B, C». Ему не удовлетворяет цепочка BCD, ее можно вычеркнуть:

  1) CBB       2) EAC              3)BCD            4) BCB

  • проверяем второе условие: «На первом месте – одна из бусин B, D, C, которой нет на третьем месте». Ему не удовлетворяют цепочки EAC (на первом месте – E) и BCB (на первом и третьем местах стоит буква B), поэтому остается только вариант CBB:

  1) CBB       2) EAC              4) BCB

  • проверяем третье условие: «В середине – одна из бусин А, C, E, B, не стоящая на первом месте». К счастью, оставшаяся цепочка CBB ему удовлетворяет.
  • таким образом, правильный ответ – 1.

Решение (подробный вариант):

1.правило содержит три условия, обозначим их так:

У1: третья бусина – A, B или C
У2-3: первая бусина – B, D или C, не совпадающая с третьей
У4-5: вторая бусина – A, B, C или E, не совпадающая с первой

2. фактически условия У2-3 и У4-5 сложные, их можно разбить на два, так что получится всего пять условий

У1: третья бусина – A, B или C
У2: первая бусина – B, D или C
У3: первая и третья бусины – разные
У4: вторая бусина – A, B, C или E
У5: первая и вторая бусины – разные

3. теперь для каждого из ответов проверим выполнение всех условий; в таблице красный крестик обозначает, что условие не выполняется для данного варианта; зеленым цветом выделена строка, где нет ни одного крестика, то есть все условия выполняются:

  • таким образом, правильный ответ – 1.

Задание 4. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. умножь на 3
Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 2 числа 26, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 – это программа:
умножь на 3
прибавь 1
умножь на 3
прибавь 1
прибавь 1,
которая преобразует число 1 в 14).

Решение:
Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 26 к числу 2, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.
1) Число 26 не делится на 3, значит, оно получено прибавлением единицы к числу 25: 26 = 25 + 1 (команда 1).
Повторим рассуждение для числа 25: 25 = 24 + 1 (команда 1).
2) Т. к. мы хотим получить не более 6 команд, то для получения числа 24 выгодно использовать умножение:
24 = 8 * 3 (команда 2).
Для числа 8 применяем первое рассуждение: 8 = 7 + 1(команда 1), повторяем его для 7: 7 = 6 + 1 (команда 1), а для числа 6 применим рассуждение 2): 6 = 2 * 3(команда 2).
Тогда окончательно получаем ответ: 211211
Ответ: 211211

Задание 5.  Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:
Вперед 5 – Кузнечик прыгает вперёд на 5 единиц,
Назад 3 – Кузнечик прыгает назад на 3 единицы.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 21?

Решение: Обозначим через x   количество команд «Вперед 5» в программе, а через y – количество команд «Назад 3», причём  x и  могут быть только неотрицательными целыми числами.
Для того чтобы КУЗНЕЧИК попал в точку 21 из точки 0, должно выполняться условие:   5x-3y=21

Представим его в виде:  5x=21+3y
Из последнего уравнения видно, что правая часть должна делиться на 5.
Из всех решений нас интересует такое, при котором – наименьшее возможное число.
Используя  метод подбора находим: y=3Ответ: 3


Задание 6. Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:
вверх
влево
влево
вниз
вниз
вправо
вправо
вниз
вправо
вверх
Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

Решение: Задачу можно решить, повторив все движения Робота на бумаге. Затем соединить начальную клетку и конечную клетку пути Робота, используя имеющиеся команды, и посчитать их количество.
Заметим, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают Робота, поэтому все такие пары можно выкинуть из программы, вдобавок, поскольку стенок нет, все равно где стоят парные команды в программе.
Вычеркнув все пары, видим, что остались только команды вниз, вправо. Их две.  Ответ: 2.

Задание 7. Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:
Сместиться на вектор (а, b) – исполнитель перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по вертикали.
Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.
Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:
Сместиться на вектор (5,2)
Сместиться на вектор (-3, 3)
Повторить 3[Сместиться на вектор (1,0)]
Сместиться на вектор (3, 1)
На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

Решение: Конечная точка будет обладать координатами по оси x и y. Эти координаты можно складывать независимо друг от друга.
Найдём значение x: 5 — 3 + 1 + 1 + 1 + 3 = 8.
Найдём значение y: 2 + 3 + 1 = 6.
Расстояние от начала координат находится по формуле:

поэтому

Ответ: 10.

Задание 8. Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N – Кузнечик прыгает вперед на N единиц
Назад M – Кузнечик прыгает назад на M единиц
Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад 4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?

Решение: Обозначим через   количество команд «Вперед 3» в программе, а через x — 4  – количество команд «Назад 4», причём x может быть только неотрицательным целым числом.
Всего кузнечик сделал x+x — 4=20 команд. Отсюда найдём x=12. Посчитаем, в какую точку попадёт Кузнечик после выполнения указанных команд: 3*12-4*(12-4)=36 — 32=4

В эту точку можно попасть из исходной, выполнив команду «Вперед 4».
Ответ: Вперед 4.

Задание 9.  На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.

Решение:

  1. фактически к числу дважды дописывается бит чётности, причем уже после шага «а» у нас всегда получится чётное число единиц, поэтому шаг «б» всегда добавит ноль
  2. если в конце двоичной записи числа стоит 0, значит, оно чётное
  3. минимальное чётное число, которое превышает 43, это 44, но число, полученное из 44 отбрасыванием последнего нуля в двоичной записи (то есть, делением на 2!), 22 = 101102, содержит нечётное число единиц, что не допускается по условию – после шага «а» число единиц двоичной записи должно быть чётным
  4. следующее чётное число, 46, при делении на 2 даёт число 23 = 101112, которое содержит чётное число единиц, поэтому оно могло быть получено после шага «а» алгоритма. Ответ: 46.

Задание 10.  Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.

2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).

Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.

Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.

Решение:

  1. единственный способ разбить запись 1311 на два числа – это 13 и 11 (числа 131 и 311 не могут образоваться в результате сложения значений двух десятичных цифр)
  2. сумма первой и второй цифр должна быть наименьшей (тогда и число будет меньше!), она равна 11; тогда сумма значений двух последних цифр равна 13
  3. для того чтобы всё число было минимально, числа, составленные из первых двух и последних двух цифр должны быть минимальными соответственно для сумм 11 и 13
  4. минимальное двузначное число, у которого сумма значений цифр равна 11, — это 29, с этих двух цифр начинается исходное четырёхзначное число
  5. сумма двух последних цифр – 13, минимальное двузначное число с такой суммой цифр – 49. Ответ: 2949.

Задание 11.  В некоторой информационной системе информация кодируется двоичными шестиразрядными словами. При передаче данных возможны их искажения, поэтому в конец каждого слова добавляется седьмой (контрольный) разряд таким образом, чтобы сумма разрядов нового слова, считая контрольный, была чётной. Например, к слову 110011 справа будет добавлен 0, а к слову 101100 – 1.

После приёма слова производится его обработка. При этом проверяется сумма его разрядов, включая контрольный. Если она нечётна, это означает, что при передаче этого слова произошёл сбой, и оно автоматически заменяется на зарезервированное слово 0000000. Если она чётна, это означает, что сбоя не было или сбоев было больше одного. В этом случае

принятое слово не изменяется.

Исходное сообщение

1100101 1001011 0011000

было принято в виде

1100111 1001110 0011000.

Как будет выглядеть принятое сообщение после обработки?

1) 1100111 1001011 0011000

2) 1100111 1001110 0000000

3) 0000000 0000000 0011000

4) 0000000 1001110 0011000

Решение:

  1. по условию в правильно принятом блоке число единиц должно быть чётное
  2. в принятом сообщении 1100111 1001110 0011000 нечётное число единиц (5) только в  первом блоке, поэтому он будет заменён на нули. Ответ: 4.

 

Задание 12.  Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

  1. Вычисляются два шестнадцатеричных числа – сумма старших разрядов полученных чисел и сумма младших разрядов этих чисел.
  2. Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.

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

1)  9F                      2) 911                    3) 42                      4)         7A

Решение:

  1. по условию обе цифры числа меньше или равны 6, поэтому при сложении двух таких чисел может получиться сумма от 0 до 12 = C­16
  2. сразу делаем вывод, что цифры F в записи числа быть не может, вариант 1 не подходит
  3. каждая из двух сумм находится в интервале 0..12, поэтому записывается одной шестнадцатеричной цифрой, так что результат работы автомата всегда состоит ровно из двух цифр
  4. из п. 2 следует, что вариант 2, состоящий из трех цифр, не подходит
  5. по условию цифры записаны в порядке возрастания, поэтому вариант 3 не подходит
  6. остается вариант 4, в котором все условия соблюдаются.
  7. Ответ: 4. 

Задание 13. У исполнителя Аккорд две команды, которым присвоены номера:

1. отними 1

2. умножь на x

где x – неизвестное положительное число. Выполняя первую из них, Аккорд отнимает от числа на экране 1, а выполняя вторую, умножает это число на x.

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

Известно, что программа 12121 переводит число 4 в число 23. Определите значение x.

Решение (составление уравнения):

  1. проблема здесь в том, что мы не знаем значения x, поэтому выполним программу, используя x как переменную:

Вход: 4

1: 4 – 1 = 3

2: 3·x = 3x

1: 3·x – 1

2: (3·x – 1) ·x = 3x2x

1: 3x2x – 1 = 23

  • остаётся решить уравнение   3x2– x — 1=23 или 3x2– x — 24=0
  • это уравнение имеет 2 корня, x1= 3 и x2= – 2,666
  • нас интересует только целое положительное решение, поэтому ответ – 3.

 Задание 14.  У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:

1. сдвинь влево

2. вычти 1

Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

Решение:

  1. важно, что числа однобайтовые – на число отводится 1 байт или 8 бит
  2. главная проблема в этой задаче – разобраться, что такое «сдвиг влево»; так называется операция, при которой все биты числа в ячейке (регистре) сдвигаются на 1 бит влево, в младший бит записывается нуль, а старший бит попадает в специальную ячейку – бит переноса:

             бит переноса

можно доказать, что в большинстве случаев результат этой операции – умножение числа на 2, однако есть исключение: если в старшем (7-ом) бите исходного числа x была 1, она будет «выдавлена» в бит переноса, то есть потеряна[1], поэтому мы получим остаток от деления числа 2x на 28=256

  • попутно заметим, что при сдвиге вправо[2] в старший бит записывается 0, а младший «уходит» в бит переноса; это равносильно делению на 2 и отбрасыванию остатка
  • таким образом, фактически команда сдвинь влево означает умножь на 2
  • поэтому последовательность команд 11221 выполняется следующим образом

         Ответ – 60.

Задание 15. Исполнитель Робот действует на клетчатой доске, между соседними клетками  которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается.  Робот успешно выполнил программу

         3233241

Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

Решение:

  1. фактически заданная программа движения Робота, которую он успешно выполнил, показывает нам свободный путь, на котором стенок нет
  2. поэтому для того, чтобы не разрушиться на обратном пути, Робот должен идти точно по тому же пути в обратном направлении
  3. нарисуем путь Робота, который выполнил программу 3233241:

Робот начал движение из клетки, отмеченной красной точкой, и закончил в клетке, где стоит синяя точка

  • чтобы вернуться в исходную клетку (с красной точкой) по пройденному пути, Роботу нужно сделать шаг влево (команда 4), затем шаг вверх (команда 1) и еще один шаг влево (команда 4).  Ответ – 414.

Задание 16. Исполнитель Робот ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. Робот выполнил следующую программу:

вправо
вверх
влево
влево
вниз
вниз
вправо
вправо
вправо
вниз
влево

Укажите наименьшее возможное число команд в программе, переводящей Робота из той же начальной клетки в ту же конечную.

Решение (способ 1, моделирование движения Робота):

  1. отметим, что в условии ничего не говорится о стенках, то есть, молчаливо предполагаем, что их нет
  2. можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота:
  • поскольку Робот не может ходить по диагонали, для перехода из начальной точки в конечную кратчайшим путем ему нужно выполнить, например, такую программу (см. штриховые линии на рисунке):
вниз вниз вправо
  • есть и другие варианты (попробуйте их найти!), но все они содержат 3 команды: одну команду вправо и две команды вниз. Ответ – 3.

Решение (способ 2, анализ программы):

  1. можно решить задачу без повторения движений Робота
  2. обратим внимание, что пары команд «вперед-назад» и «влево-вправо» дают нулевой эффект, то есть, не перемещают  Робота, поэтому все такие пары можно выкинуть из программы
  3. поскольку стенок нет, все равно где стоят парные команды в программе, вычеркиваем их:
  • смотрим, какие команды остались (они отмечены желтым маркером), их всего 3. Ответ – 3.

Задание 17. Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение  КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

 Вперед 4 – Кузнечик прыгает вперед на 4 единицы,

  Назад 3 – Кузнечик прыгает назад на 3 единицы.

  Какое наименьшее количество раз должна встретиться в программе команда     

  «Назад 3», чтобы Кузнечик оказался в точке 27?

  Решение (составление уравнения, подбор решения):

  1. обозначим через  количество команд «Вперед 4» в программе, а через  – количество команд «Назад 3»
  2. для того, чтобы КУЗНЕЧИК попал в точку 27 из точки 0, должно выполняться условие 4x — 3y = 27 — 0 = 27
  • это уравнение называется диофантовым; поскольку числа 4 и 3 – взаимно простые (их наибольший общий делитель равен 1), оно имеет бесконечно много решений
  • из всех решений нас интересует такое, при котором  – наименьшее возможное неотрицательное (!) число
  • представим уравнение в виде 4x = 27 + 3y

нужно подобрать минимальное неотрицательное , при котором правая часть делится на 4

  • дальше используем метод подбора (или перебора), начиная от 1; получаем
  • видим, что первое y , при котором  27 + 3y делится на 4, это  y = 3 (при этом x = 9). Ответ – 3.

         Задание 18. Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:

1. прибавь 1

2. умножь на 2

Выполняя команду номер 1, КАЛЬКУЛЯТОР прибавляет к числу на экране 1, а выполняя команду номер 2, умножает число на экране на 2. Укажите минимальное число команд, которое должен выполнить исполнитель, чтобы получить из числа 19 число 629.

Решение:

Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 629 к числу 19, тогда однозначно восстановим программу с минимальным числом команд. Полученные команды будут записываться справа налево.

1) Число 629 не делится на 2, значит, оно получено прибавлением единицы к числу 628: 629 = 628 + 1 (команда 1).

2) Т. к. мы хотим получить минимальное число команд, то для получения числа 628 нужно использовать умножение: 628 = 314 * 2 (команда 2).

Далее, если число чётное, применяем рассуждение 2), если нечётное — рассуждение 1), поэтому:

314 = 157 * 2 (команда 2);

157 = 156 + 1 (команда 1);

156 = 78 * 2 (команда 2);

78 = 39 * 2 (команда 2);

39 = 38 + 1 (команда 1);

38 = 19 * 2 (команда 2).

Считаем количество команд и получаем ответ: 8.

Задание 19. У ис­пол­ни­те­ля Калькулятор две команды:

1. при­бавь 1

2. при­бавь 4.

Первая из них уве­ли­чи­ва­ет число на экра­не на 1, вторая — на 4. Сколь­ко различных чисел можно по­лу­чить из числа 2 с по­мо­щью программы, ко­то­рая содержит не более 3 команд?

Решение:

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

Каждой про­грам­ме соответствует одно число, по­это­му посчитав ко­ли­че­ство возможных про­грамм (с точ­но­стью до перестановки), найдём ко­ли­че­ство различных чисел. При этом не будет по­вто­ря­ю­щих­ся чисел, по­сколь­ку

4 = 1 + 1 + 1 + 1,

т. е. ко­ман­да 2 рав­но­силь­на четырём ко­ман­дам 1, но у нас не более 3 команд.

Если в про­грам­ме n ко­манд 1, тогда остав­ши­е­ся будут ко­ман­да­ми 2. После одной ко­ман­ды n из­ме­ня­ет­ся от 0 до 1. Всего 2 программы, следовательно, 2 числа.

После двух ко­манд n из­ме­ня­ет­ся от 0 до 2. Всего 3 программы, следовательно, 3 числа.

Аналогичным об­ра­зом рассуждаем для трёх команд: по­лу­чим 4 числа.

Суммируем ко­ли­че­ство получившихся чисел и учтём, что ко­ли­че­ство команд не более 3, а значит, если про­грам­ма не со­дер­жит ни одной команды, то мы про­сто получим число 2.

Всего раз­лич­ных чисел: 2 + 3 + 4 + 1 = 10.

Ответ: 10.

Задание 20. У исполнителя Накопитель две команды:

1. прибавь 5,

1. прибавь 10.

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

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

Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд?

Решение:

Число команд 7, а от перестановки мест слагаемых сумма не меняется. Тогда пусть n — количество команд»1″, следовательно конечное число:

1 + 5 * n + (7 — n) * 10 = 1 + 70 + 5n — 10n = 71 — 5n, а n принимает значение от 0 до 7, т. е. 8 значений. Ответ: 8.

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

1. умножь на 2

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

Первая из них умножает число на экране на 2, вторая — утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 3 команд?

Решение:

*Следующее рассуждение удобно записывать в виде дерева.

С помощью одной команды из числа 2 можно получить 2 различных числа:

2 * 2 = 4

2 * 3 = 6.

С помощью двух команд можно получить по два числа из 4 и 6:

4 * 2 = 8

4 * 3 = 12

6 * 2 = 12

6 * 3 = 18

Видим, что два результата совпадают, поэтому получилось 3 числа, а не 4.

С помощью трёх команд получаются следующие числа.

12 * 2 = 24

12 * 3 = 36

8 * 2 = 16

8 * 3 = 24

18 * 2 = 36

18 * 3 = 54

Числа 36 и 24 встречаются дважды, поэтому всего получаем 4 различных числа.

Суммируем количество получившихся чисел и учтём, что количество команд не более 3, а значит, если программа не содержит ни одной команды, то мы просто получим число 2.

Всего различных чисел: 2 + 3 + 4 + 1 = 10. Ответ: 10.

Задание 22. У исполнителя Множитель 2 две команды:

1.умножь на 5

2.умножь на 3

Первая из них увеличивает число на экране в 5 раз, вторая – увеличивает его в 3 раза. Программа для исполнителя Множитель2 – это последовательность команд.

Сколько различных чисел можно получить из числа 81 с помощью программы, которая содержит ровно 4 команды?

Решение:

Всего 4 команды.

От перестановки мест множителей произведение не меняется.

Пусть n — количество команды «1», тогда конечное число:

81 * 5n * 34 — n = 81 * 34 * (5 / 3)n = 812 * (5 / 3)n,

где n меняется от 0 до 4, следовательно, разных значений будет 5. Ответ: 5.

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

1. умножь на 2

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

Первая из них умножает число на экране на 2, вторая — утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 3 команд?

Решение:

*Следующее рассуждение удобно записывать в виде дерева.

С помощью одной команды из числа 2 можно получить 2 различных числа:

2 * 2 = 4

2 * 3 = 6.

С помощью двух команд можно получить по два числа из 4 и 6:

4 * 2 = 8

4 * 3 = 12

6 * 2 = 12

6 * 3 = 18

Видим, что два результата совпадают, поэтому получилось 3 числа, а не 4.

С помощью трёх команд получаются следующие числа.

12 * 2 = 24

12 * 3 = 36

8 * 2 = 16

8 * 3 = 24

18 * 2 = 36

18 * 3 = 54

Числа 36 и 24 встречаются дважды, поэтому всего получаем 4 различных числа.

Суммируем количество получившихся чисел и учтём, что количество команд не более 3, а значит, если программа не содержит ни одной команды, то мы просто получим число 2.

 Всего различных чисел: 2 + 3 + 4 + 1 = 10. Ответ: 10.


Top