Технология построения алгоритмов


§ 59. Технология построения алгоритмов

Изучив этот пункт, мы:

Познакомимся с технологией построения алгоритмов;

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

==== 59.1.Технологический подход к построению алгоритма ============================

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

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

Основой любого программного продукта является алгоритм. Мы познакомимся с Технологией разработки алгоритма, основанного на трех основных принципах:

·  проектирования алгоритма Методом пошаговой детализации, или Методом «сверху вниз»;

·  организация алгоритма в виде относительно независимых частей — модулей;

·  применение унифицированных алгоритмических структур.

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

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

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

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

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

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

Читать  Лекция Операторы языка Паскаль

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

==== 59.2.Главный и вспомогательные модули. Формальные и фактические параметры ==============

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

Связь между главным и вспомогательными модулями устанавливается через указание о выполнении вспомогательного модуля. Это указание называется Вызовом модуля.

Вызов должен содержать:

·  имя модуля, вызывается;

·  входные данные, которые он проработать;

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

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

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

==== 59.3.Программа и процедуры ===============================================

При подаче алгоритма на языке программирования описание всех модулей приводится в программе. Главный модуль составляет тело программы. Описания вспомогательных модулей приводятся в описательной части программы — после объявления переменных основной программы.

Вспомогательные модули в языке Паскаль называются Процедурами (от англ. Procedure — метод действий).Описание процедуры вполне аналогичный описания программы, однако имеет существенные отличия:

·  описание процедуры начинают служебным словом Procedure (а не Program)

·  после имени процедуры в круглых скобках размещают перечень формальных параметров с объявлением их типов. Перечень имен переменных-результатов предшествует служебное слово Var;

·  описание процедуры завершается служебным словом End и точкой с запятой, а не точкой.

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

Читать  Алгоритмизации и программирования Текст Лекций на языках Pascal, VBA, C ++

Procedure distance (xp, yp, xk, yk: Real; Var d: Real) Begin

D = sqrt (sqr (xk — xp) + sqr (yk — yp))

End;

Как видим, в процедуре отсутствуют операторы, связанные с введением входных данных и выводом исходных данных.

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

Если описание процедуры distance приведены в описательной части программы, то с любого места программы можно вызвать эту процедуру таким, например, образом:

Distance (0, 5, 0, 17 z)

В результате такого вызова переменная z получит значение 12.

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

Например, при выполнении процедуры distance по вызову

Distance (xa, ya, xb, yb, ab)

Текущие значения переменных Xa, ya будут использованы как координаты начальной точки отрезка, значение переменных Xb, yb как координаты его конечной точки. Переменная ab получит значение длины отрезка. Если на момент вызова процедуры xa = 0, ya = 5, xb = 0, yb = 17, то переменная ab примет значение 12.

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

==== 59.4.Задача Дидоны (треугольный вариант) ====================================

Продемонстрируем применение процедур на примере задачи Дидоны.

По древней легенде, Дидону, дочь и наследницу могущественного царя, братья решили лишить престола. Они вывезли Дидону на пустой берег моря, дали ей кожу быка и сказали: «Построй себе город на этой коже и царствуй в нем».Не растерялась Дидона. Порезала она кожу на тонкие полоски, связала их в длинную веревку и охватила этой веревкой большой кусок прибрежной земли. Удивились брать мудрости Дидоны и не стали препятствовать строительству сначала новой крепости, а затем и нового города. Так был основан Карфаген.

Читать  Файлы Паскаль, файловый тип, Процедуры и Функции в Pascal

Сформулируем задачу Дидоны в упрощенном варианте. Будем считать, что для закрепления кожаной веревки Дидона имела три колышки. Предположим также, что кожа быка имеет площадь 4 кв. метра, а ширина полосок, на которые Дидона ее разрезала, составляет 1 мм. Итак, длина кожаной веревки составляет 4000 м. Задача состоит в том, чтобы определить, каким образом и какую наибольшую площадь может оградить Дидона с помощью трех колышков и веревки длиной d = 4000 м.

Проанализируем постановку задачи. Участок земли, которую могла оградить Дидона, имеет форму треугольника. Одну его сторону (обозначим ее AC) образует линия моря, две другие — веревка, натянутая на колышки, установленные в точках А, В и С. Задача сводится к определению треугольника самой большой площади, у которого сумма длин двух сторон является заданной: AB + BC = d. Определение треугольника в нашем случае сводится к определению длин сторон АВ и ВС.

Разработаем информационную модель задачи. Обозначим через ac и ab, соответственно, значения длин сторон АC и AB. Очевидно, что значение ac и ab должны быть меньше d. Длину стороны BC обозначим через bc. Значение bc будем находить по формуле: bc = d — Ab.Площадь треугольника (обозначим ее через s) будем определять по трем известными длинами его сторон по формуле Герона.

Алгоритм вычисления значения s состоит из следующих действий: задать значение ac и ab, найти значение bc, вычислить s.

