Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Программная реализация основных алгоритмических структур на языке высокого уровня Паскаль).pdf

Как видно из блок-схем, цикл «повторение ДО» выполняется, по крайней мере, один раз, а цикл «повторение ПОКА» может сразу выйти из цикла.

Подготовка выполнения первого цикла

Подготовка выполнения первого цикла

Условие окончания

да

Тело цикла

Подготовка выполнения следующего цикла

нет

Тело цикла

Подготовка выполнения следующего цикла

Условие окончания

нет

да

а б

Рисунок 3 - Циклы с известным числом повторений [7; с. 16-17]

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

│Y_i –Y_i-1│<d, где d – допустимая точность вычисления.

Типовую структуру алгоритма итерационных вычислений демонстрирует рис. 4 [2; с. 11-13].

Y₁=Y(0)

Задание начальных условий

Первая итерация

Y=f (Y₁)

Вычисление текущей ошибки

D=│Y -Y₁ │

Y₁=Y

Переприсвоение

D≤d

Оценка точности

нет

да

Рисунок 4 - Циклы с неизвестным числом повторений [7; C. 19]

Сложные циклы. Вычислительные процессы, содержащие два и более включенных друг в друга циклов, называются сложные циклические процессы (алгоритмы). Цикл, содержащий внутри себя другой цикл, называется внешним, а содержащийся внутри цикл - внутренним (вложенным). Нужно учесть, что за одно выполнение внешнего цикла происходит многократное повторение внутреннего цикла [12; С. 23].

Пример 5. Разработать алгоритм вычисления и вывода на печать функции y = x*z / (b + c) при изменении аргументов 1< x < 8 c шагом ∆x = 1 и 1< z<5 c шагом ∆z = 1. Алгоритм решения примера приведен на рис. 5.

Внутренний цикл организован по переменной z, а внешний - по переменной x. При каждом значении переменной x (переменной внешнего цикла) от 1 до 8 переменная z (переменная внутреннего цикла) изменяется от 1 до 5 с шагом 1 [8].

Блок вывода на печать находится во внутреннем цикле, что позволяет отслеживать значения переменных на всем диапазоне их изменения. На рис. 6 эту же задачу решает модифицированная блок-схема алгоритма, в которой циклы представлены более компактными условными обозначениями, принципы организации которых проясняет рис. 7 [7; С. 21].

Ввод А,В

y=x*z/(A+B)

z=1

x=1

Ввод А,В

Х=1,10,1

Вывод x, y, z

z=1,4,1

z=z+1

да

y=x*z/(A+B)

z≤4

нет

Вывод x, y, z

x=x+1

x≤10

да

нет

Конец

Конец

Вход в цикл

Х=1,10,2

Вход i+1 Выход из цикла

шага цикла

Выход i-го шага цикла

Рис. 7 – Компактные условные обозначения [7; С. 22]

Первой цифрой внутри фигуры (рис. 7) задается начальное значение переменной, второй ее конечное значение, а третьей - шаг изменения переменной. При отсутствии последней цифры шаг изменения переменной по умолчанию равен 1 [7; с. 18-22].

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

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

2. Программная реализация основных алгоритмических структур на языке высокого уровня Паскаль

2.1. О языке высокого уровня Паскаль

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

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

Паскаль - язык профессионального программирования, названный в честь французского математика и философа Блеза Паскаля (1623-1662гг.) и разработанный в 1968-1971гг. Никлаусом Виртом, профессором Цюрихского технического университета (Швейцария). Первоначально язык разработан для обучения, но вскоре стал использоваться для разработки программ [4; с. 5-17].

Не менее впечатляющей, в том числе и финансовой, удачи добился Филип Кан, француз, разработавший систему Турбо-Паскаль. Суть его идеи состояла в объединении последовательных этапов обработки программы – компиляции, редактирования связей, отладки и диагностики ошибок – в едином интерфейсе. Версии Турбо-Паскаля заполонили практически все образовательные учреждения, программистские центры и частные фирмы. На базе языка Паскаль созданы несколько более мощных языков (Модула, Ада, Дельфи) [2; c. 20].

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

Паскаль популярен среди программистов по следующим причинам:

1. Простой для обучения.
2. Позволяет отражение фундаментальных идей алгоритмов в легко воспринимаемой форме, что предоставляет программисту средства для проектирования программ.
3. Позволяет четкую реализацию структурного программирования и структурной организации данных.
4. Использует простые и гибкие структуры управления: ветвления, циклы.
5. Надежность разрабатываемых программ.

Программа – это алгоритм, записанный на языке программирования. Вышеприведенные алгоритмы задач переведем на язык программирования Паскаль [11].

2.2. Операторы цикла в Паскаль

Операторами цикла описываются повто­ряющиеся процессы. Повторяющиеся действия называют телом цикла. В общем случае число повторений тела цикла каким-то образом задается. В ином случае такой процесс будет бесконечен­.

Для окончания повторений нужно связать возврат в начало тела цикла с условием, задаваемым в виде явного счетчика или иным способом. Основной способ проверки возможного окончания цикла - определение функции f(x) (X – множество переменных программы) такой, что f(X) ≤ 0 удовлетворяет условию окончания, а также доказательство убывания этой функции.

