ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

Алгоритмическая структура ВЕТВЛЕНИЕ

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

Логические величины и выражения

Найдите ответ на вопрос, с чем связано название логического типа – Boolean. Допустимые операции для логического типа данных: операции сравнения… Арифметические выражения можно сравнивать между собой с помощью операций сравнения. Эти операции известны Вам из курса…

Условный оператор

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

При решении задач в системе ИнтАл Вы использовали две формы записи команды ветвления: сокращенную и полную. Аналогично обстоит дело в Паскале:

Неполная команда ветвления	Полная команда ветвления
IF P THEN S ;	IF P THEN S1 ELSE S2 ;
Рис.3.4.

Здесь P – условие разветвления (логическое выражение или выражение отношения), S, S1, S2 – выполняемые операторы.

* Условие Р бывает простым (если оно содержит единственное выражение сравнения) и составным (если оно составлено из нескольких выражений сравнения, соединенных логическими операциями). В составных условиях выражения сравнения заключаются в круглые скобки. Примеры простых выражений: a>b, 5+x=3, sqrt (x)<=25. Примеры сложных выражений:

(x+y=5) and (2*x*sin(x)<5.5) à

(x<y) or not (y<z) à

Порядок выполнения операторов приводится на рис. 3.4. Так, в неполной конструкции, если условие Р истинно, выполняется оператор S, а затем – оператор, следующий за оператором if.

Если по одной из ветвей после служебных слов THEN и(ли) ELSE требуется выполнение более одного оператора, их ограничивают операторными скобками BEGIN … END и рассматривают как составной оператор.

Примеры:

Запись на ИнтАле	Запись на Паскале
Если a>b То x:=a Иначе x:=b Конец_Если	IF a>b THEN x:=a ELSE x:=b ;
Если a>b То x:=a k:=1 Иначе x:=b k:=2 Конец_Если	IF a>b THEN BEGIN x:=a ; k:=1 END ELSE BEGIN x:=b ; k:=2 END ;
Если a>b То Если a>c То x:=a Конец_Если Конец_Если	IF a>b THEN IF a>c THEN x:=a ;
* IF (a>b) and (a>c) THEN x:=a ;

Примеры решения задач:

Пример 1. Моделирование работы пожарного датчика в помещении: программа должна выводить сообщение «Пожароопасная ситуация», если температура в комнате превысит 60° C; если температура не более 60° C, датчик «молчит».	Program OGON; Var T: Real; Begin Write ('T='); Readln (T); If T>60 then Writeln ('Пожароопасная ситуация') End.
Пример 2. Реализуем на Паскале полностью алгоритм решения задачи 1 (§ 9): «Определить, на какой высоте и на каком расстоянии от места броска окажется через время t (с) мяч, брошенный под углом α к горизонту с начальной скоростью υ0 (м/с)» (с учетом проверки корректности исходных данных). Напомним, что математическая постановка задачи и описание алгоритма ее решения приводятся в § 9, линейная часть алгоритма реализована на Паскале в § 15. Будем использовать неполную команду ветвления: если требуемые условия не выполняются, программа не совершает никаких действий. Можно предусмотреть вывод сообщения о некорректных данных: If (alfa>0) and (…) … then Begin … End Else Writeln ('Некорректные данные');	Program BROSOK ; Const g = 9.8 ; Var V0, t, alfa, x, y : Real ; Begin Write ('введите скорость ') ; Readln (V0) ; Write ('введите время ') ; Readln (t) ; Write ('введите угол ') ; Readln (alfa) ; alfa:=alfa*pi/180; If (alfa>0) and (alfa<=pi/2) and (V0>0) and (V0<=20) and (t>0) Then Begin x:=V0*cos(alfa)*t ; y:=V0*sin(alfa)*t-g*t*t/2 ; Writeln ('x=',x) ; Writeln (' y=',y) End ; End .
Пример 3. Требуется определить, является ли человек, возраст которого x задан, школьником. Задача сводится к проверке условия: 6 ≤ х ≤19 (сравните с решением примера 4 п. 19.1)	Program School_1; Var X : Byte ; Begin Write ('Возраст='); Readln (X) ; If X>=6 then if X<=19 then Writeln ('школьник') End .	Program School_2; Var X : Byte ; Begin Write ('Возраст='); Readln (X) ; If (X>=6) and (X<=19) then Writeln ('школьник') End .

