Вверх             вниз      влево    вправо.

Лабораторная работа №2. Выполнение алгоритмов для различных исполнителей

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

· правила выполнения линейных, разветвляющихся и циклических алгоритмов

· основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)

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

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

· запись нц для i от 1 до nобозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1

Примеры заданий:

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a,b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3)переместит Чертёжника в точку (6, −1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа):

НАЧАЛО

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

ПОВТОРИ n РАЗ

сместиться на (a, b)

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

КОНЕЦ ПОВТОРИ

Сместиться на (–24, -12)

КОНЕЦ

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

Решение:

1) запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:

2) поскольку Чертёжник должен вернуться в исходную точку, эти величины должны быть равны нулю; следовательно, нужно найти набольшее натуральное n, при котором система уравнений

разрешима в целых числах относительно a и b

3) несложно заметить, что для этого число n должно быть одновременно делителем чисел 14 и 25

4) наибольший общий делитель чисел 14 и 25 равен 1

5) ответ – 1.

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a,b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a; y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3)переместит Чертёжника в точку (6, −1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (буквами n, a, b обозначены неизвестные числа, при этом n > 1):

НАЧАЛО

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

ПОВТОРИ n РАЗ

сместиться на (a, b)

сместиться на (27, 12)

КОНЕЦ ПОВТОРИ

Сместиться на (–22, -7)

КОНЕЦ

Укажите наименьшее возможное значение числа n (n > 1), для которого найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку.

Решение:

1) запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:

2) поскольку Чертёжник должен вернуться в исходную точку, эти величины должны быть равны нулю; следовательно, нужно найти наименьшее натуральное n > 1, при котором система уравнений

разрешима в целых числах относительно a и b

3) несложно заметить, что для этого число n должно быть одновременно делителем чисел 10 и 25

4) наименьший общий делитель чисел 10 и 25 равен 5

5) ответ – 5.

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Если числа a, b положительные, значение соответствующей координаты увеличивается, если отрицательные – уменьшается. Например, если Чертёжник находится в точке с координатами (2, 4), то команда Сместиться на (1, –5) переместит Чертёжника в точку (3, –1).

Запись

Повтори k раз

Команда1

Команда2

Команда3

конец

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

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

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

Повтори N раз

Сместиться на (27, 17)

Сместиться на (a, b)

конец

Сместиться на (–27, –17)

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

1) 4     2) 5      3) 6      4) 7

Решение:

6) обратим внимание, что в этой задаче значения a и b неизвестны

7) вычислим итоговое смещение Чертёжника (общее изменение каждой координаты должно быть равно 0):

(3, -3)

N раз (27+a, 17+b)

(-27, 17)

общее изменение x-координаты:

3+N(27+a)-27 = 0

общее изменение y-координаты:

-3+N(17+b)-17 = 0

8) упрощаем оба уравнения:

N(27+a) = 24

N(17+b) = 20

9) таким образом, N – общий делитель чисел 24 и 20, это может быть 2 или 4; из вариантов ответа, приведённых в задаче, подходит только 4 (ответ 1)

10) Ответ: 1.

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх             вниз      влево    вправо.

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: