Разбиение задачи на подзадачи, вспомогательный алгоритм

Сегодня на уроке мы вспомним:

· Что такое вспомогательный алгоритм;

· Чем отличается процедура от функции.

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

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

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

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

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

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

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

Давайте вспомним как выглядит вспомогательный алгоритм на блок-схеме.

Этот блок называется «Предопределённый процесс», внутри него записывается название вспомогательного алгоритма, входные и выходные параметры.

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

var a: integer;

procedure reverse(n: integer);

 begin

 write(n mod 10);

 if (n div 10) <> 0 then

 reverse(n div 10)

 end;

begin

 readln(a);

 reverse(a);

 writeln;

end.

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

Подпрограммы делятся на процедуры и функции.

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

Сначала идёт служебное слово Procedure, и через пробел указывается имя процедуры. Не забудьте, что имя процедуры не должно совпадать с именем программы, названием служебных слов или переменных, остальные требования те же, что и к имени программы, то есть оно может состоять из 1 до 255 цифр, букв латинского алфавита и знаков подчёркивания, и должно начинаться с буквы латинского алфавита или знака подчёркивания. После имени процедуры в круглых скобках, как в разделе описания переменных, необходимо перечислить сначала входные параметры с указанием типа, затем после служебного слова var перечисляются выходные параметры с указанием типа. В конце строки ставится точка с запятой. Если необходимы промежуточные переменные, то строкой ниже записывается раздел описания переменных процедуры, который, как и в основной программе, начинается со слова var. Далее, между служебными словами begin и end, следует тело процедуры. В данном случае после служебного слова end ставится точка с запятой.

procedure <имя процедуры> (<входные параметры>;

var <выходные параметры>);

var

<промежуточные переменные>;

begin

<тело процедуры>

end;

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

program tes;

var

a: integer;

b, c: real;

procedure nomer (x: real, k: integer;

var t: real);

…

begin

…

nomer (b, a, c);

nomer (3.9, 5, b);

…

end.

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

Ещё одним видом подпрограмм, кроме процедур, являются функции.

Функция – это подпрограмма, которая возвращают всего одно значение. Оно сохраняется в ячейке памяти с именем, которое совпадает с названием функции. То есть функция принимает на вход несколько или одну переменную, а по выполнении команд возвращает всего одну переменную, с именем, которое совпадает с названием функции, в отличие от процедуры, которая может возвращать несколько переменных.

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

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

Затем между служебными словами begin и end следует тело функции. Так как значение возвращаемое функцией сохраняется в переменную, название которой совпадает с её названием, тело функции должно содержать хотя бы одну команду присваивания переменной с этим названием какого либо значения. Как и при записи процедуры после служебного слова end следует точка с запятой.

function nomer (<входные параметры>:

<тип возвращаемого значения>);

var

<промежуточные переменные>;

begin

<тело функции>

nomer := …;

end;

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

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

program tes;

var

a, c: integer;

b: real;

function nomer (x: real, k: integer): integer;

…

begin

…

a := nomer (b, b) + 10;

Writeln (nomer(3.1, 5))

…

end.

Выполним несколько заданий.

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

Запишем решение на алгоритмическом языке. Итак, длина отрезка может быть рассчитана по следующей формуле:, где (x1, y1) и (x2, y2) – координаты концов этого отрезка.

У алгоритма будет 5 параметров: из них четыре это координаты точек и один параметр – это переменная для будущего результата.

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

алг Dlina (вещ a1, b1,a2,b2,l)

 арг a1, a2, b1, b2

 рез l

нач

 l := ((a1 – a2)2 + (a1 – a2)2)1/2

кон

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

Составляем основной алгоритм расчёта периметра треугольника P с вершинами (k1, m1), (k2, m2) и (k3, m3). Для этого нужно будет вычислить длины отрезков (l1, l2, l3) три раза. Таким образом в основном алгоритме будет трижды вызывать созданный вспомогательный алгоритм Dlina. Каждый раз при вызове будут указываться координаты вершин очередного отрезка и переменная для сохранения его длины.

алг Perimetr

нач

вещ k1, k2, k3, m1, m2, m3

вещ l1, l2, l3

ввод k1, k2, k3, m1, m2, m3

Dlina (k1, m1, k2, m2, l1)

Dlina (k1, m1, k3, m3, l2)

Dlina (k2, m2, k3, m3, l3)

P := l1 + l2 + l3

вывод P

кон

Следующее задание.

Напишите функцию, которая возвращает среднее арифметическое двух переданных ей аргументов (параметров).

Теперь решим задачу на Паскале.

В программе создадим функцию average, которая имеет два вещественных параметра (c и d) и возвращает также вещественное число. В теле функции вычисляется среднее арифметическое аргументов, оно присваивается имени (идентификатору) функции. В языке программирования Pascal это означает, что присвоенное имени функции значение будет передано в основную ветку программы.

В основном алгоритме переменным a и b присваиваются значения, которые вводит пользователь. Далее вызывается функция average(), которой в качестве аргументов передаются значения этих переменных. В данном случае вызов функции не присваивается никакой переменной, так как возвращенное значение сразу будет выведено на экран.

var

 a, b: real;

function average(c, d: real): real;

begin

 average := (c + d) / 2;

end;

begin

 readln(a, b);

 writeln(average(a, b):5:2);

end.

Ну что же, попробуйте ответить на следующие вопросы:

Что такое вспомогательный алгоритм?

Какие подпрограммы выделяют?

Как называется подпрограмма, которая возвращает всего одно значение?

Внимательно посмотрев урок, вам не составит труда ответить на вопросы.