Задача 3. Исполнитель Вычислитель имеет систему команд: разделить на 3, уменьшить на 1, увеличить на 1

Исполнитель Вычислитель имеет систему команд: разделить на 3, уменьшить на 1, увеличить на 1. Его система вопросов: делится на 3?

Определить какое число будет получено из 100 в процессе выполнения следующих команд.

если делится на 3

то разделить на 3

увеличить на 1

иначе уменьшить на 1

Все

если делится на 3

то разделить на 3

уменьшить на 1

иначе увеличить на 1

Все

если делится на 3

то разделить на 3

увеличить на 1

иначе уменьшить на 1

Все

Решение.

В первом вопросе условие не выполняется, получим 99. Во второй раз - выполняется, значит, получим сначала 33, потом 32. В третий раз условие опять не выполняется, значит, получим 31.

R

R

-R

Задача 4.

На координатной плоскости имеется фигура, представляющая собой половину круга и половину квадрата. Задается число R, которое определяет ее размер в соответствии с рисунком. Требуется определить, принадлежит ли точка с координатами X, Y указанной фигуре.

Решение.

В первую очередь следует решить вопрос лежит ли точка в верхней или нижней полуплоскости. В верхней полуплоскости нас интересует расстояние от точки до начала координат, квадрат которого мы вычисляем по теореме Пифагора и сравниваем с квадратом радиуса. Если точка в нижней полуплоскости, то она принадлежит фигуре, если X находится в пределах от –R до R, при этом Y ≥ – R.

Нач

ввести R, X, Y

если Y > 0

тоесли X * X + Y * Y > R * R

товывести “Не принадлежит”

иначевывести “Принадлежит”

Все

иначеесли X ≥ –R и X ≤ R и Y ≥ –R

товывести “Принадлежит”

иначевывести “Не принадлежит”

Все

Все

Кон

Вспомогательные алгоритмы

В процессе разработки алгоритмов мы довольно часто имеем сходные по структуре последовательности команд, которые применяются в разные моменты и с различными данными. Такие последовательности команд обычно выделяют в специальные алгоритмы. Их принято называть вспомогательными алгоритмами, подпрограммами или функциями.

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

Здесь же важным для нас является то, что функция получает извне некоторые сведения на вход и, совершив с этими сведениями ряд действий, дает результат на выходе. С этой точки зрения функцию можно рассматривать как абстрактный «черный ящик», внутреннее устройство которого недоступно извне, а мы можем только взаимодействовать с ее входами и выходами. Говорят, что пользователю доступен только интерфейс функции.

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

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

Могут использоваться две формы вспомогательных алгоритмов.

В первой из них все параметры являются исходными данными вспомогательного алгоритма.

алг Название (Список параметров)

Нач

Действия …

вернуть Результат работы

Кон

Например, таким образом можно записать вспомогательный алгоритм вычисления квадрата числа X.

алг квадрат (X)

Нач

вернуть X * X

Кон

Другим примером подобного вспомогательного алгоритма является поиск минимального из двух величин A и B.

алг минимум (A, B)

Нач

если А < В

товернуть А

иначевернуть В

Все

Кон

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

Z:= минимум (X, Y)

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

алг Название (арг Список исходных данных рез Список результатов)

Нач

Действия …, среди которых

присваивание переменным из списка результатов итоговых значений

Кон

Например, таким может быть алгоритм сокращения рациональной дроби, где на вход дается пара целых чисел: числитель и знаменатель. Их новые значения после сокращения должны быть результатами работы вспомогательного алгоритма. Предположим, у нас имеется функция НОД(A, B), которая находит наибольший общий делитель двух натуральных чисел A и B.

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

алг Сократить (алг A1, B1, рез A2, B2)

Нач

C:= НОД(A1, B1)

A2:= A1 / C

B2:= B1 / C

Кон

Вызов такого вспомогательного алгоритма может иметь вид:

Сократить (12, 9, X, Y).

В итоге получим X=4, Y=3.

При этом, переменные основной программы X и Y, а также величины 12 и 9 называются фактическими параметрами вспомогательного алгоритма, поскольку именно с ними фактически и происходят действия внутри алгоритма. Переменные A1, A2, B1, B2 в заголовке вспомогательного алгоритма называются формальными параметрами. В момент вызова вспомогательного алгоритма на выполнение происходит присваивание значений фактических параметров в A1 и B1 соответственно. По завершении работы вспомогательного алгоритма происходит присваивание значений из A2, B2 в X, Y.

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

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

В качестве примера рассмотрим программу, расположенную справа, для исполнителя Робот (смотри задачу 2 в предыдущей теме). Довольно сложно разобраться в этом тексте программы и понять ее назначение. Присмотревшись внимательнее, можно заметить, что одна и та же последовательность команд встречается три раза. Она обеспечивает рисование флажка, закрашивая 5 клеток поля. Имеет смысл выделить эту последовательность команд в отдельный вспомогательный алгоритм, а в основном алгоритме он должен трижды вызываться.   В данном случае рисование флажка происходит абсолютно одинаково, т.е. у этого вспомогательного алгоритма параметров не предусмотрено. Можно считать, что в системе команд исполнителя появляется еще одна новая команда – нарисовать флажок. Программа примет следующий вид: Алгоритм стал компактнее, доступнее для понимания. Становится понятно, что в целом происходит рисование трех флажков с определенными сдвигами. алг флаг нач закрасить вправо закрасить вниз закрасить влево закрасить вниз закрасить кон алг основной нач вниз флаг вниз вправо флаг вправо вправо вправо флаг кон

нач вниз закрасить вправо закрасить вниз закрасить влево закрасить вниз закрасить вниз вправо закрасить вправо закрасить вниз закрасить влево закрасить вниз закрасить вправо вправо вправо закрасить вправо закрасить вниз закрасить влево закрасить вниз закрасить кон

Рассмотрим, для чего следует выделять последовательности команд во вспомогательные алгоритмы. Вспомогательный алгоритм (подпрограмма) – инструмент, который позволяет:

сократить текст основного алгоритма за счет отсутствия многократных описаний одних и тех же повторяющихся действий;

облегчить понимание текста программы, делая его похожим на текст на естественном языке, при условии, конечно, использования содержательных имен процедур;

расширять СКИ, поскольку новый вспомогательный алгоритм можно воспринимать как новую команду, которую теперь может делать исполнитель;

свести новую задачу к уже решенным, используя уже написанные алгоритмы как вспомогательные;

писать, проверять и отлаживать большую программу по частям;

модифицировать программы и исправлять в них ошибки, не затрагивая тех частей алгоритма, которые остаются без изменения;

в сочетании с методом последовательной детализации алгоритмов решить сложную задачу, разбивая ее на более мелкие и легкие подзадачи;

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

Методика последовательной детализации алгоритма

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

Сборочный метод

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

На практике часто оба эти подхода дополняют друг друга.

Теперь мы можем точно сформулировать, что происходит при вызове вспомогательного алгоритма на выполнение:

На время выполнения вспомогательного алгоритма выполнение основного алгоритма приостанавливается.

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

Устанавливаются значения формальных параметров, равные фактическим, указанным в команде вызова в основном алгоритме.

Выполняется вспомогательный алгоритм.

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

Возобновляется выполнение основного алгоритма.