ПРОГРАММИРОВАНИЕ РАЗВЕТВЛЯЮЩИХСЯ АЛГОРИТМОВ

⇐ ПредыдущаяСтр 3 из 7Следующая ⇒

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

Составной и пустой операторы

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

Любая группа операторов, размещенных между словами BEGIN и END (иначе, операторные скобки), рассматривается как один – составной оператор. При выполнении составного оператора все его компоненты (операторы) выполняются в порядке их написания (линейно).

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

Наряду с понятием «составной оператор» в языке существует специфическое понятие «пустой оператор». Пустой оператор – это оператор, который не предусматривает выполнения никаких действий. Зачем он нужен? Действительно, если оператор не выполняет никаких действий, то стоит ли его писать? Однако практика показывает, что иногда полезно иметь такое средство, например, при выполнении искусственной задержки выполнения программы:

FOR I: = 1 TO 10 000 DO;

При выполнении данного оператора машина переменной I последовательно присвоит значения от 1 до 10 000. В теле цикла нет операторов, значит, кроме увеличения значений переменной на 1 ничего не будет выполнено, однако время на это затрачивается, и, следовательно, некоторое время программа «висит» на данном операторе.

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

Организация ветвлений. Операторы выбора

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

2.2.1. Оператор ветвления IF

Оператор IF можно представить в общей форме записи как

IF < Условие> THEN < Оператор 1> ELSE < Оператор 2>,

где конструкция «Условие» есть логическое выражение, которое принимает два значения типа BOOLEAN: TRUE, FALSE (истинно или ложно).

Само логическое выражение складывается из операций сравнения: >, > =, <, < =, =, < >. Результат сравнения может быть TRUE или FALSE.

Логические выражения могут формироваться также и с помощью трех логических операций: NOT, AND, OR. Приоритеты всех используемых в Паскале операций таковы:

Высший: ( )

NOT *, /, DIV, MOD

AND

OR +, -

Низший: >, =, < , > =, < >, < =

В качестве условия может быть использована и логическая переменная, например:

I and J or K ---> (I and J) or K;

not X and Y ---> (not X) and Y, где I, J, K, X, Y – переменные типа BOOLEAN;

(A < B) or (B = 0), где A, B – переменные простого типа.

В операторе IF всегда за словами THEN и ELSE должен следовать один оператор. Этим оператором может быть не только оператор присваивания, но и любой другой. Если хотя бы один из них является снова оператором IF, то полученную конструкцию называют вложением.

П р и м е р:

IF < условие1> THEN < ветвь 1>

ELSE IF < условие2> THEN < ветвь 2>

ELSE < ветвь 3>;

Такое вложение используется для уменьшения числа необходимых проверок. Этот метод часто обеспечивает большую эффективность, чем составное условие, однако одновременно он уменьшает надежность программы. Не рекомендуется использовать более двух-трех уровней вложения IF. Вложения могут идти и после слова THEN.

Первый способ предпочтительнее, чем второй, так как конструкция THEN-IF менее удобна, чем ELSE-IF. С помощью конструкции ELSE-IF чаще всего осуществляется выбор одного из нескольких альтернативных вариантов. Заметим, однако, что иногда такое вложение можно заменить на последовательность операторов короткой формы IF-THEN. Это видно на следующем примере:

program QUARD;

var A, B, C: real; D: real;

begin

read (A, B, C); D: = sqr (B) – 4 * A - C;

1-й вариант	2-й вариант
if D < 0 then write ('Не имеет корней');	if D < 0 then write ('Нет корней') else if D = 0 then write ('Один корень')
if D = 0 then write ('Один корень'); if D > 0 then write ('Два корня');	else write ('Два корня');

end.

Рис. 2. Пример программы двух разных вложений

Однако в данном примере 2-й вариант более эффективен, так как имеет на одно сравнение меньше, и в случае D < 0 сразу же дает ответ, не делая последующих проверок.

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

2.2.2. Оператор варианта CASE

Оператор варианта состоит из выражения и списка операторов, каждому из которых предшествует одна или более констант, называемых константами выбора.

Общая форма записи

CASE < выражение> OF

константы: оператор;

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

константы: оператор

ELSE < оператор>

END;

Выражение, стоящее между CASE и OF, называется селектором. Константы (значения выражения), предшествующие двоеточию, называются метками случаев. Порядок работы оператора: сначала вычисляется значение селектора, затем выполняется оператор, одна из меток которого совпадает со значением селектора. Все остальные операторы не выполняются, и управление передается следующему после END оператору. В случае короткой формы оператора CASE при несовпадении значения селектора (ключа) ни с одной из констант из списка никакой оператор не подлежит исполнению. Если же в операторе есть строка ELSE, то при несовпадении значения селектора ни с одной константой выполняется оператор, следующий за ELSE.

