Исполнители алгоритмов

ОГЭ по информатике

Алгоритм. Исполнитель алгоритма. Свойства алгоритма

Алгоритм - это последовательность действий, направленных на решение поставленной задачи. Синонимы: план решения, порядок работы, рецепт.

Пример: "как завязать галстук"

 

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

Исполнитель - тот, кто выполняет заданный ему алгоритм. Чаще всего, исполнитель это человек (неформальный исполнитель) или техническое устройство, например, компьютер (формальный исполнитель). 

Система команд исполнителя - элементарные команды исполнителя, которые он способен понять и выполнить. Пример СКИ исполнителя Робот: вправо, влево, вниз, вверх.

Недоступен флеш-плагин. Скачайте здесь.

Среда выполнения алгоритма - условия, в которых находится исполнитель. Например, для Робота это прямоугольное поле со стенками.

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

Недоступен флеш-плагин. Скачайте здесь.

Примеры решения задач

Пример 1.

Решение:

1. Вычислим перемещение исполнителя за одно выполнение тела цикла по оси ох:
     -2 + 3 + (-4) = -3

2. Так как цикл выполнялся три раза, общее перемещение по оси ох составляет 3 * (-3) = -9

3. Аналогично мы можем вычислить общее перемещение исполнителя по оси оу:
     3 * (-3 + 2 + 0) = 3 * (-1) = -3

Итак, алгоритм:

Повтори 3 раз
    Сместиться на (-2,-3) 
    Сместиться на (3,2) 
    Сместиться на (-4,0)
конец

можно заменить одной командой: Сместиться на (-9,-3)

Ответ: 1)

 

Пример 2.

Решение:

Это легкая задача. Один из вариантов решения может быть таким:
65 → 64 → 32 → 16 → 8 → 4

Ответ: 21111

 

Пример 3.

Решение:

Запишем в общем виде число: abc

Автомат на шаге 1 вычисляет a+b, b+c. На втором шаге автомат записывает эти суммы в порядке невозрастания.
Например, пусть дано число 197. Шаг первый: 1+9=10, 9+7=16. Шаг второй: записываются полученные числа 10 16 в порядке невозрастания : 1610

Еще пример: пусть на вход автомата поступило число 999. Шаг первый: 9+9=18, 9+9=18. Шаг второй: 1818

Как мы видим, максимальная сумма от сложения двух разрядов не превышает 18.

Итак, разберем приведённые выше числа: 1616  169  163  1916  1619  316  916  116.
1616 можно получить в результате работы автомата, например из чисел 888, 979, 797.
169 можно получить из таких чисел, как 881, 188, 972, 790.
163 никак получить нельзя, так как нельзя подобрать среднее число таким образом, чтобы оно входило в сумму 16 и в сумму 3 одновременно.
1916 получить нельзя, так как максимальная сумма двух десятичных цифр равна 18 (9+9).
1619 получить нельзя, так как сумму 19 невозможно получить из двух цифр и нарушен порядок записи - 16 и 19 записаны по возрастанию, а надо по убыванию.
316 нарушен порядок записи.
916 нарушен порядок записи. 
116 может получиться в результате работы автомата, например из чисел 560,651, 156, 742, 247

Ответ: 3 (указываем количество "правильных" чисел).

 

Пример 4.

Некоторый алгоритм из одной цепочки символов получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов; если она чётна, то удаляется правый символ цепочки, а если нечётна, то в начало цепочки добавляется буква Б. В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в русском алфавите (А <nobr style="line-height: 1.231;">–</nobr> на ББ <nobr style="line-height: 1.231;">–</nobr> на В и т.д., а Я <nobr style="line-height: 1.231;">–</nobr> на А).

Получившаяся таким образом цепочка является результатом работы описанного алгоритма.

Например, если исходной была цепочка АВС, то результатом работы алгоритма будет цепочка ВБГТ, а если исходной была цепочка КРОТ, то результатом работы алгоритма будет цепочка ЛСП.

Дана цепочка символов СТОП. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (т.е. применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

Русский алфавит: АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

Решение:

  1. Длина цепочки символов СТОП равна 4
  2. Длина 4 - число чётное, удаляем символ справа: СТО
  3. Заменяем каждую букву на следующую букву в алфавите: ТУП

Применим к результату ТУП  данный алгоритм ещё раз:

  1. Длина цепочки символов ТУП равна 3
  2. Длина 3 - число нечётное, добавляем в начало цепочки букву Б: БТУП
  3. Заменяем каждую букву на следующую букву в алфавите: ВУФР

Ответ: ВУФР

 

Пример 5.

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существует две команды:
Вперёд n (где n – целое число), вызывающая передвижение Черепашки на n шагов в направлении движения;
Направо m (где m – целое число), вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори k [Команда1 Команда2 Команда3] означает, что последовательность команд в скобках повторится k раз.

Черепашке был дан для исполнения следующий алгоритм:
Повтори 5 [Вперёд 100 Направо 120]

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

  1. правильный пятиугольник
  2. правильный треугольник
  3. правильный шестиугольник
  4. незамкнутая ломаная линия

Решение, 1 способ: 

Выполнив первый раз команды [Вперёд 100 Направо 120], мы получим линию длиной 100 и развернем Черепашку на 120 градусов  по часовой стрелке:

Выполнив второй раз эти же команды, мы в целом получим две линии:

Выполнив третий раз эти команды, получим три линии:

Четвертое выполнение повторяет первое, пятое выполнение повторяет второе (то есть рисуют линию поверх старых).

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

Решение, 1 способ: 

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

Существует формула для определения внутреннего угла любого правильного многоугольника:

внутренний угол = (N-2)*180 / N, где N - число вершин многоугольника

В нашем случае внутренний угол равен 60 градусов:

 

Подставим значение угла в выражение:
60 = (N - 2) * 180  / N

Проверим вариант ответа № 1 - правильный пятиугольник:
60 = (5-2) *180 /5
60 = 3*180 /5 
60 = 108   Неверно! 

Проверим вариант ответа № 2 - правильный треугольник:
60 = (3-2) *180 /3
60 = 60   Верно!

Ответ: 2

Пройти тест по этой теме

 

ОГЭ по информатике

blog comments powered by Disqus

Яндекс.Метрика Мой канал на youtube Усть-Куломская школа Усть-Куломский район Коноплев О.О.

© 2016 Рассыхаев А.А.