Разработаем компьютерную модель задачи. Переменные ab, ac, bc, s объявим как переменные вещественного типа, постоянную величину d представим как константу. Для вычисления площади треугольника воспользуемся процедурой Geron.

Program Didona;

Uses Crt;

Const d = 4000;

Var ab, ac, bc, s: Real;

Procedure Geron (a, b, c: Real; Var s: Real) {Подаем описание процедуры}

Var p: Real; Begin

P = (a + b + c) / 2;

S = sqrt (p * (p — a) * (p — b) * (p — c));

End;

Begin Clrscr;

Writeln ( ‘Введите расстояние AC (<4000):’); {Вводим исходные данные:}

Readln (AС) {выбраны значения Длин}

Writeln ( ‘Введите расстояние AB (<4000):’); {двух сторон треугольника}

Readln (ab)

Bс = d — ab; {Находим значение длины Третьей Стороны} Geron (ab, bc, ac, S) {Вычисляем Площадь Треугольника} Writeln ( ‘Площадь:’, s: 10: 1, » кв. м ‘); {Выводим Результат} Readln;

Читать  Лекция Паскаль 1 – Создание проекта, создание форм, обработка событий

End.

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

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

Установите значение.

ВЫВОДЫ

Контрольные вопросы и упражнения

1. Что значит проектирования алгоритма методом «сверху вниз »?

А) постепенное раздробление задачи на все более простые составляющие;

Б) запись алгоритма, начиная с верхней строки и до самого нижнего;

В) управление процессом проектирования алгоритма с верхней до нижней звена.

2. Модульная организация алгоритма — это:

А) организация алгоритма из крупных блоков;

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

3. Вызов модуля содержит

А) имя модуля, который вызывает вспомогательный; б) имя модуля, который вызывается;

В) входные данные, необходимые для выполнения модуля

Г) имена переменных для хранения результатов выполнения модуля.

4. В следующих утверждениях пропущенные слова Формальные и Фактические. Вставьте нужные слова вместо троеточий.

А) … параметры присутствуют в описании процедуры, а… — в ее вызова

Б) … параметры используются в теле процедуры для описания действий, а… — для их выполнения;

В) через… параметры процедуре передаются значения аргументов и от нее получаются значения результатов;

Г) … параметры замещают… в момент вызова процедуры.

5. Процедура summa (a, b: Integer; Var s: Integer) находит значение s как сумму чисел a и b. Оператор вызова этой процедуры является правильным и что позволит предоставить целой переменной X значение суммы чисел 10 и 5?

А) summa (10, 5: Integer; Var x: Integer);

Б) summa (10, 5, x = s);

В) summa (10, 5, x)

Г) summa (10, 5; x)

Д) summa (5.0, 10.0, x)

Е) summa (10, 5, Var x).

6. Процедура average (n, m, k: Integer; Var x: Real) находит значение x как среднее арифметическое чисел n, m и k. Какие операторы вызова этой процедуры не содержат ошибок, если все переменные являются переменными действительного типа?

А) average (4, 5, 6, z3)

Читать  Величины и их описание, Общая структура алгоритма

Б) average (10, 5.0, 20, s);

В) average (10, 5, 200, x)

Г) average (426848, 15254, 16666, z)

Д) average (25, 31, 23: Integer; Var z: Real)

Е) average (10 + 5, 89-45, 8 * 7, x)

Е) average (75, 81/9, 3, x)

Ж) average (sqr (2), Sqr (3), Sqr (4), seredne).

7. Составьте процедуру, которая выводит на экран строку из 20 звезд, начиная с заданной позиции. Используйте эту процедуру для составления программы вывода на экран 5 разноцветных строк звездочек.

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

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

10. С помощью программы Didona проведите эксперимент и определите, какую площадь могла оградить Дидона с помощью трех колышков. Модифицируйте программу Didona для нахождения площади, которую можно оградить с помощью четырех колышков. Объясните полученные результаты. Ответьте на вопрос:

1) Какой формы приобретает участок Дидоны с увеличением количества колышков?

2) Если веревку можно было просто разложить на земле, как действовала мудрая Дидона и на какой площади был основан древний Карфаген?

8

11. Составьте программу определения площади выпуклого пятиугольника, заданного координатами его вершин на плоскости.  Воспользуйтесь процедурами distance (см. П.59.3) и Geron (см. П. 59.4).

12. Составьте программу решения задачи о вороне. На вершине дерева с золотыми яблочками сидит ворона. Она хочет украсть яблочко — одно из тех, что рассыпаны вокруг дерева. Участок с яблоками огородили забором. Яблоки охраняет сторож. Какое яблоко следует схватить вороне, чтобы как можно быстрее вылететь за забор? Высота дерева h, забора — z, расстояние от дерева до забора — r.

Рассмотрите два варианта задачи:

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

2) вверх ворона летит медленнее, чем вниз.

Для составления программы воспользуйтесь процедурой distance (п.59.3).

[Всего голосов: 3    Средний: 5/5]