Выражение «селектор» может относиться к любому скалярному типу, кроме REAL. Метки случаев должны принадлежать тому же типу, что и селектор. Нежелательно, чтобы одна и та же метка появлялась более одного раза в операторе CASE. Если же это произойдет (компилятор не проверяет повторяемость меток), то выполнится тот оператор, который соответствует первому вхождению метки в список констант.

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

П р и м е р 1. Печать названия десятичных цифр.

program DICITS;

var DIGIT: integer;

begin

writeln ('Введите цифру');

readln (DIGIT);

case DIGIT of

0: writeln ('нуль');

1: writeln ('один');

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

9: writeln ('девять');

else writeln ('это не цифра');

end;

end.

П р и м е р 2. Печать номера квартала года.

program NUMKVART;

var MESIATZ: 1..12;

begin

write ('Введите номер месяца года – ');

read (MESIATZ);

case MESIATZ of

1, 2, 3: writeln ('Первый квартал');

4, 5, 6: writeln ('Второй квартал');

7, 8, 9: writeln ('Третий квартал');

10, 11, 12: writeln ('Четвертый квартал');

end;

end.

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

Лабораторная работа №2

Цель работы: научиться решать задачи на разветвляющиеся алгоритмы; научиться использовать в программах условный оператор if и оператор выбора case.

Общие сведения

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

Перед выполнением работы необходимо ознакомиться с правилами записи логических выражений, операций сравнения, операторов if, case.

Пример. Дано действительное x. Для функции f, график которой представлен на рисунке, вычислить f(x).

Решение задачи .

Математическая модель: функция вычисляется по следующей формуле:

Составим схему алгоритма, детализировав все блоки (рис. 2).

Дальнейшая детализация не требуется. Переводим алгоритм на язык Паскаль.

Program example1;

var x, f: Real;

begin

Write('Введите x: '); Readln(x);

if x< -1 then f: = - x-1 else

if (x> =-1) and (x< 0) then f: = x-1 else

if (x> =0) and (x< 1) then f: = - x+1 else f: = x+1;

Writeln('F= ', f: 6: 2);

Readln;

end.

Рис. 3. Блок-схема ветвления в 4-х направлениях

Варианты заданий

Задание 1. Используя оператор if, вычислить заданное выражение для данных типа Integer:

а) b)

c) d)

Задание 2. Найти алгоритм решения задачи и реализовать его с помощью оператора (операторов) if-then-else:

a) Составить программу, реализующую эпизод сказки: машина спрашивает, куда пойдет герой, и в зависимости от ответа (налево – (-1), прямо – 0, направо – 1), печатает, что произойдет с героем.

b) Морской бой. Машина задумывает два числа от 0 до 9. Игрок пытается их угадать, вводя свои два числа. Если они совпали (в любом сочетании), то игрок выиграл.

c) В Атлантическом океане терпит бедствие пассажирский теплоход «Посудина». Все пассажиры будут спасены, если на помощь успеют два судна. Судно продержится на плаву tчасов. Скорость судов-спасателей 40 узлов. Составить программу, определяющую спасутся ли пассажиры. Известны расстояния от трех судов-спасателей до тонущего судна.

d) Через старый мост движется поток автомашин. Одновременно на мосту могут находиться 3 машины. Если на мост въедут 3 легковых или 2 легковых и грузовик – мост выдержит. Если 2 грузовика и легковая или 3 грузовика – рухнет.

Задание 3. Используя оператор выбора, составить программы решения следующих задач.

a) По номеру дня недели вывести на печать рабочий это день или выходной, считая выходными субботу и воскресенье.

b) По номеру месяца указать, к какому времени года он относится.

c) По номеру месяца вывести на печать количество дней в нем.

d) Единицы массы пронумерованы следующим образом: 1 — килограмм, 2 — миллиграмм, 3 — грамм, 4 — тонна. Дан номер единицы массы и масса тела M в этих единицах (M - вещественное число). Вывести массу данного тела в килограммах.

Дополнительные задания

1. Даны действительные числа a, b, c, x, y. Выяснить, пройдет ли кирпич с ребрами a, b, c в прямоугольное отверстие со сторонами x и y. Просовывать кирпич в отверстие разрешается только так, чтобы каждое из его ребер было параллельно или перпендикулярно каждой из сторон отверстия.

2. Сможет ли шар радиуса R пройти в ромбообразное отверстие со стороной P и острым углом Q?

Контрольные вопросы

1. Какие операторы используются для программирования развилок?

2. Как выполняются операторы условного перехода?

