Материал: Информатика. Неформальное программирование и основы алгоритмизации вычислительных процессов. Кононов А.Д., Кононов А.А

будет иметь следующий вид:

Этап 1. Если x>0, то перейти к этапу 2, иначе перейти к этапу 3. Этап 2. Положить y = x . Перейти к этапу 4.

Этап 3. Положить y = 2x . Перейти к этапу 4.

Этап 4. Принять значение y за искомый результат и прекратить процесс вычисления.

Пример 4. В этом примере формульно-словесный способ записи алгоритма Евклида нахождения D=НОД(N,M) двух конечных положительных чисел N и M (N>M) может быть записан в виде:

1) разделим N на M, получим остаток N=Mq1+R1,

если R1=0, то конец: D=M, иначе 2) разделим M на R1

M=R1q2+R2,

если R2=0, то конец: D= R1, иначе 3) разделим R1 на R2

R1=R2q3+R3 и т.д.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

к) разделим Rk-2 на Rk-1

Rk-2=Rk-1qk+0 и тогда D=Rk-1.

Здесь qi – частные, а Ri – остатки на каждом i-ом этапе деления. Остатки – целые положительные числа, они уменьшаются до значения, равного нулю на каком-то k-ом этапе. Это описание алгоритма Евклида понятно человеку, но недоступно ЭВМ, так как содержит «и т. д.».

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

1) Возьмем в качестве Делимого N, в качестве Делителя M

10

2)Разделим Делимое на Делитель, получим Остаток

3)Если Остаток равен нулю, то конец: перейдем к пункту 4, иначе возьмем в качестве Делимого Делитель, в качестве Делителя Остаток, перейдем к пункту 2

4)Результат – последний Делитель.

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

Впроцессе выполнения алгоритма под словами Делимое, Делитель, Остаток понимаются числа, которые на разных этапах меняют свои значения.

Переменная – это ячейка памяти вычислителя вместе с ее содержимым, которое называется значением переменной. Действия, которые записаны в тексте программы как действия над переменными, фактически выполняются над их значениями.

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

Теперь алгоритм Евклида может быть записан в виде:

1)Ввод (Делимое, Делитель)

2)Остаток := МОD (Делимое, Делитель)

3)Если Остаток = 0 то перейти к п.4,

иначе { Делимое := Делитель,

4)Вывод (Делитель).

Впоследней форме алгоритма Евклида использованы обозначе-

ния:

:= операция присваивания; MOD (A,B) – операция вычисления целочисленного остатка от деления А на В.

Вновь переходя к словесно-формульному способу описания алгоритма, заменим слово Делимое на буквенное обозначение N, Делитель на M, Остаток на R. Тогда получим:

1)Ввод (N,M)

2)R := MOD (N,M)

3)Если R = 0, то перейти к п.4, иначе { N:=M, M := R, перейти к п. 2 }

11

4) Вывод (М).

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

ных затруднений, являются блок - схемы.

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

–блок, определяющий начало, конец или прерывание процесса вычисления;

– блок ввода-вывода информации;

– блок вычислений;

– блок проверки выполнения условия (логический блок);

– блок цикла (модификация);

12

– вычисление по подпрограмме, стандартной программе;

– печать результатов на бумаге;

– линии потока, изображают последовательность связей между блоками;

– соединители, указывают связи между прерванными линиями потока, связывающими блоки;

---– пояснения, содержание подпрограмм, формулы.

Рассмотренный выше алгоритм Евклида может быть представлен в виде блок-схемы на рис. 1.

Правила построения алгоритмов на языке блок-схем:

1.Блок-схема строится сверху вниз.

2.В любой блок-схеме имеется один элемент, соответствующий началу, и один элемент, соответствующий концу.

3.Должен быть хотя бы один путь из начала блок-схемы к любому элементу.

4.Должен быть хотя бы один путь от каждого элемента алгоритма в конец блок-схемы.

Описание на алгоритмическом языке. Алгоритм можно рассматривать как задание для исполнителя, который получит правильный результат, если точно выполнит то, что в нем написано. Человек, автоматическое устройство, компьютер – это разные исполнители. Для того, чтобы компьютер мог выполнить алгоритм, он должен быть написан на понятном ему языке. Компьютер понимает машинный язык. Человеку трудно писать и читать алгоритмы на машинном языке, ему понятен естественный язык. Но научить компьютер понимать естественный язык затруднительно потому, что в естественном языке слишком много слов и нет строгих правил записи предложений.

13

начало

N,M

R:=MOD(N,M)

Да

R = 0

Нет

N:=M M:=R

M

Конец

Рис. 1. Блок-схема алгоритма Евклида

Для того чтобы человек и компьютер понимали друг друга, разработаны специальные языки для записей алгоритмов – алгоритмические языки. Алгоритмический язык отличается от машинного тем, что состоит из слов и символов, как естественный язык, но в нем мало слов (обычно 30–40) и очень строгие правила составления предложений. Основные слова языка называют служебными словами. В алгоритмических языках используют слова английского алфавита. Алгоритмический язык легко понимают и человек, и компьютер. Алгоритм, записанный на алгоритмическом языке, – это программа для компьютера. Каждое предложение в программе – оператор.

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

14