Информатика и программирование - Основы информатики (926517), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

3. q = x₁x₂.

4. Вывести p, q.

Конец. □

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

Пример 9.41. Составим алгоритм определения максимального числа из трех чисел: z = max (a, b, c).

Решение задачи на ЭВМ можно получить, действуя следующим образом. Сначала найдем наибольшее из двух чисел, например, сравнив между собой a и b. Предположим, что исполнитель может выполнить операцию сравнения «больше». Найденное наибольшее число "запомним" в качестве значения переменной z. Далее сравним значение переменной z с оставшимся числом c. Если с больше z, то присвоим z новое значение – значение с, в противном случае, значение z останется прежним. В результате переменная z будет равна наибольшему из a, b, c и будет являться искомым результатом.

Изложенные рассуждения можно представить в виде следующей словесной записи алгоритма:

Начало.

1. Ввести a, b, c.

2. Если a > b, то z := a,

иначе z := b.

3. Если c > z, то z := c.

4. Вывести z

Конец.

Ход выполнения алгоритма зависит от результатов проверки условий а > b и c > z. Если для введенных значений a, b действительно a > b, то выполняется операция z := a; если нет, то выполняется z := b. Таким образом, в зависимости от результата проверки условия a > b требуется выполнить различные действия. В алгоритме на этом шаге предусмотрены оба возможных направления дальнейших вычислений. При проверке условия c > z операция z := c может выполняться, если действительно c > z, или не выполняться, в противном случае. □

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

Пример 9.42. Составим алгоритм определения остатка от деления двух целых неотрицательных чисел А и В, где В  0. Рассматривая деление как многократное вычитание делителя В из делимого А, получим алгоритм, состоящий из следующих шагов:

Начало.

1. Ввести A, B.

2. Если A < B, то перейти к шагу 5,

иначе перейти к шагу 3.

3. A := A – B.

4. Перейти к шагу 2.

5. ОСТ := A.

6. Вывести ОСТ.

Конец.

Шаги 2, 3, 4 записаны в алгоритме один раз, а могут выполняться многократно. Многократно повторяемые участки вычислений образуют так называемый цикл. Вычислительный процесс, содержащий многократные вычисления по одним и тем же математическим зависимостям, но для различных значений входящих в них переменных, называется циклическим. Переменные, изменяющиеся в цикле, называются переменными цикла, а действия, повторяемые в цикле, – телом цикла. Количество повторений цикла определяется значениями переменных, входящих в условие его окончания.

Чтобы лучше понять характер циклических процессов, рассмотрим подробнее структуру приведенного алгоритма. Первый шаг алгоритма представляет собой подготовку цикла: задание начальных значений переменным цикла перед первым его выполнением. Тело цикла – действия, многократно повторяемые в цикле (шаги 2, 3, 4). В каждом конкретном случае число повторений этих действий будет различным. Шаг 3 обеспечивает модификацию (изменение) значений переменной цикла А, входящей в условие его окончания. Управление циклом осуществляется на шаге 2. Проверяется условие окончание цикла (А < В), и осуществляется, либо выход из цикла, либо возврат на его повторение. Очень важно правильно сформулировать условие окончания цикла.

Поняв сущность и структуру циклических алгоритмов, можно записать алгоритм более компактно:

Начало.

1. Ввести A, B.

2. Пока A  B, выполнять A := A – B.

3. ОСТ := A.

4. Вывести ОСТ.

Конец.

Предписание «Пока А  В выполнять А := А  В» надо понимать следующим образом: если А больше или равно В, то выполнить операцию А := A  В и перейти опять на проверку условия А  В; если А меньше В, то перейти к выполнению следующего предписания (шаг 3), не выполняя операцию А := A  В. □

9.4.2.Схемы алгоритмов