3. Какую из функций: Sin(x), Abs(x), Trunc(x) можно заменить условным оператором if x< 0 then x: = - x?

4. Если выбор вариантов осуществляется из конечного числа элементов выбора, то лучше взять для этого оператор if или case?

5. Как заменить оператор case операторами if?

6. В чем преимущество оператора case от последовательности «коротких» операторов if?

7. Какой тип переменной можно использовать в качестве ключа оператора case?

ОРГАНИЗАЦИЯ ЦИКЛОВ

Оператор цикла задает повторное выполнение определенных операторов. Для реализации циклов в Паскале предусмотрены три различных структурных оператора: WHILE, REPEAT, FOR. Первые два используются, если число повторений (итераций) заранее не определено, но известно условие завершения цикла. Оператор FOR применяется тогда, когда число повторений тела цикла известно заранее.

Оператор WHILE

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

WHILE < Условие> DO < Тело цикла>;

Логическое выражение, стоящее после WHILE, называется условием возобновления цикла и должно иметь булевский тип. Оператор, следующий за DO, является телом цикла. Он повторяется до тех пор, пока истинно условие возобновления цикла. Как только условие возобновления цикла становится ложным, управление переходит к оператору, стоящему за WHILE. Если условие возобновления не удовлетворяется до начала выполнения цикла, то тело цикла пропускается.

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

П р и м е р. Даны числа A, B (A > 1). Получить все степени числа A, меньшие числа B.

program STEPENI;

var A, B, C: real;

begin

readln (A, B); C: = A;

while C < B do

begin

writeln (C);

C: = C*A;

end;

end.

Примечание. Грамотное использование оператора WHILE предполагает умение правильно написать условие возобновления цикла. Здесь надо иметь в виду следующие рекомендации:

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

2. Во избежание зацикливания лучше сначала написать условие прекращения цикла и взять потом в операторе его отрицание.

3. Переменные логического выражения должны получить свои исходные значения до входа в оператор WHILE.

Оператор REPEAT

Оператор REPEAT называют оператором цикла с постусловием, так как здесь выражение, управляющее повторным выполнением последовательности операторов, помещается после тела цикла:

REPEAT < Тело цикла> UNTIL < Условие>;

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

В этом операторе тело цикла выполняется до тех пор, пока ложно условие, стоящее после UNTIL. Условием выхода из цикла является истинность выражения. Мы видим, что это есть форма «цикла-до».

П р и м е р. Даны числа A, B (A > 1). Получить все степени числа A, меньшие числа B.

program STEPENI;

var A, B, C: real;

begin

readln (A, B); C: = A;

repeat

writeln (C);

C: = C*A;

until C > = B;

end.

Примечание. Между операторами WHILE и REPEAT существует три основных различия:

1. В операторе REPEAT проверка условия выхода из цикла выполняется в конце, а не в начале цикла, как в операторе WHILE, поэтому в операторе REPEAT тело цикла выполняется хотя бы один раз.

2. В REPEAT выход из цикла осуществляется по истинности условия, а в WHILE – по ложности.

3. В операторе WHILE тело цикла чаще всего имеет форму составного оператора, в операторе REPEAT для организации тела цикла операторные скобки не нужны.

Оператор FOR

Оператор FOR предназначен для организации циклов, когда заранее известно, сколько раз должно повториться тело цикла. Здесь управление числом повторений осуществляется с помощью специальной переменной – параметра цикла (управляющей переменной), которой присваивается возрастающая (убывающая) последовательность значений. Оператор FOR имеет следующий вид:

FOR < Переменная>: = < Выражение 1> TO < Выражение 2> DO;

FOR< Переменная>: =< Выражение1> DOWNTO< Выражение1> DO;

Здесь «Переменная» есть параметр цикла, «Выражение 1» – начальное значение параметра, «Выражение 2» – его конечное значение. В качестве управляющей переменной должна быть переменная, объявленная локальной в блоке, который содержит данный оператор FOR. Управляющая переменная должна иметь ординальный тип. Начальное и конечное значения имеют тип, совместимый с типом параметра цикла.

Когда начинает выполняться оператор FOR, начальное и конечное значения определяются один раз, и эти значения сохраняются на протяжении всего выполнения оператора.

Оператор, который содержится в теле цикла, выполняется один раз для каждого значения управляющей переменной в диапазоне между начальным и конечным значениями. Управляющая переменная всегда инициализируется начальным значением. Она принимает все свои значения из диапазона с шагом 1, если TO, и с шагом -1, если DOWNTO.

В случае TO, если начальное значение превышает конечное, тело цикла не выполняется.

