Вопросы 6, 14, 16. Исполнители

Тема:  Поиск алгоритма минимальной длины для исполнителя. (4 мин)

Что нужно знать:

·    исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

·    чтобы определить все возможные результаты работы алгоритма, нужно обозначить входные данные как переменные и выполнить алгоритм

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

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

Вопрос 6

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя 

след  в  виде  линии.  Чертёжник  может  выполнять  команду 

Сместиться на (a, b)  (где a, b – целые числа), перемещающую Чертёжника 

из  точки c координатами (x, y) в  точку  с координатами (x + a, y + b). Если 

числа  a,  b  положительные,  значение  соответствующей  координаты 

увеличивается; если отрицательные – уменьшается. 

Например,  если  Чертёжник  находится  в  точке  с  координатами (9, 5),  то 

команда Сместиться на (1, –2) переместит Чертёжника в точку (10, 3). 

Запись  

Повтори k раз 

Команда1 Команда2 Команда3 

конец 

означает,  что  последовательность  команд  Команда1  Команда2  Команда3 

повторится k раз. 

Чертёжнику был дан для исполнения следующий алгоритм: 

Повтори 3 раз 

Сместиться на (–2, –3) Сместиться на (3, 2) Сместиться на (–4, 0)  

конец  

На  какую  одну  команду  можно  заменить  этот  алгоритм,  чтобы  Чертёжник 

оказался в той же точке, что и после выполнения алгоритма? 

 1) Сместиться на (–9, –3) 

  

2) Сместиться на (–3, 9) 

 3) Сместиться на (–3, –1) 

  

4) Сместиться на (9, 3) 

  

Ответ:

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

1)      можно повторить все движения Робота на бумажке и посмотреть, куда он уйдет; на схеме исходная точка обозначена красной точкой, а конечная – синей, синяя линия показывает путь Робота:

Из рисунка видно, что правильный ответ под номером 1.

Решение (способ 2, сложение векторов):

1). подсчитываем сумму первого повтора

х=(-2+(+3)+(-4)*3)=-3*3=-9

y=(-3+2+0)*3=-1*3=-3

Ответ:сместиться(-9,-3)

Нужно выбрать тот способ решения, которым вы более владеете,и который более экономичен по времени.

 Задания для тренировки

Вопрос 14 (время решения 10 мин)

Что нужно знать:

·    каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом

·    исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

У исполнителя Делитель две команды, которым присвоены номера:
1. раздели на 2
2. вычти 1
Первая  из  них  уменьшает  число  на  экране  в 2  раза,  вторая  уменьшает  его
на 1.
Исполнитель работает только с натуральными числами.
Составьте  алгоритм  получения из числа 65 числа 4,  содержащий  не  более
5 команд. В ответе запишите только номера команд.

(Например, 12112 – это алгоритм:
раздели на 2
вычти 1
раздели на 2
раздели на 2
вычти 1,
который преобразует число 42 в число 4).

Если таких алгоритмов более одного, то запишите любой из них.

 Ответ: _____

Решение (вариант 1, «прямой ход»):

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

2)      начнем решать задачу, «отталкиваясь» от начального числа

3)      на первом шаге с помощью имеющихся команд из числа 65 можно получить 65-1=64 делить нельзя;

4)      на втором шаге из 64 можно получить 32 и 63, а из 32 – 16 и 48, и т.д., получается такая схема (структура «дерево»), цифры около стрелок показывает номер выполненной команды:

Ответ:11112

Возможные ловушки и проблемы: ·    большую схему неудобно рисовать, в ней легко запутаться ·    не всегда можно сразу угадать нужную ветку «дерева», то есть, ту, которая быстрее всего приведет к успеху

Решение (вариант 2, «обратный ход»):

1)      нам нужно увеличить число (с 4 до 65), для этого в большинстве случаев умножение эффективнее сложения, поэтому нужно постараться максимально использовать умножение, а сложение – только в крайних случаях

2)      попробуем решить задачу «обратным ходом», начав с числа 65;

8)      таким образом, правильный ответ записывается снизу вверх – 11112, эта программа состоит из 5 команд.

Ответ:11112

 Задания для тренировки

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

1. вычти 2

2. умножь на три

Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, 21211 – это программа:

умножь на три

вычти 2

умножь на три

вычти 2

вычти 2,

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

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

1. прибавь 2

2. умножь на 3

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

умножь на 3

прибавь 2

умножь на 3

прибавь 2

прибавь 2,

которая преобразует число 1 в 19).

3)      У исполнителя УТРОИТЕЛЬ две команды, которым присвоены номера:

1. вычти 1

2. умножь на 3

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

Запишите порядок команд в программе получения из числа 3 числа 16, содержащей не более 5 команд, указывая лишь номера команд.