Схема алгоритма – это графический способ его представления с элементами словесной записи. Каждое предписание алгоритма изображается с помощью плоской геометрической фигуры – блока. Отсюда название: блок-схема. Переходы от предписания к предписанию изображаются линиями связи – линиями потоков информации, а направление переходов – стрелками. Различным по типу выполняемых действий блокам соответствуют различные геометрические фигуры. Приняты определенные стандарты графических изображений блоков (табл. 9 .18).

Таблица 9.18. Изображение блоков в схемах алгоритмов

Наименование символа	Обозначение и размеры	Функция
Процесс (вычислительный блок)		Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположение данных
Решение (логический блок)		Выбор направления выполнения алгоритма в зависимости от некоторых условий
Модификация (заголовок цикла)		Выполнение операций по управлению циклом – повторением команды или группы команд алгоритма
Пуск-останов (начало-конец)		Начало или конец выполнения программы или подпрограммы
Предопределенный процесс (вызов подпрограммы)		Вызов и использование ранее созданных и отдельно описанных алгоритмов (подпрограмм)
Ввод-вывод		Общее обозначение ввода или вывода данных в алгоритме безотносительно к внешнему устройству
Соединитель		Указание прерванной связи между блокам в пределах одной страницы
Межстраничный соединитель		Указание прерванной связи между блоками, расположенными на разных листах

Рассмотрим общие правила построения схем алгоритмов.

1. Для конкретизации содержания блока и уточнения выполняемого действия внутри блока помещаются краткие пояснения – словесные записи с элементами общепринятой математической символики (Рис. 9 .21, а).

2. Основное направление потока информации в схемах может не отмечаться стрелками. Основное направление – сверху вниз и слева направо. Если очередность выполнения блоков не соответствует этому направлению, то возможно применение стрелок (Рис. 9 .21, б).

Рис. 9.21. Примеры изображения элементов схем алгоритмов

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

4. Допускается разрывать линии потока информации, размещая на обоих концах разрыва специальный символ «соединитель» (Рис. 9 .21, в, г). В пределах одной страницы используется символ обычного соединителя, во внутреннем поле которого помещается маркировка разрыва либо отдельной буквой, либо буквенно-цифровой координатой блока, к которому подходит линия потока. Если схема располагается на нескольких листах, переход линий потока с одного листа на другой обозначается с помощью символа «межстраничный соединитель». При этом на листе с блоком-источником соединитель содержит номер листа и координаты блока-приемника, а на листе с блоком-приемником – номер листа и координаты блока-источника.

5. Нумерация блоков осуществляется либо в левом верхнем углу блока в разрыве его контура, либо рядом слева от блока (Рис. 9 .21, а). Принцип нумерации может быть различным, наиболее простой – сквозная нумерация. Блоки начала и конца не нумеруются.

6. Для блоков приняты следующие размеры: а = 10, 15, 20 мм; b = 1,5а. Если необходимо увеличить размер блока, то допускается увеличение на число, кратное пяти. Необходимо выдерживать минимальное расстояние 3 мм между параллельными линиями потоков и 5 мм между остальными символами.

С помощью блок-схем можно изображать самые различные алгоритмы, например, линейной (Рис. 9 .22), разветвляющейся (Рис. 9 .23) и циклической структур (Рис. 9 .24).

Рис. 9.22. Алгоритм вычисления коэффициентов
приведенного квадратного уравнения

Пример 9.43. Рассмотрим задачу определения наибольшего общего делителя (НОД) двух целых положительных чисел M, N.

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

Рис. 9.23. Алгоритм выбора максимального числа из трех заданных чисел	Рис. 9.24. Алгоритм определения остатка от деления двух целых неотрицательных чисел

Сформулируем алгоритм Евклида несколько иначе, рассматривая деление как многократное вычитание:

1. Если числа равны между собой, то взять в качестве НОД любое из них.

2. Если числа не равны между собой, то большее из чисел заменить их разностью и вернуться к шагу 1.

Алгоритм Евклида может быть представлен следующей словесной записью:

Начало.

1. Ввести М, N.

2. Пока МN выполнять:

Если M > N, то M := MN;

иначе N := NM.

Характеристики

Список файлов книги