Конспект по информатике "Разбиение задачи на подзадачи. Вспомогательный алгоритм" для самостоятельной подготовки к контрольным работам, экзаменам и ГИА.

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

Код ОГЭ: 1.3.4. Разбиение задачи на подзадачи, вспомогательный алгоритм



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

Структурный подход предполагает составление алгоритмов и программ методом «сверху вниз» (нисходящее программирование). При этом задача сначала рассматривается в целом, затем разбивается на крупные блоки, те в свою очередь — на блоки поменьше и т. д. Эти блоки должны быть логически завершенными. Процесс разбиения продолжается до тех пор, пока задача не будет представлена в виде ряда простых задач, для которых легко составить алгоритм. Такой метод называется методом пошаговой детализации. Он предполагает постепенный переход от более общих задач к более частным и к их подзадачам.

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

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

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

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

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

Существует и иной подход: сначала составляется множество подпрограмм, реализующих различные частные задачи, а затем создается основная программа, содержащая их вызовы. Обычно такие подпрограммы объединяют в библиотеку подпрограмм, которая может пополняться с течением времени. Такой подход называют методом программирования «снизу вверх».

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

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

Подпрограмма может быть реализована в виде функции или процедуры. Различия между ними — в способах вызова (использования) и передачи вспомогательному алгоритму параметров. Подпрограмма–функция вырабатывает результат — вычисляет некоторое единственное значение, которое присваивается ее имени (идентификатору).

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

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

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

Решение. Длина отрезка может быть рассчитана по формуле , где (x1, y1) и (x2, y2) — координаты концов этого отрезка.

Таким образом, алгоритм будет иметь 5 параметров: 4 координаты точек и переменную для будущего результата. Обозначим рассчитываемую длину через l.

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

В этом вспомогательном алгоритме отсутствуют команды ввода исходных и вывода результирующих данных. Это будет организовано в основном алгоритме. Например, для расчета длины отрезка d с координатами вершин (0, 0) и (2, 5) в основной программе надо будет указать команду Segment (0, 0, 2, 5, d).

Составим основной алгоритм расчета периметра треугольника P с вершинами (a1, b1), (a2, b2) и (a3, b3). Для этого необходимо будет вычислить длины отрезков (l1, l2, l3) трижды. Поэтому основной алгоритм будет трижды вызывать созданный вспомогательный Segment. Каждый раз при вызове будут указываться координаты вершин очередного отрезка и переменная для сохранения его длины.

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


Конспект урока по информатике «Вспомогательный алгоритм».

Вернуться к Списку конспектов по информатике.

 

Добавить комментарий

На сайте используется ручная модерация. Срок проверки комментариев: от 1 часа до 3 дней