Top.Mail.Ru
Персональный сайт учителя информатики Звездиной Веры Алексеевны

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

или Давайте учиться дружно!

Смотреть презентацию
Смотреть презентацию
Смотреть презентацию
Скачать презентацию
Скачать презентацию
Читать
Смотреть и скачать

Практикум для подготовки к ЕГЭ-2021, задание 5, часть 1.   Анализ  простых алгоритмов  для конкретного исполнителя с фиксированным набором команд 

(базовый уровень, примерное время решения – 4 минуты). 

 

Исполнители бывают двух видов  - формальные и неформальные.

 

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

Неформальный исполнитель может выполнять команду каждый раз по-разному.

 

Например, набранный и сохраненный на компьютере текст всегда будет распечатан в одном и том же виде.

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

Как правило, человек выступает в роли неформального исполнителя.

 

Формальными исполнителями являются преимущественно технические устройства.

 

Человек в роли неформального исполнителя сам отвечает за свои действия.

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

 

Каждый исполнитель создается для решения задач определённого класса (круга).

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

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

 

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

 

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

 

Так следует поступать и нам при решении задач для формального исполнителя.

 

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

 

Тип 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, дает нам однозначно верное решение:

При помощи элементарных рассуждений и вычислений получаем (здесь символ V обозначает корень квадратный из числа):

         V 49 = 7 + 3 = 10 + 3 = 13 + 3 = 16, 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

© 2018–2022   Звездина Вера Алексеевна, v_zvezdina@mail.ru

SSL