* Пример 4. Требуется написать программу для решения неравенства ax > b (a, b – действительные числа).

Возможны следующие варианты ответа: 1) x>b/a (при a > 0); 2) x<b/a (при a < 0); 3) нет решений (при a = 0, b ≥ 0); 4) x – любое число (при a=0, b<0). Program Neravenstvo ; Var a, b : Real ; Begin Write ('a=') ; Readln (a) ; Write ('b=') ; Readln (b) ; If a>0 Then Writeln ('x>',b/a) Else If a<0 Then Writeln ('x<',b/a) Else If b>=0 Then Writeln ('нет решений') Else Writeln ('x-любое число') End .   If a >0 Then Writeln ('x>',b/a) ; If a <0 Then Writeln ('x<',b/a) ; If a=0 then If b>=0 Then Writeln ('нет решений') Else Writeln ('x-любое число')

* В случае вложенных ветвлений каждое новое ключевое слово Else следует считать относящимся к ближайшему неиспользованному If. Например,

If x>-5 Then If x<=6 Then y:=x*x Else y:=x*x*x Else y:=x ;

Этот фрагмент позволяет вычислить значение y по формуле:

1. Какие значения могут принимать переменные типа Boolean?

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

3. Что может быть операндом выражений сравнения? логических выражений?

4. Что такое «условный оператор» и когда он применяется?

5. Что может использоваться в качестве условия в условном операторе?

1. Определите, какие значения будут принимать переменные Х и Y после выполнения следующих операторов при:

1) A=5, B=3; 2) A=7, B=7; 3) A=-3, B=-10; 4) A=3, B=0; 5) A=5, B=2:

а) if A=B then X := A+1; Y:=B+1 ;	б) if A>B then X:=B+1 else Y:=A+1; X:=0;
в) if A=B then Begin X := A+1 ; Y := B+1 End ;	г) if A>B then Y:=A-1 else Begin X:=B-2; Y:=0 End ;
* д) if (A>B) and (A*B>0) then Begin X:=SQRT (A*B); Y:=100 End Else Begin X:=B-A; Y:=A*B End ;

2. Определите, какие значения будут иметь переменные a и b после выполнения условного оператора if a>=b then a:=b else b:=a;

если: 1) a=0.9; b=0.7; 2) a=-7.3; b=7.3; 3) b=17; a=17; 4) a=5; b=5;

* 3. Определите, какие из следующих операторов задают вычисления по формуле:

4. Напишите программы решения задач:

1) Найти лучший результат в забеге на 100 м трех спортсменов.

2) Участники забега на 100 м имеют номера 1, 2, 3. Найти номер победителя, если результаты забега известны.

3) Определить длительность звучания музыкальной композиции, если известно время начала и окончания звучания. На экран компьютера требуется вывести только значения времени (часов, минут, секунд), отличные от нуля (например, если время начала – 16 ч 57 м 30 с, а время окончания – 17 ч 14 м 30 с, то длительность звучания составит 17 м ).

4) Определить по номеру года, является ли он високосным (год високосный, если его номер делится на 4, кроме тех, которые делятся на 100 и не делятся на 400). Например, 1900 год – не високосный, 2000 год – високосный.

5) Для старшеклассника определены нормальные значения границ кровяного давления: верхняя – не более 100, нижняя – не менее 60 и разница верхней и нижней границ – не менее 30. Определить, является ли давление старшеклассника нормальным, если заданы значения нижней и верхней границ кровяного давления.

* 6) Используя метод Ленуара, определить название дня недели для некоторой даты, которая задается номерами года (g), месяца (m), дня (d):

