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

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

(теория к урокам и ОГЭ - задание 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, дает нам однозначно верное решение:

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

  ___                                           ___

V49 = 7 + 3 = 10 + 3 = 13 + 3 = V16  = 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