Понятная информатика

Анализ простых алгоритмов для конкретного исполнителя

с фиксированным набором команд (ОГЭ, задание 5)

Есть вопросы - пишите!

Исполнители бывают двух видов - формальные и неформальные. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду каждый раз по-разному.Например, набранный и сохраненный на компьютере текст всегда будет распечатан в одном и том же виде. Человек же, даже переписывая готовый текст, может написать его с различиями – например, аккуратно или безобразным почерком, с ошибками или без них. Как правило, человек выступает в роли неформального исполнителя.

  

Формальными исполнителями являются преимущественно технические устройства. Человек в роли неформального исполнителя сам отвечает за свои действия. За действия формального исполнителя отвечает управляющий им объект.

 

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

 

Алгоритм – это порядок решения задачи, описанный в ней самой. Линейный алгоритм описывает действия, выполняемые в строгой последовательности друг за другом. Решение задачи по готовому алгоритму требует от исполнителя только строгого следования заданным предписаниям

 

Исполнитель не вникает в смысл того, что он делает, и не рассуждает, почему он поступает так, а не иначе — он действует формально. Так следует поступать и нам при решении задач для формального исполнителя.

 

Рассмотрим задачи четырех различных типов.

 

 

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

 

В решении задач такого типа следует учитывать, что для сокращения количества команд в алгоритме нужно как можно чаще использовать команды умножения, деления, возведения в степень или извлечения корня, и только при невозможности их применения -  команды сложения и вычитания.

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

 

Пример 1. 1.

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

     1. раздели на 2

     2. прибавь 1

Первая из них уменьшает число на экране в 2 раза, вторая увеличивает его на 1. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 23 числа 4, содержащий не более 5 команд. В ответе запишите только номера команд (Например, 11222 — это алгоритм: раздели на 2, раздели на 2, прибавь 1, прибавь 1, прибавь 1, который преобразует число 36 в 12.) Если таких алгоритмов более одного, то запишите любой из них.

 

Решение.

Так как в задаче есть ограничение на количество используемых команд, то нужно чаще использовать команду деления на 2 для четных чисел и прибавлять 1 к нечетным в противном случае. Решение от исходного числа дает при этом однозначное решение.

При помощи элементарных рассуждений и вычислений получаем:

        23 + 1 = 24 / 2 = 12 / 2 = 6 / 2 = 3 + 1 = 4

Ответ: 12221

 

Пример 1.2.

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

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

     2. вычти 3

Первая из них возводит число на экране во вторую степень, вторая — вычитает из числа 3.

Составьте алгоритм получения из числа 4 числа 49, содержащий не более 5 команд. В ответе запишите только номера команд. (Например, 12221 — это алгоритм возведи в квадрат, вычти 3, вычти 3, вычти 3, возведи в квадрат, который преобразует число 4 в 49). Если таких алгоритмов более одного, то запишите любой из них.

 

Решение.

Так как в задаче есть ограничение на количество используемых команд, то нужно чаще использовать команду возведения в квадрат  и  вычитания   в противном случае. При этом решение с конца, от результата к исходному числу с применением команд извлечения корня  и прибавления 3, дает нам однозначно верное решение.

При помощи элементарных рассуждений и вычислений получаем:

          49= 7 + 3 = 10 + 3 = 13 + 3 = 16, 16  = 4

Тогда ответ пишем в обратную сторону заданными командами.

Ответ: 12221

 

 

Тип 2. Задан алгоритм для исполнителя с конкретным количеством команд, при этом одна из команд содержит неизвестное значение. Требуется найти значение неизвестного.

 

Пример 2.1.

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

     1. прибавь 2;

     2. умножь на b

     (b — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Альфа увеличивает число на экране на 2, а выполняя вторую, умножает это число на b. Программа для исполнителя Альфа — это последовательность номеров команд. Известно, что программа 12111 переводит число 7 в число 51. Определите значение b.

 

Решение.

Запишем заданную нам программу последовательностью математических действий, описанных в командах. При этом помним, что исполнитель выполняет их последовательно, невзирая на математические законы!

В результате выполнения команды 1 получаем

                   7+2 = 9.

Затем запишем дальнейшие действия в виде уравнения и решим его:

                9 * b +3*2 = 51

Тогда 9*b = 45, то есть b=5.

Ответ: 5

 

Пример 2.2.

У исполнителя Сигма две команды, которым присвоены номера:

     1. прибавь 1;

     2. раздели на b

     (b — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Сигма увеличивает число на экране на 1, а выполняя вторую, делит это число на b. Программа для исполнителя Сигма — это последовательность номеров команд. Известно, что программа 11211 переводит число 50 в число 22. Определите значение b.

 

Решение.

Запишем заданную нам программу последовательностью математических действий, описанных в командах. При этом помним, что исполнитель выполняет их последовательно, невзирая на математические законы!

В результате выполнения команды 1 получаем

                   50+2*2 = 54

Затем запишем дальнейшие действия в виде уравнения и решим его:

                54/b +2*2 = 22

Тогда 54/b=18, то есть  b = 3.

Ответ: 3

 

 

Тип 3. Задан алгоритм для исполнителя Чертёжник с фиксированным набором команд, определяющий перемещение исполнителя на плоскости.  Требуется ответить на поставленный в задаче вопрос.

 

Исполнитель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плоскости, остав­ляя след в виде линии. Чертёжник может вы­пол­нять команду Сместиться на (a, b) (где a, b — целые числа), пе­ре­ме­ща­ю­щую Чертёжника из точки с координатами (x, у) в точку с ко­ор­ди­на­та­ми (x + а, у + b). Если числа a, b положительные, зна­че­ние соответствующей ко­ор­ди­на­ты увеличивается; если отрицательные, уменьшается.

Например, если Чертёжник на­хо­дит­ся в точке с координатами (4, 2), то ко­ман­да Сместиться на (2, −3) пе­ре­ме­стит Чертёжника в точку (6, −1).

 

Запись

     Повтори k раз

     Команда1 Команда2 Ко­ман­даЗ

     Конец

означает, что по­сле­до­ва­тель­ность команд Команда1 Команда2 КомандаЗ по­вто­рит­ся k раз.

 

Пример 3. 1.

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

     Повтори 2 раз

         Команда1

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

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

     Конец

     Сместиться на (−6, −4)

После выполнения этого алгоритма Чертёжник вернулся в исходную точку. Какую команду надо поставить вместо команды Команда1?
     1) Сместиться на (−2, −1)
     2) Сместиться на (1, 1)
     3) Сместиться на (−4, −2)
     4) Сместиться на (2, 1)

 