Простейший вид такой функции - обычный счетчик, т.е. функция вида i:=i-1 либо i:=i+1 (происходит вычита­ние или прибавление единицы после каждого повтора). В первом случае происходит убы­вание некоторого начального значения i (к примеру, n) до некоторого конеч­ного значения (к примеру, 1). Тогда условие завершения цикла будет i ≤ 1 и число повторений равно n. Во втором случае счет может быть начат с i равного 1 и убывает разность между текущим значением i и ко­нечным значением n, проверка которой на меньше-равно нулю аналогична проверке условия i ≤ n.

Язык Паскаль имеет три разных оператора, посредством которых возможно программирование повторяющихся фрагментов программ [9; с. 58].

2.2.1 Оператор цикла FOR

Структура счетного оператора цикла FOR следующая:

FOR <парам_цикла> := <нач_значение> ТО <кон_значение> DO <оператор>

Здесь FOR/ TO, DO - зарезервированные слова (для/до, делать);

<парам_цикла> - параметр цикла в виде переменной типа INTEGER (может быть любой порядковый тип);

<нач_значение> - начальное значение - выражение такого же типа;

<кон_значение> - конечное значение - выражение такого же типа;

< оператор > - любой оператор Паскаля.

При выполнении оператора FOR сначала вычисляется выражение <нач_значение> и присваивается <парам_цикла> : = <нач_значение>. После этого циклическое повторение:

• проверки условия <парам_цикла <= <кон_значение>; при не выполнении условия завершается работа оператора FOR;
• выполнения оператора <оператор>;
• наращивания переменной <парам_цикла> на единицу [10; С 37].

При этом, условие, которое управляет работой оператора FOR, проверяется до выполнения оператора <оператор>, при не выполнении условия в самом начале работы оператора FOR, исполняемый оператор не выполняется ни разу. Шаг параметра цикла строго постоянный и равен (+1). Есть другая форма оператора:

FOR <парам_цикла>: = <нач_значение> DOWNTO <кон_значение> DO <оператор>

При замене зарезервированного слова ТО на DOWNTO шаг наращивания параметра цикла становится (-1), а управляющее условие становится <парам_цикла> = <кон_значение> [10; С. 37].

2.2.2 Оператор цикла WHILE…DO

Оператор цикла WHILE с предпроверкой условия:

WHILE <условие> DO <оператор>.

Здесь WHILE, DO - зарезервированные слова (пока [выполняется условие], делать);

<условие> - логическое выражение;

<Оператор> - любой оператор Паскаля.

При значении выражения <условие> TRUE выполняется <оператор>, после вычисляется выражение <условие> и повторяется его проверка.

При значении <условия> FALSE , прекращается работа оператора WHILE.

Приведем пример 2 для иллюстрации использования оператора WHILE.

While Counter < 10 do

begin

Writeln(‘Значение счетчика равно ’,Counter);

Counter:= Counter+2;

End; [16]

2.2.3 Оператор цикла Repeat…until

Оператор цикла REPEAT. .. UNTIL с постпроверкой условия имеет вид:

REPEAT <тело__цикла> UNTIL <условие>

Здесь:

REPEAT, UNTIL — зарезервированные слова (повторять до тех пор, пока не будет выполнено условие);

<тело_цикла> — является произвольной последовательностью операторов Паскаля;

<условие> — логическое выражение.

Операторы <тело_цикла> выполняются хотя бы один раз, после этого вычисляется выражение <условие>: при его значении FALSE, происходит повтор операторов <тело_цикла>, иначе завершение работы оператора REPEAT. .. UNTIL [11; С. 37].

Пара REPEAT. .. UNTIL аналогична операторным скобкам begin .. end, и потому перед UNTIL точка с запятой не обязательна.

Для гибкости управления операторами цикла FOR, WHILE и REPEAT в составе Паскаля есть две процедуры:

BREAK — реализация немедленного выхода из цикла; управление передается оператору, следующему сразу за концом оператора цикла;

CONTINUE — реализация досрочного завершения очередного прохода цикла; эквивалентна передаче управления в самый конец циклического оператора.

Введением в язык этих процедур практически исключается необходимость использования оператора безусловного перехода GOTO, который нежелательно использовать [11; С. 38].

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

Программа расчета площади круга на языке Паскаль:

Program SR;

Var

R,s,pi: real;

Begin

Writeln(‘Vvedite radius r=’);

Readln(r);

Pi:=3.14;

S:=pi*r*r;

Writeln(‘Ploshad kruga s= ’,s, ‘ radius r= ’,r);

End.

Ниже на рис. 8 приведен скриншот выполнения программы - при радиусе 5 площадь круга равна 78,5 [11].

Рис. 8 - Результат выполнения программы SR.pas

Программа реализации разветвляющегося алгоритма Vetvi.pas:

Program Vetvi;

Var

X,f: integer;

Writeln(‘Vvedite x= ’);

Readln(x);

If x>0 then f:=2*x

Else f:=x*x;

Writeln(‘x= ’,x,’ f= ’,f);

End. [12]

На рисунке 9 приведен скриншот выполнения программы Vetvi.pas.

При х = 4 f = 8,

при х = -3 f = 9.

Рис. 9 - Результат выполнения программы Vetvi.pas

2.4. Реализация циклических алгоритмов

Цикл for

Program Cycle1;

Var

P,pi: real;

R,n: integer;

Begin