вначале следует вычислить значение С = [365,25g] + [30,56m] + d +N, где N=1, если месяц – январь или февраль високосного года, N=2, если месяц – январь или февраль невисокосного года, N=0 для остальных месяцев;

затем нужно найти остаток от деления С на 7; если он равен 0, то в качестве ответа выведите «среда», 1 – «четверг», …, 6 – «вторник».

* 7) В финале конкурса «Лучший по профессии» приняли участие два конкурсанта: Петров и Сидоров. Финал предусматривает проведение трех конкурсов, по каждому из которых выставляется число баллов каждому участнику. Победитель должен быть определен по сумме баллов. С клавиатуры вводятся количество баллов, которое набрал каждый участник в каждом конкурсе. Требуется вывести наибольшую сумму баллов и фамилию победителя.

8) Найти решение уравнения ax=b.

9) Решить квадратное уравнение ax² +bx + c =0 (а ≠ 0).

* 10) Решить уравнение ax² +bx + c =0.

11) Заданы три действительных числа. Выяснить, могут ли они оказаться длинами сторон некоторого треугольника.

* 12) Получить решение системы уравнений:

* 13) На экскурсию в крепость-герой Брест отправляется N человек. Для их перевозки выделены автобусы вместимостью K и M человек. Определить, сколько необходимо автобусов для перевозки всех экскурсантов (не забудьте, что одно место в каждом автобусе занято гидом). Попытайтесь определить вариант с минимальным количеством автобусов.

* 14) При исследовании поверхности планеты Зета обнаружена популяция, развитие которой с момента ее возникновения подчиняется закону, описываемому следующим образом:

где k = 1, 2, 3, … (а_i – численность популяции в i-м году). По заданному номеру nгода найти численное значение популяции.

Оператор выбора CASE

Оператор CASE представляет собой частный случай структуры ВЕТВЛЕНИЕ, когда возникает необходимость выбора одного из нескольких возможных вариантов вычислений в зависимости от значений некоторого выражения (ключа, селектора).

Порядок выполнения оператора Case следующий: вычисляется значение выражения K; полученное значение сравнивается с K1, K2, …, KN; если оно совпадает с одним из этих значений, то управление передается соответствующему оператору и выполнение оператора CASE завершается. Если значение выражения K не совпадает ни с одним из возможных значений, далее все зависит от типа оператора CASE: если он полный (в нем присутствует служебное слово ELSE), то управление передается команде S; в противном случае выполнение оператора завершается.

Конструкция	ИнтАл	Паскаль
	Выбрать_По K K1: S1 K2: S2 . . . KN: SN Иначе S Конец_Выбора   K – переменная целого типа; K1, K2, …, KN – возможные значения переменной К; S1, S2, …, SN, S – выполняемые команды	CASE K OF K1 : S1 ; K2 : S2 ; . . . KN : SN ELSE S END ;   K – выражение, определяющее значение ключа; K1, K2, …, KN – возможные значения ключа; S1, S2, …, SN, S – выполняемые операторы (простые или составные)

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

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

В Паскале допускается использование нескольких возможных значений ключей, разделенных запятой (перечисление значений) или двумя точками “..” (диапазон значений).

Пример 1. По номеру дня недели требуется определить его название.

Program Day ;

Var Num : Byte ;

Begin

Writeln ('Введите номер дня недели') ;

If Num = 1 then Writeln ('Понедельник') Else if Num=2 then Writeln ('Вторник') Else if Num=3 then Writeln ('Среда') Else if Num=4 then Writeln ('Четверг') Else if Num=5 then Writeln ('Пятница') Else if Num=6 then Writeln ('Суббота') Else if Num=7 then Writeln ('Воскресенье') Else Writeln ('Это не номер дня …') ;

Readln (Num);

Case Num of

1: Writeln ('Понедельник') ;

2: Writeln ('Вторник') ;

3: Writeln ('Среда') ;

4: Writeln ('Четверг') ;

5: Writeln ('Пятница') ;

6: Writeln ('Суббота') ;

7: Writeln ('Воскресенье')

Else

Writeln ('Это не номер дня недели')

End;

End.

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