Решение.

В задаче сказано, что Чертёжник вернулся в исходную точку, то есть нужно найти такое значение Команда 1, которое сведет значение всех ходов Чертёжника к нулю.  Для решения данной задачи подсчитаем пройденное расстояние  по осям абсцисс и ординат, чтобы определить, на сколько Чертёжник отошел от исходной точки. Для этого складываем координаты в заданных командах с учетом цикла:

     по оси абсцисс:    2 * (3 + 2) – 6 = 4

     по оси ординат:  2 * (2 + 1) – 4 = 2

С учетом того, что Команда1 также выполнялась 2 раза, то делим полученный результат  (4, 2) на 2 и  берем его с обратным знаком, тогда получаем значение

     Команда1 = (4, 2) * (-1) / 2 = (-2, -1)

Ответ: 1

 

Пример 3. 2.

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

     Повтори 7 paз

         Сместиться на (−1, 2)

         Сместиться на (−2, 2)

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

     Конец

Каковы координаты точки, с которой Чертёжник начинал движение, если в конце он оказался в точке с координатами (0, 0)?

     1) (7, 0)
     2) (−7, 0)
     3) (0, −7)
     4) (0, 7)

 

Решение.

В задаче сказано, что Чертёжник вернулся в начало координат,  значит, нужно подсчитать пройденное им расстояние и взять его с обратным знаком.  Для этого складываем координаты в заданных командах с учетом цикла:

     по оси абсцисс:  7 * ( –1 – 2 + 4 ) = 7

     по оси ординат:  7 * (2 + 2 – 4) = 0

 

Для обнуления результата  (7, 0)  берем его с обратным знаком и получаем (-7, 0).

Ответ: 2

 

Пример 3. 3.

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

     Повтори 7 paз

         Сместиться на (−1, 2)

         Сместиться на (−2, 2)

         Сместиться на (4, −5)

     Конец

Каковы координаты точки, с которой Чертёжник начинал движение, если в конце он оказался в точке с координатами (1, 1)?
    1) (6, 8)
    2) (−6, 8)
    3) (8, −6)
    4) (8, 6)

 

Решение.

Так как требуется найти координаты начальной точки, то нужно посчитать  все расстояние, пройденное Чертёжником, вычесть из него координаты конечной точки  и взять его с обратным знаком.  Для этого складываем координаты в заданных командах с учетом цикла:

     по оси абсцисс:  7 * ( –1 – 2 + 4 ) = 7 - 1= 6

     по оси ординат:  7 * (2 + 2 – 5) – 1 = -8

Тогда координаты начальной точки будут (6, -8) * (-1)  = (-6, 8)

Ответ: 2

 

Пример 3. 4.

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

     Повтори 5 paз

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

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

         Сместиться на (4, −5)

     Конец

Координаты точки, с которой Чертёжник начинал движение, (3, 1). Каковы координаты точки, в которой он оказался?
    1) (15, −6)
    2) (14, −5)
    3) (13, −4)
    4) (12, −3)

 

Решение.

Так как требуется найти координаты конечной точки, то нужно посчитать  все расстояние, пройденное Чертёжником,  и  прибавить к нему координаты конечной точки. С учетом цикла получаем:

     по оси абсцисс:  5 * ( 0 – 2 + 4 )  +  3 = 13

     по оси ординат:  5 * (1 + 3 – 5) + 1 = - 4

Тогда координаты конечной точки (13, -4).

Ответ: 3

 

Пример 3. 5.

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

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

     Повтори 4 раз

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

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

         Сместиться на (−1, 4)

     Конец

