Глава 8. Начала алгоритмизации 419

схемы, представленной на рис. 8.15. Хотя это и не всег­да возможно, но к этому нужно стремиться.

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

8.3.2. Составление

разветвляющихся алгоритмов

Составление таких алгоритмов выполняется в соот­ветствии с «Основными принципами алгоритмизации», здесь работает та же схема:

«формулировка задачи — метод — алгоритм».

Рассмотрим несколько классов задач, решение кото­рых требует составления разветвляющихся алгоритмов.

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

Задача 8.8. Вычислить значение Y по одной из фор­мул:

Х+а, если Х<10; (1)

У _щ Х-Ь₁₇ если 10<ХГ<20; (2)

с+Ь₂, если 20<Х<30; (3)

с-Ь₃, если 3(КХ, (4)

гдеХ=з/а + &₁ .

Глава 8. Начала алгоритмизации 427

Пример 1. Дана система координат на плоскости. Ус­ловие — точка М(х, у) лежит в первой четверти — явля­ется составным и может быть записано в таком виде:

х>0 и у>0.

Пример 2. Условие — точка R (х, у) лежит на одной из осей координат — является составным и может быть записано так:

х=0 или у=0.

Реализация логических выражений (составных условий). Возможны два подхода к составлению алгоритмов задач, содержащих составные условия:

1. Составное условие рассматривается как «единое и не­делимое» и в схеме изображается одним логическим блоком. Такой подход допустим, если в языке про­граммирования, на который мы ориентируемся, состав­ные условия разрешены.

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

Подобная схема имеет два выхода {Да и Нет) и обес­печивает «передачу управления» (так принято говорить) на один выход, если составное условие выполняется, и на другой, если оно не выполняется.

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

Далее будем ориентироваться на такие версии Бейси­ка, в которых "составные условия допустимы, и будем использовать первый подход, но для начала рассмотрим Решения задач 8.13 и 8.14 с использованием второго подхода, что должно помочь читателю «прочувствовать» смысл условий «А и В», «А или В».

434 Основы информатики

Глава 8. Начала алгоритмизации

435

Здесь значения X будут восприниматься как элемен­ты массива, так как переменная X — с индексом. Чтобы избежать этого, выражение (8.2) записывают в алгорит­ме так:

Х:=Х+3.

В общем случае при последовательном использова­нии значений переменной любое выражение вида X_i+l=f(x_t) можно преобразовать в алгоритме в такое:

X:=f_(X).

ЗдесьX — простая переменная. При этом символ «X», стоящий справа от знака «: = », означает предшествую­щее, а тот же символ слева от знака «:=» — последую­щее значение переменной X. В этом случае для перемен­ной X выделяется в ЭВМ только одна ячейка, и все зна­чениях последовательно помещаются в нее, причем каж­дое новое значение будет стирать предшествующее:

X: =Х+3

²⁽*тУ

1 I <— Ячейка для X

При этом должно быть задано начальное значение переменной, а также либо конечное ее значение, либо число ее значений.

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

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

Теперь уточним термин «исхоДные данные». С уче­том сказанного в этом параграфе будем четко различать два понятия: • данные задачи -— все величины, необходимые для ре­шения задачи, указанные в ее формулировке;

• исходные данные для'алгоритма (программы) — ве­личины, значения которых должны быть заданы пе­речислением их. В дальнейшем ради краткости тер­мин «исходные данные» будем использовать именно в этом смысле.

Так, в задаче: «вычислить произведение целых чет­ных чисел от М до JV» данными задачи будут числа М, М+2> М+4, ..., N. Однако в список исходных данных для алгоритма (программы) следует включать лишь М и JV, так как все прочие значения можно вычислить, зная М и N, в процессе решения задачи.

В частном случае данные задачи и данные для алго­ритма могут совпадать.

Понятие циклического алгоритма. Проиллюстрируем это понятие конкретным примером.

Задача 8.16. Вычислить значения функции Y=X³+BX--С при Х=2, 4, 6.

Решение. В соответствии с изложенным выше все значения X можно вычислить по формуле

Х:=Х+2, возложив эту обязанность на ЭВМ.

В таком случае исходными данными будут только величины* В л С. Решая задачу, получим три значения величины У, выдаваемые последовательно.

Порядок решения задачи можно описать следующим линейным алгоритмом:

1.Х:=2. 7. Х:=Х+2.

2. Y—X4BX-C. 8.Y: =Х³+ВХ-С.

3. Вывод Y. 9. Вывод Y.

4. Х:=Х+2. 10. Х:=Х+2.

5. У:=Х³+ВХ-С. 11. Останов.

6. Вывод Y.

Однако эта запись весьма громоздка, а если предста­вить, что X изменяется до 2 000 (или до 20 000!), то и вообще окажется неприемлемой (описать 1 000 (или Ю 000) этапов!).

* Здесь данными задачи являются величины X, В, С, но ис­ходными данными для алгоритма будут лишь В, С.

438 Основы информатики

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

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

Так, в задаче 8.16 рабочая формула

Y:=X^a+BX-C. Закон изменения аргумента Х:=Х+2.

Как видно из схем рис. 8.28, а, б, выполнение цик­лического алгоритма распадается на этапы — их назы­вают циклами, на каждом из которых выполняются опе­рации блоков 2, 3, 4, т.е. на каждом цикле вычисляются новые значения аргументов (в блоке 4) и соответствую­щие им новые значения результатов рабочих операций (в блоке 2) (результатов промежуточных или окончатель­ных).

В этом суть циклического алгоритма!

Блоки 1 и 3 (рис. 8.28, а) обычно задают диапазон изменения аргументов. Так, в задаче 8.16 подобные бло­ки обеспечивают изменение X от 3 до 6.

Блок 1 присваивает всем аргументам начальные зна­чения, обеспечивая тем самым выполнение рабочих опе­раций на первом цикле.

В блоке 3 проверяется условие окончания (повторе­ния) цикла, чаще всего предполагающее сравнение теку-