Дано: month, year – номера месяца и года.

Найти: kol_days – количество дней в этом месяце.

Связь:

year – високосный, если year делится без остатка на 4, кроме тех, которые делятся на 100 и не делятся на 400. Например, 1900 год – не високосный, 2000 год – високосный.

Будем считать, что данные корректны.

Program Days ;

Var Year : Integer ;

month, kol_days : Byte ;

Sto : Boolean;

Begin

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

Readln (month) ;

Case month of

1, 3, 5, 7, 8, 10, 12 : kol_days := 31 ;

4, 6, 9, 11 : kol_days := 30 ;

2 : Begin {февраль}

Write ('Введите номер года ') ;

Readln (Year) ;

Sto:=(Year mod 100)=0;

if ((Sto=True) and (Year mod 400 =0)) or

((Sto=False) and (Year mod 4=0)) Then

kol_days := 29

Else kol_days := 28

End;

End ;

Writeln (kol_days);

End .

Пример 3. Составить программу проверки, делится ли заданное натуральное число на 7.

Пусть х – заданное натуральное число. Составим выражение сравнения: x mod 7 =0. Используем это выражение в качестве селектора; его возможные значения: True, False. Ниже приводятся два варианта использования оператора выбора (в полной и неполной формах):

Program PRIM_3 ; Var x : LongInt ; Begin Write ('Введите натуральное число ') ; Readln (x) ;
Case x mod 7 = 0 of True : Writeln ('делится на 7') ; False : Writeln ('не делится на 7')	Case x mod 7 = 0 of True : Writeln ('делится на 7') Else Writeln ('не делится на 7')
End ; End .

1. Какова структура условного оператора? * оператора выбора?

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

1. Напишите программы решения следующих задач:

1) На экран компьютера выводится текст:

 

 

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

2) По номеру класса, в котором учится школьник, требуется определить, в школе какого типа он обучается (подготовительная, начальная, базовая, средняя).

3) На экран компьютера выводится текст:

 

 

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

4) Таблица К. Купера позволяет определить степень физической подготовленности человека в зависимости от суммы очков, набранных им на занятиях по физической культуре за неделю:

Сумма очков, набранных за неделю	Степень физической подготовленности
Юноша	Девушка
Не менее 75	Не менее 65	Превосходно
51-74	41-64	Отлично
32-50	27-40	Хорошо
21-31	16-26	Удовлетворительно
10-20	8-15	Плохо
Меньшее 10	Меньше 8	Очень плохо

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

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

6) В пятиэтажном доме на каждом этаже по 4 квартиры. Программа должна предложить ввести номер этажа и вывести номера квартир на этом этаже.

7) Программа предлагает ввести число k полных лет человека (от 1 до 120) и вывести фразу: «Вам k лет». Например, при k=3 – «Вам три года», k=18 – «Вам 18 лет», k=101 – «Вам 101 год».

8) Определить наиболее подходящий возраст партнера для вступления в брак. Программа должна запросить данные пользователя: возраст, признак пола (из выведенного на экран меню: 1 – юноша, 2 – девушка) и вывести подходящий возраст партнера, который вычисляется так: возраст девушки равен увеличенной на 7 половине возраста юноши, возраст юноши определяется как удвоенный возраст девушки минус 14.

9) Вывести в римской системе нумерации век, к которому относится заданный год (номер года вводится с клавиатуры).

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

11) Программа должна предложить ввести текущее время и вывести период суток (день, ночь, утро, вечер, обед).

Алгоритмическая структура ПОВТОРЕНИЕ

20.1. ПОКА – цикл с предусловием (WHILE)      

Смешанные алгоритмы

       

Алгоритмические структуры и графические построения

Графические построения

Рассматривая некоторое изображение в виде совокупности одноименных объектов (точек, отрезков и т.д.), можно прийти к пониманию возможности… Примеры программ: Пример 1. Получение изображения отрезка прямой. … Возможность выбора построения того или иного изображения, представленная в алгоритме (и соответственно, в программе) в…

Программирование движущихся объектов

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