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

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

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

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

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

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

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

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

нет

да

Рисунок 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].

да

нет

да

нет

Вход в цикл

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

шага цикла

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа – это алгоритм, записанный на языке программирования. Вышеприведенные алгоритмы задач переведем на язык программирования Паскаль [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

Writeln(‘Vvedite n= ’);

Read(n);

Pi:=3.14;

For r:=1 to n do

Begin

P:=2*pi*r;

Writeln(‘r= ’,r,’ p= ’,p);

End;

End. [14]

Результат выполнения программы Cycle1.pas с циклом for дан на рис. 10.

Рис. 10 - Результат выполнения программы Cycle1.pas с циклом for

Программа Cycle2.pas с использованием цикла Repeat …until.

Program Cycle2;

Var

P,pi: real;

R,n: integer;

Begin

Writeln(‘Vvedite n= ’);

Read(n);

Pi:=3.14;

R:=1;

Repeat

P:=2*pi*r;

Writeln(‘r= ’,r,’ p= ’,p);

r:=r+1;

until r>n;

end. [16]

На рис. 11 приведен скриншот выполнения программы Cycle2.pas с использованием цикла Repeat …until.

Рис.11 - Результат выполнения программы Cycle2.pas с использованием цикла Repeat …until

Программа Cycle3.pas с циклом while.

Program Cycle3;

var P,pi: real;

R,n: integer;

Begin

Writeln(‘Vvedite n= ’);

Read(n);

Pi:=3.14;

R:=1;

While (r<=n) do

begin

P:=2*pi*r;

Writeln(‘r= ’,r,’ p= ’,p);

r:=r+1;

end;

end. [9]

На рис. 12 приведен результат выполнения программы Cycle3.pas с использованием цикла while.

Рис. 12 - Результат выполнения программы Cycle3.pas с использованием цикла while

Программа Cycle4.pas с циклом с неизвестным числом повторений.

Программа вычисляет значение функции у = 2cos(x)+sin(x) c шагом dx=0,5 с точностью 0,01 [12].