Файл: программирование на паскале2.doc

1.4.2. Алгоритм и способы его записи.

Алгоритм – это представление процесса решения некоторой задачи в виде совокупности конечного числа элементарных действий. Слово "алгоритм" произошло от латинского перевода имени выдающегося ученого-энциклопедиста Мухаммеда Аль Хорезми (780-850), которые впервые описал правила (т. е. алгоритмы) десятичной арифметики.

Строгое определение алгоритма дается в теории алгоритмов. Здесь лишь стоит отметить, что алгоритм должен обладать следующими свойствами:

1. Универсальность(массовость) - это возможность решения с помощью алгоритма класса задач (не одной задачи). Класс задач определяется областью возможных значений исходных данных.

2. Конечность(результативность) - обязательное получение результата законечноечисло действий.

3. Определенностьозначает, что при многократном выполнении алгоритма с одними и теми же исходными данными мы получим одинаковые результаты; другими словами, определенность - это отсутствие случайности.

Известны различные способы записи алгоритма. До сих пор широко применяется словесное описание алгоритма "по шагам". Программа в кодах ЭВМ или на любом алгоритмическом языке - другой пример записи алгоритма. Блок-схемыпредставляют собой еще один способ записи алгоритма, более точный, чем словесное описание, и менее формальный, чем программа на алгоритмическом языке. Блок-схемы не зависят от алгоритмического языка и компьютера, с помощью которых будет выполняться алгоритм, и легко воспринимаются.

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

1.4.3. Изображение алгоритмов в виде блок-схем

Блок-схема - это конечное число блоков, соединенных стрелками. Блоки соответствуют определенным действиям, а стрелки указывают последовательность выполнения этих действий. Если стрелка идет вниз, то ее можно не рисовать (оставить линию без стрелки). В соответствии с принципом программного управления функционированием ЭВМ необходимо иметь следующие виды блоков.

1. Вычислительный блок. Используется для изображения любых вычислений (арифметических, логических и др.). Внутри блока записывается действие. Это либо оператор присваивания, либо обобщенное действие (например, "вычисление среднего"). Изображается прямоугольником (см. рис.2, а). Имеет один вход и один выход

2. Блок ввода или вывода. Изображается как параллелограмм (см. рис.2,б). Внутри записывается пояснение, например, "ввод а,b" или "вывод суммы". Имеет один вход и один выход, также как и вычислительный блок.

3. Условный блок. Изображается ромбом (рис.2,в), внутри которого записывается некоторое условие (соотношение или более сложное логическое условие). Имеет один вход и два выхода. Один из выходов (его обозначают "да", или "истина", или "+") соответствует пути алгоритма, где условие выполняется. Другой выход ("нет", "ложь", "‑") соответствует невыполнению условия.

4. Блок начала алгоритма (рис 2, г). Имеет только выход, входа нет.

5. Блок конца алгоритма (рис. 2, д). Имеет только вход.

1.4.4. Базовые структуры алгоритмов и их кодирование на Паскале

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

1. Следование

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

2. Ветвление (развилка)

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

Ветвление предполагает проверку некоторого условия. Если на момент проверки условие истинно, то будет выполнен оператор 1, иначе оператор 2. В Паскале ветвление кодируется с помощью условного оператора:

If условие then

оператор 1

else

оператор 2

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

Возможна ситуация, когда ветвь “Нет ” не содержит операторов В этом случае в условном операторе слово else иоператор 2 отсутствуют.

Если операторы 1 или 2 состоят из нескольких операторов (являются составными), то входящие в них операторы окаймляются операторными скобками begin-end:

If условие then

begin

оператор 1_1;

оператор 1_2;

…

оператор 1_N

end

else

begin

оператор 2_1;

оператор 2_2;

…

оператор 2_M

end

Таким образом, операторные скобки begin-end позволяют объединить несколько операторов в один составной.

3. Цикл

Ц

.

На Паскале циклы кодируются следующим образом:

Тело цикла должно представлять собой один оператор – простой или составной.

Замечания

1. Каждая из трех рассмотренных базовых структур имеет один вход и один выход. Это очень важно, так как любой прямоугольник на рисунках 3 – 5 может представлять собой одну из базовых структур.

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

Кроме того, в программировании широко используется еще одна базовая структура (избыточная), которая называется параметрическим циклом (см. рис.6). Этот цикл управляется переменной (так называемым параметром цикла, на блок-схеме для него выбрано имя i), которая меняется от начального значения до конечного с заданным шагом (в Паскале шаг равен единице). Разработчиками компилятора параметрический цикл может быть реализован и как цикл с предусловием, и как цикл с постусловием. Учитывая практику последнего времени, мы считаем, что параметрический цикл реализован как цикл с предусловием.

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

for i:=нач_знач to кон_знач do

тело цикла;

Существует также вариант оператора for, в котором параметр изменяется с шагом –1:

for i:=нач_знач downto кон_знач do

тело цикла;

Как и для предыдущих операторов, тело цикла – один оператор, простой или составной.

1.4.5. Примеры разработки программ

Пример 1. Программа решения квадратного уравнения

ax² + bx + c=0

Исходные данные:a,b,c- коэффициенты уравнения, вещественные переменные.

Выходные данные:х1, х2 - значения двух корней уравнения, если дискриминант неотрицателен, и значения вещественной и мнимой частей комплексно-сопряженных корней, если дискриминант отрицателен; это также вещественные переменные.

Промежуточные данные:d- дискриминант уравнения, вещественная переменная.

Блок-схема алгоритма представлена на рис.7. Алгоритм должен разделяться на две ветви в зависимости от знака дискриминанта, поэтому он использует базовую структуру ветвление. Ввод исходных данных,вычисление и анализ dсоединены последовательно (используется базовая структура следование).

По этой блок-схеме написана программа:

Program kv_ur;

Var a,b,c,x1,x2,d:real;

Begin

Writeln('введите коэффициенты уравнения');

Readln(a,b,c);

d:=sqr(b)-4*a*c;

if d>=0 then

begin

x1:=(-b-sqrt(d))/2/a;

x2:=(-b+sqrt(d))/2/a;

writeln('действ. корни уравнения х1=',x1, 'x2=',x2)

end

else

begin

x1:=-b/2/a;

x2:=sqrt(-d)/2/a;

writeln(‘уравнение имеет комплексно-сопряженные корни’);

writeln('мнимая часть компл. корней х2=',x2);

writeln('действит. часть компл. корней х1=',x1)

end;

Readln;{для задержки экрана с результатами}

End.

Пример 2.Составить программу решения следующей задачи.

На начало первого из рассматриваемых месяцев вклад клиента в банке был равенaруб. В течение каждого следующего месяца со счета снимаетсяb руб.; в конце каждого месяца на остаток вклада начисляетсяр%. Вывести величину вклада на начало 1, 2,...n месяца.

Исходные данные:a,b,p- вещественные переменные,n- целая переменная.

Выходные данные: i - номер месяца, v - величина вклада на начало месяца.

Блок-схема алгоритма приведена на рис. 8.

Program primer2;

Var a,b,p,v:real; n,i:integer;

Begin

Writeln('Введите a,b,p,n');

Readln(a,b,p,n);

If a<b then

writeln('a,b недопустимы')

else

begin

v:=a;

i:=1;

while (i<=n) and (v>=b) do

begin

writeln(i:7, v);

v:=v-b;