На какую команду можно заменить этот алгоритм?
     1) Сместиться на (8, 28)
     2) Сместиться на (7, 29)
     3) Сместиться на (−8, −28)
     4)Сместиться на (−7, −29)

 

Решение.

Для ответа на вопрос достаточно найти сумму координат по обеим осям. С учетом цикла получаем:

     по оси абсцисс:  -1 + 4 * ( 3 + 0 - 1 )  = 7

     по оси ординат:  1 + 4 * (1 + 2  + 4) = 29

Тогда требуемой командой будет:  Сместиться на (7, 29)

Ответ: 2

 

 

Тип 4. Задан алгоритм для исполнителя Черепашка с фиксированным набором команд,  задающий перемещение исполнителя на плоскости.  Требуется ответить на поставленный в задаче вопрос.

 

Исполнитель Че­ре­паш­ка пе­ре­ме­ща­ет­ся на экра­не компьютера, остав­ляя след в виде линии. В каж­дый кон­крет­ный мо­мент из­вест­но по­ло­же­ние ис­пол­ни­те­ля и на­прав­ле­ние его движения.

 

У ис­пол­ни­те­ля Че­ре­паш­ка су­ще­ству­ет две команды: 

       Вперёд n (где n — целое число), вы­зы­ва­ю­щая пе­ре­дви­же­ние Че­ре­паш­ки на n шагов в на­прав­ле­нии движения; 

     Направо m (где m — целое число), вы­зы­ва­ю­щая из­ме­не­ние на­прав­ле­ния дви­же­ния на m гра­ду­сов по ча­со­вой стрелке.

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

Поскольку в данных алгоритмах в цикле выполняются одинаковые команды, то в результате работы Черепашки на экране могут появиться:

• правильная геометрическая фигура, если количество шагов (циклов) Черепашки достаточно для рисования всех сторон фигуры с учетом заданных углов;
• незамкнутая ломаная линия – если шагов не достаточно.

      Если количество циклов превышает количество сторон, то Черепашка после   получения нужной фигуры пройдет оставшееся число  по его сторонам еще раз.

 

      При работе с Черепашкой не нужно рисовать результаты его ходов – можно ошибиться с градусами и получить неверный ответ.

        Команда Вперед n  вопросов при выполнении не вызывает.

      При выполнении команды Направо m нужно помнить, что Черепашка только поворачивается на нужный угол вправо, не смещаясь с заданной точки. При этом внутренний угол фигуры вычисляется по формуле 180 – m, а количество вершин многоугольника – по формуле 360/(180 – m).

 

Пример 4. 1.

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

           Повтори 9 [Вперёд 50 На­пра­во 60].

Какая фи­гу­ра по­явит­ся на экране?

 

     1) правильный шестиугольник

     2) правильный треугольник

     3) незамкнутая ло­ма­ная линия

     4) правильный девятиугольник

 

Решение.

Внутренний угол фигуры будет равен 180 – 60 = 120  градусов,  а количество вершин равно 360/(180 – 120) = 6. Количество циклов превышает количество углов, то в результате работы Черепашки получаем правильный шестиугольник.

Ответ: 1

 

Пример 4.2.

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

        Повтори 5 [Вперёд 80 На­пра­во 90].

Какая фи­гу­ра по­явит­ся на экране?

 

     1) незамкнутая ло­ма­ная линия

     2) правильный девятиугольник

     3) правильный пятиугольник

     4) правильный четырёхугольник

 

Решение.

Внутренний угол фигуры будет равен 180 – 90 = 90  градусов, а количество циклов больше 4, то в результате работы Черепашки получаем квадрат (правильный четырехугольник).

Ответ: 4

 

Пример 4.3.

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

        Повтори 6 [Вперёд 5 На­пра­во 30]

Какая фи­гу­ра по­явит­ся на экране?

      1)  не­за­мкну­тая ло­ма­ная линия

      2)  пра­виль­ный тре­уголь­ник

      3)  пра­виль­ный пятиугольник

      4)  пра­виль­ный шестиугольник

 

Решение.

Внутренний угол фигуры будет равен 180 – 30 = 150  градусов,  а количество вершин равно 360/(180 – 150) = 12.  Так как количество циклов меньше количества вершин, то в результате работы Черепашки получаем незамкнутую ломаную линию.

Ответ: 1

 

Пример 4.4.

При выполнении какого из перечисленных ниже алгоритмов на экране появился правильный треугольник?
    1) Повтори 3 [Вперёд 50 Направо 20 Направо 25]
    2) Повтори 3 [Вперёд 50 Направо 100 Направо 20]
    3) Повтори 6 [Вперёд 50 Направо 10 Направо 20]
    4) Повтори 6 [Вперёд 50 Направо 20 Направо 40]

Решение.

Внутренний угол равностороннего треугольника равен  60  градусов,  то ищем среди указанных вариантов тот, в котором сумма углов поворота равна 180-60 = 120 градусов.  Это будет вариант  Повтори 3 [Вперёд 50 Направо 100 Направо 20].

 Ответ: 2

 

 

С вопросами, замечаниями или предложениями по теме обращайтесь через форму обратной связи,  в группе сайта Вконтакте или  пишите на электронную почту v_zvezdina@mail.ru.