(Например, программа 21211 это программа

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1

которая преобразует число 1 в 4.) 

1)      Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:

Вперед N (Кузнечик прыгает вперед на N единиц);

Назад M (Кузнечик прыгает назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд “Назад 2” на 12 больше, чем команд “Вперед 3”. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?

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

1.     Умножь на 2

2.     Вычти 2

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

команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не

более 5 команд, которая из числа 7 получает число 44. Укажите лишь номера команд.

Например, программа 11221 – это программа:

Умножь на 2;  

Умножь на 2;

Вычти 2;

Вычти 2;

Умножь на 2,

которая преобразует число 5 в число 32.

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

1. умножь на 3

2. вычти 2

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

команду номер 2, вычитает из числа на экране 2. Напишите программу, содержащую не

более 5 команд, которая из числа 1 получает число 23. Укажите лишь номера команд.

Например, программа 11221 – это программа:

умножь на 3

умножь на 3

вычти 2

вычти 2

умножь на 3,

которая преобразует число 1 в число 15.

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

1.     Вычти 3

2.     Умножь на 2

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

команду номер 2, умножает число на экране на 2. Напишите программу, содержащую не

более 5 команд, которая из числа 5 получает число 25. Укажите лишь номера команд.

Например, программа 22221 – это программа:

Умножь на 2

Умножь на 2

Умножь на 2

Умножь на 2

Вычти 3,

которая преобразует число 1 в число 13.

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

1. Умножь на 2

2. Вычти 1

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

команду номер 2, вычитает из числа на экране 1. Напишите программу, содержащую не

более 4 команд, которая из числа 7 получает число 52. Укажите лишь номера команд.

Например, программа 12121 - это программа:

Умножь на 2

Вычти 1

Умножь на 2

Вычти 1

Умножь на 2

которая преобразует число 5 в число 34.

6)      Исполнитель Чертежник имеет перо, которое можно поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след в виде прямой линии. У исполнителя существуют следующие команды:

Сместиться на вектор (а, Ь) – исполнитель  перемещается в точку, в которую можно попасть из данной, пройдя а единиц по горизонтали и b – по  вертикали.

Запись: Повторить 5[ Команда 1 Команда 2] означает, что последовательность команд в квадратных скобках повторяется 5 раз.

Чертежник находится в начале координат. Чертежнику дан для исполнения следующий алгоритм:

Сместиться на вектор (5,2)

Сместиться на вектор (-3, 3)

Повторить 3[Сместиться на вектор (1,0)]

Сместиться на вектор (3, 1)

На каком расстоянии от начала координат будет находиться исполнитель Чертежник в результате выполнения данного алгоритма?

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

Умножь на 2

Прибавь 1

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

команду номер 2, прибавляет к числу на экране 1. Напишите программу, содержащую не

более 5 команд, которая из числа 6 получает число 33. Укажите лишь номера команд.

Например, программа 12122 -это программа:

Умножь на 2

Прибавь 1

Умножь на 2

Прибавь 1

Прибавь 1

которая преобразует число 5 в число 24.

http://kpolyakov.narod.ru

Вопрос 16 (время решения 5 мин)

Что нужно знать:

·    каких-либо особых знаний из курса информатики не требуется, задача решаема на уровне 6-7 класса простым перебором вариантов, просто его нужно организовать оптимальным образом

·    исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды

Не­ко­то­рый ал­го­ритм из одной це­поч­ки сим­во­лов по­лу­ча­ет новую це­поч­ку Автомат  получает  на  вход  трёхзначное  десятичное  число. По  полученному числу строится новое десятичное число по следующим правилам. 

1. Вычисляются  два  числа –  сумма  старшего  и  среднего  разрядов,  а  также сумма среднего и младшего  разрядов заданного числа.  

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

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

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

1616  169  163  1916 1619 316  916 116 

В ответе запишите только количество чисел.

Решение:

1)     Анализируем предложенные числа с целью выявления не отвечающих условию задачи: все 4-х значные числа 1616 не отвечает 2 условию, 1916 и 1619 из-за числа 19=10+9, одно слагаемое меньше 10

2)      исключаем числа 316, 916 не соответствуют пункту 2

3)    число 163 исключается, т.к. число 16 может быть получено: 8+8, 7+9, 9+7, а число 3 не получается,
Таким образом остаются числа 169, 116.
Ответ: 2 

Вопрос 13. Системы счисления

Тема:  Системы счисления и двоичное представление информации в памяти компьютера.

Что нужно знать для решения этого задания?

Что такое  система счисления?

