Основные управляющие структуры

ОСНОВЫАЛГОРИТМИЗАЦИИ.

Понятие алгоритма - исполнителя алгоритма

Слово «алгоритм» происходит от algorithmi — латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.

Алгоритм — это организованная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.

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

Вся совокупность таких команд называется системой команд исполнителя.

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

Компьютер — автоматический исполнитель алгоритмов.

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

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

Основные свойства алгоритма

1) Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

2) Дискретность - запись алгоритма в виде отдельных элементарных действий (исполнение расчленяется на выполнение отдельных шагов: каждый очередной шаг выполняется после завершения предыдущего).

3) Однозначность - единственность толкования правил выполнения и их порядка (этим не обладают предписания для людей).

4) Конечность - обязательное завершение каждого из действий и завершимость алгоритма в целом.

5) Результативность - выполнение алгоритма должно завершаться получением определенных результатов.

6) Массовость - возможность применения для решения целого класса задач, отвечающих общей постановке задач.

На практике наиболее распространены следующие формы представления алгоритмов:

- словесная (запись на естественном языке);

- графическая (изображения из графических символов);

- псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

- программная (тексты на языках программирования).

Основные управляющие структуры

1) Следование - предписывает выполнение указанного набора команд в естественном порядке: одно за другим, без пропусков и повторений.

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

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

begin writeln('Введите a, b'); readln(a,b); c:=a; a:=b; b:=c; writeln('Стало a=',a,' b=',b); readln; end.

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

Структура ветвление существует в четырех основных вариантах:

• если—то;
• если—то—иначе;
• выбор;
• выбор—иначе.

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

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

Алгоритмический язык	Блок-схема
1. если—то
если условие то действия все
2. если—то—иначе
если условие то действия 1 иначе действия 2 все
3. выбор
выбор при условие 1: действия 1 при условие 2: действия 2............ при условие N: действия N все
4. выбор—иначе
выбор при условие 1: действия 1 при условие 2: действия 2............ при условие N: действия N иначедействия N+1 все

Примеры структуры ветвление

Язык программирования Pascal	Язык блок-схем
if x > 0 then y:= sin(x)
if a > b then begin a:= 2*a; b:= 1 end else b:= 2*b
Case n of n = 1: y:= sin(x); n = 2: y:= cos(x); n = 3: y:= 0;end;
Case a of a > 5: i:= i+1; a = 0: j:= j+1 else begin i:= 10; j:=0 end end;

3. Конструкция цикла

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

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

а) Цикл с предусловием (цикл «пока»).

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

Алгоритмический язык	Блок-схема
нц пока условие тело цикла (последовательность действий) кц

б) Цикл с постусловием.

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

Алгоритмический язык	Блок-схема
нц повторять тело цикла кц доусловия

в) Цикл с параметром

i1 и i2 - начальное и конечное значения параметра цикла.

С - приращение значения параметра цикла (может быть положительное, отрицательное, целое, дробное).

Работа цикла сводится к следующему: параметру цикла i присваивается начальное значение i1, выполняется тело цикла; i присваивается значение i1+С и если значение i2 не превышено, то выполняется тело цикла и т.д., до i = i2. После выполнения тела цикла для i = i2 работа конструкции заканчивается. Эту конструкцию следует использовать тогда, когда известно количество повторений тела цикла. Параметр i может исполнять 2 функции:

- функцию счетчика;

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

Алгоритмический язык	Блок-схема
нц для i от i1до i2 тело цикла (последовательность действий) кц

Примеры конструкции цикл

Язык программирования Pascal	Блок-схемы
Whilei <= 5 do begin S:= S+A[i] i:= i+1 end;end;
Fori:=1 to 5 do begin X[i]:= i*i*i; Y[i]:= X[i]/2 end; end;

Например, решение задачи о нахождении произведения чисел от 1 до n может иметь следующий вид.