Для случая DOWNTO это имеет место, когда начальное значение меньше, чем конечное. Отсюда заключаем, что оператор цикла FOR реализует, как и WHILE, схему цикла «пока» – проверка условия повторения цикла идет до тела цикла.

Примечание.

1. Если тело цикла в этом операторе состоит из более одного оператора, то они все заключаются в операторные скобки (реализуют конструкцию составного оператора).

2. В отличие от школьного алгоритмического языка, оператор FOR нельзя прервать путем присваивания управляющей переменной ее конечного значения. Изменения переменной цикла не влияют на число повторений тела цикла.

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

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

П р и м е р 1. Печать отсчета цифр при старте.

program START;

var SEC: integer;

begin

writeln ('До старта осталось...');

for SEC: = 10 downto 1 do

writeln (SEC: 4);

writeln ('ноль'); writeln ('Старт!! ')

end.

В данном примере управляющая переменная SEC принимает значения типа INTEGER, однако в Паскале она определена как переменная ординального типа и, следовательно, может принимать значения типа CHAR или принадлежать перечислимому типу, как показано в примере 2.

П р и м е р 2. Подсчет числа часов рабочей недели.

program WORKTIME;

type DAYS = (MO, TU, WE, TH, FR, SA, SU);

var DEN: DAYS; WT: integer;

begin

WT: = 0;

for DEN: = MO to SA do

if DEN < > SA then WT: = WT + 8

else WT: = WT + 7; writeln (WT);

end.

Лабораторная работа № 3

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

Общие сведения

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

Перед выполнением работы необходимо изучить различные схемы организации циклов и операторы for, while, repeat.

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

Пример: На промежутке от 1 до M найти все числа Армстронга. Натуральное число из n цифр называется числом Армстронга, если сумма его цифр, возведенных в степень n, равна самому числу. Например, число 153 (153=13+53+33).

Решение. После организации ввода данных программа будет содержать цикл с параметром i (от 1 до М) с двумя вложенными циклами. Первый предназначен для подсчета количества цифр n, второй – для вычисления суммы s степеней цифр числа i. Если числа i и s равны, то i – число Армстронга, его необходимо вывести на экран.

PROGRAM Primer_1;

var i, k, s, p, n, M: Integer;

begin

Write('Введите M '); Readln(M);

for i: =1 to M do

begin

s: =0; k: =i; n: =0;

while k< > 0 do

begin k: =k div 10; n: =n+1 end;

k: =i;

While k< > 0 do

begin p: =k mod 10; k: =k div 10;

if p< > 0 then s: =s+ Round(Exp(n*Ln(p)))

end;

if s=i then Writeln(i);

end;

Readln;

end.

Варианты заданий

Задание 1. Целочисленная арифметика.

Найти количество натуральных двузначных чисел, каждое из которых делится на 3 и на 13.

a) Найти количество натуральных четырехзначных чисел, каждое из которых не делится ни на 2, ни на 3.

b) Найти количество натуральных чисел, не превосходящих 1000, каждое из которых кратно 25 и не кратно 3.

c) Найти те натуральные числа, не превосходящие x, которые при делении на 10 дают в остатке 5.

Задание 2. Найти алгоритм решения задачи и реализовать его в виде Паскаль-программы.

a) Начальный вклад в банк составляет а рублей. Через сколько лет он станет больше b рублей? Каждый год вклад увеличивается на 3%.

b) Ежегодный прирост рыбы в пруду составляет 15%. Запасы рыбы оценены в А тонн. Ежегодный план отлова В тонн. Подсчитать, сколько лет можно выдерживать заданный план?

c) Каждая бактерия делится на две в течение одной минуты. В начальный момент имеется A бактерий. Сколько времени потребуется, чтобы количество бактерий превзошло X?

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

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

a) Вычислить количество точек с целочисленными координатами, попадающими в круг радиуса R (R> 0) с центром в начале координат.

b) Найти все натуральные числа от 1 до N, представимые в виде суммы кубов двух натуральных чисел.

c) Найти все натуральные числа от 1 до N, представимые в виде суммы квадратов трех натуральных чисел.

d) Даны натуральные M, N (M< N). Найти числитель и знаменатель несократимой правильной дроби p/q такой, что p/q = m/n.

Контрольные вопросы

1. Как записывается и как работает оператор for?

2. Для организации каких циклов применим оператор for?

3. В чем отличие оператора while от оператора repeat?

4. Как программируются циклические алгоритмы с явно заданным числом повторений цикла?

5. Напишите пример оператора цикла, который не выполняется ни разу.

6. С какими ограничениями реализована конструкция цикла со счетчиком?

7. Замените оператор " repeat A until B" равносильным фрагментом программы с оператором while.

⇐ Предыдущая 1 234 5 6 7 Следующая ⇒