Это способ записи числа с помощью знаков (символов, которые мы называем цифрами)
Какими цифрами, знаками мы  пользуемся? 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Эти цифры мы называем арабскими. Но не всегда человечество использовало для записи числа эти знаки. Разные народы использовали разные знаки:
древние римляне использовали римские цифры I, II. III, IV, V, VI, VII, VIII, IX, X, Наши предки древние славяне использовали кириллицу, над буквой ставился значок "титло", который обозначал, что это не буква, а число.

В XVII немецкий ученый Го́тфрид Ви́льгельм Ле́йбниц окончательно разработал систему счисления, в которой все числа можно записать с помощью двух знаков 0 и 1, она называется двоичная система счисления. Лейбниц писал: 

«Вычисление с помощью двоек... является для науки основным и порождает новые открытия... При сведении чисел к простейшим началам, каковы 0 и 1, везде появляется чудесный порядок». Как перевести обычное число (десятичное) в двоичное состояние? Как выполнять задание? ·    перевод чисел между десятичной, двоичной, восьмеричной и шестнадцатеричной системами счисления Полезно помнить, что в двоичной системе: ·    четные числа оканчиваются на 0, нечетные – на 1; ·    числа, которые делятся на 4, оканчиваются на 00, и т. д.; числа, которые делятся на 2k, оканчиваются на k нулей ·    если число N принадлежит интервалу 2k-1 £ N < 2k, в его двоичной записи будет всего k цифр, например, для числа 125:                                26 = 64 £ 125 < 128 = 27,    125 = 11111012  (7 цифр) ·    числа вида 2k записываются в двоичной системе как единица и k нулей, например:           16 = 24 = 100002 ·    числа вида 2k-1 записываются в двоичной системе k единиц, например:           15 = 24-1 = 11112 ·    если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например:      15 = 11112,          30 = 111102,         60 = 1111002,   120 = 11110002 ·           желательно выучить наизусть таблицу двоичного представления чисел 0-7 в виде триад (групп из 3-х битов): X10, X8 X­2 X10, X8 X­2 0 000 4 100 1 001 5 101 2 010 6 110 3 011 7 111 и таблицу двоичного представления чисел 0-15 (в шестнадцатеричной системе – 0-F16) в виде тетрад (групп из 4-х битов): X10 X­2 X10 X­16 X­2 0 0000 8 8 1000 1 0001 9 9 1001 2 0010 10 A 1010 3 0011 11 B 1011 4 0100 12 C 1100 5 0101 13 D 1101 6 0110 14 E 1110 7 0111 15 F 1111 Пример задания: Вопрос 13 (Демо_2016)  Переведите число 126 из десятичной системы счисления в двоичную систему счисления. В ответе укажите двоичное число, основание системы счисления указывать не нужно. Решение. (вариант первый прямой перевод) 1) переводим число 126 в двоичную систему счисления: 126:2=63 (0) 63:2 = 31 (1) 31:2 = 15 (1) 15 :2 =  7 (1)  7   :2  = 3 (1)  3 :  2 = 1  (1) 1  : 2 = 0  (1)  Двоичное число представлено остатками 0 или 1, записываем снизу вверх 1111110 Ответ: 1111110 Решение (вариант 2, разложение на сумму степеней двойки): 1) раскладываем число 126, на числа, которые легко перевести в степени двоек 126=64+32+16+8+4+2=26+25+24+22+21 2) нужно знать таблицу степеней двойки 26=1000000 25=100000 24=10000 23=1000 22=100 21=10 Складываем двоичные числа: 1000000+100000+10000+1000+100+10=1111110 Ответ: 1111110 Какой способ решения выбрать? Тот, который вы лучше знаете. Ещё пример задания:  Сколько единиц в двоичной записи числа 1025? 1) 1            2)  2       3)  10  4) 11 Решение (вариант 1, прямой перевод): 1)      переводим число 1025 в двоичную систему: 1025 = 10000000001­2 2)      считаем единицы, их две 3)      Ответ: 2 Возможные проблемы: легко запутаться при переводе больших чисел. Решение (вариант 2, разложение на сумму степеней двойки): 1)      тут очень полезно знать наизусть таблицу степеней двойки, где 1024 = 210 и 1 = 20 2)      таким образом, 1025=  1024 + 1 = 210 + 20 3)      вспоминая, как переводится число из двоичной системы  в десятичную (значение каждой цифры умножается на 2 в степени, равной её разряду), понимаем, что в двоичной записи числа ровно столько единиц, сколько в приведенной сумме различных степеней двойки, то есть, 2 4)      Ответ: 2 Возможные проблемы: нужно помнить таблицу степеней двойки. Когда удобно использовать: ·    когда число чуть больше какой-то степени двойки Материал взят: http://kpolyakov.spb.ru/school/ege.htm