Оператори розгалуження та складений

Майже кожний, хто провчився в школі років вісім, пам'ятає, як обчислювати дійсні корені квадратного рівняння ax² + bx + c =0 (природно, за умови a¹ 0):

(1) прочитати коефіцієнти a, b, c;

(2) обчислити d=b²-4ac;

(3) якщо d>0, то обчислити x1=(-b- )/(2a), x2=(-b+ )/(2a);

у противному випадку

якщо d=0, то обчислити x1=-b/(2a),

інакше нічого не робити.

Майже кожний розуміє, що він задає три різні послідовності дій. Яка саме виконується, залежить від конкретних значень a, b, c. Пункт (3) алгоритму задає перевірку, яка з умов d >0, d =0 або d> 0 справджується, і залежно від цього ті або інші дії.

Умову будемо розуміти як фразу, що може бути або істинною, або хибною. У мові Паскаль умову можна відтворити бульовим виразом, як правило, із змінними. Його значеннями можуть бути true або false – це залежить від значень змінних. Звичайно, умови можуть бути тотожно істинними або тотожно хибними – вони відтворюються виразами, швидше за все, без змінних. Втім, вирази z or not z і z and not z мають значення відповідно true і false незалежно від значення z.

Перевірка умови при виконанні програми – це обчислення відповідного бульового виразу.

Перевірка умов і виконання залежно від цього різних дій задається в мові Паскаль операторами розгалуження. Вони мають дві форми – повну та скорочену. Оператор розгалуження в повній формі має вигляд:

if умова then оператор else оператор

Ключові слова if, then, else – це англійські "якщо", "то", "інакше". Для полегшення читаності програми оператор розгалуження часто записують "східцями":

if умова

Then

оператор

Else

оператор

або

if умова then

оператор

else оператор

Виконання його полягає в тім, що спочатку обчислюється значення умови, записаної після слова if. Далі, якщо цим значенням є true, виконується оператор, записаний після слова then, і на цьому виконання закінчується. Але якщо це значення хибне, те виконується не перший, а другий оператор, записаний після else. Наприклад, при виконанні послідовності операторів

readln(x);

if x>=0 then z:= 1 else z:= -1

змінна z одержить значення 1, якщо прочитано невід'ємне значення x. Якщо ж прочитано значення від'ємне, то z одержить значення –1.

Оператор розгалуження в скороченій формі має вигляд:

if умова then оператор

Він відрізняється лише тим, що якщо обчислення умови дає значення false, то на цьому його виконання закінчується.

Як бачимо, оператори розгалуження містять умови, з обчислення яких і починається їх виконання. Тому ці оператори ще називаються умовними.

Застосуємо оператори розгалуження для перекладу алгоритму обчислення коренів на мову Паскаль. Пункт (3) можна, здавалося б, перекласти так:

if d>0 then x1:=(-b- sqrt(d))/(2*a); x2:=(-b+sqrt(d))/(2*a)

Else

if d=0 then x1:=-b/(2*a);

{інакше нічого не робити}

Але це неправильно! Оператор розгалуження закінчується оператором присвоювання змінній x1. Оператор x2:= (-b+sqrt(d))/(2*a) записано уже за роздільником ";", тобто після оператора розгалуження. Те, що написано далі, взагалі не є оператором.

Як же записати послідовність із двох або більше операторів там, де має бути один? Напрошується відповідь, що їх треба взяти в дужки. І такі дужки, що перетворюють послідовність операторів у один оператор, у мові Паскаль є. Це так звані відкриваюча та закриваюча операторні дужки: ключові слова begin і end (початок і кінець).

Запис вигляду

begin послідовність операторів end

називається складенимоператором.

Отже, опишемо обчислення одного або двох коренів таким оператором розгалуження в повній формі:

if d>0 then

begin x1:=(-b+sqrt(d))/(2*a); x2:=(-b-sqrt(d))/(2*a) end

Else

if d=0 then x1:=-b/(2*a)

Як бачимо, після слова then записано складений, а після слова else – оператор розгалуження в скороченій формі.

Оформимо алгоритм обчислення коренів у вигляді програми:

program roots(input, output);

var a, b, c: real; x1, x2: real;

Begin

{1} readln(a,b,c); {припускаємо, що a<>0! }

{2} d:=b*b-4*a*c;

{3} if d>0 then

Begin

x1:=(-b+sqrt(d))/(2*a);

x2:=(-b-sqrt(d))/(2*a)

End

Else

if d=0 then x1:=-b/(2*a)

end.

Якщо при виконанні цієї програми задати значення змінних a, b, c, наприклад, відповідно 1, 3, 2, то справджується d>0, і обчислюються x1 і x2. Якщо задати значення 1, 2, 3, то умова d>0 хибна, обчислюється умова d=0, її значенням є false, і на цьому все закінчується. При значеннях 1, 2, 1 умова d=0 істинна, і обчислюється лише x1.

До програми слід додати оператори виведення, щоб вона не була занадто "мовчазною". Це залишається як вправа.

І останнє зауваження щодо структури операторів розгалуження. Розглянемо такий оператор:

if z>0 then if z>5 then k:=2 else k:=1

Хибності якої умови, z>0 чи z>5, відповідає else -гілка? Тобто чи є оператор

if z>5 then k:=2

оператором розгалуження в скороченій формі, чи він має повну форму

if z>5 then k:=2 else k:=1?

Відповідь на це питання дає наступне неформальне правило.

Будемо рухатися по тексту програми від слова else назад до найближчого слова if,пропускаючи при цьому складені оператори. Цьому слову if та хибності умови, записаної за ним, і відповідає else -гілка. Але якщо на шляху ми зустріли слово else, то за цим самим правилом спочатку відшукаємо відповідне йому if, і лише після цього продовжимо наши пошуки.

За цим правилом у останньому прикладі else -гілка k:=1 відповідає хибності умови z>5, а не z>0. В операторі

if z>0 then

begin readln(x); if x=0 then k:=1 end

else k:=5

else -гілка k:=5 відповідає хибності умови z>0, а не умови x=0, пропущеної у складеному операторі. За цим самим правилом у операторі

if x>0 then {квадранти перший або четвертий}

if y>0 then k:=1 else k:=4

else {квадранти другий або третій}

if y>0 then k:=2 else k:=3

гілка з початком " else if y>0" відповідає хибності умови x>0, а хибності першої умови y>0 відповідає гілка " else k:=4".

Масовість задач і програм

При виконанні оператора розгалуження, булів вираз у якому не тотожно істинний або хибний, можливі принаймні два різних процеси обчислень. Який із них здійснюється, залежить від значень змінних, що входять в умову, тобто від стану пам'яті програми. Таким чином, оператор розгалуження задає різні дії, що їх має виконати комп'ютер при різних станах пам'яті.

Різні стани пам'яті після виконання тих самих операторів програми можуть утворюватися, якщо її змінним "присвоюються з зовнішнього світу" різні набори значень. Отже, з використанням оператора розгалуження можна описати розв'язання задачі для різних наборів значень, що надходять "із зовнішнього світу" (вхідних значень, або вхіднихданих).

Програми, як правило, пишуться для того, щоб перекласти на комп'ютер розв'язання задач, які людина не хоче або не може розв'язати сама. Звичайно задача ставиться в загальному вигляді з указанням параметрів, від значень яких залежить хід і результат розв'язання, наприклад, "розв'язати квадратне рівняння ax ²+ bx + c =0, задане коефіцієнтами a, b, c ". Параметри тут – коефіцієнти рівняння.

Задачі, що ставляться в загальному вигляді з параметрами, називаються масовими. Задача, поставлена не в загальному вигляді, а з конкретним набором значень параметрів, називається екземпляромзадачі. Наприклад, "розв'язати рівняння x ²+3x+2=0, задане коефіцієнтами 1, 3, 2".

Всі можливі конкретні набори значень параметрів утворюють екземпляри задачі й задають конкретні процеси її розв'язання.

Алгоритм розв'язання масової задачі теж повинний бути масовим, тобто таким, що за ним можна здійснити процеси розв'язання всіх екземплярів задачі. Наприклад, розв'язати всі можливі конкретні квадратні рівняння. Таким чином, програми, як правило, мають властивість масовості. І оператор розгалуження – це один із засобів, яким масовість забезпечується.

Блок-схеми

Процеси, задані оператором розгалуження if умова then оператор else оператор, можна зобразити як гілки одного процесу, на які він розділяється. Позначимо обчислення умови ромбом, із якого виходять два стрілки, позначені можливими значеннями умови true і false. Стрілки задають послідовність дій. Позначимо виконання оператора прямокутником; рис.3.1 виражає "розгалуження" процесу виконання оператора розгалуження на два можливих процеси, хоча при будь-якому його виконанні здійснюється в точності один із них.

Зображення, складені з прямокутників, ромбів указаного вигляду й стрілок, називаються блок-схемами. Одна зі стрілок звичайно починається з "нізвідки" і позначає початок блок-схеми. Якщо рухатися по стрілках і виписувати дії, позначені в блоках (ромбах і прямокутниках), утворяться позначення процесів, що задаються блок-схемою. Отже, блок-схема – це теж алгоритм, тільки виражений в іншій формі. Такого, нехай не зовсім точного, тлумачення блок-схем нам буде достатньо, оскільки ми скористаємося ними лише для ілюстрації семантики окремих операторів.

Пункт (3) алгоритму обчислення коренів квадратного рівняння за його коефіцієнтами можна задати блок-схемою з рис. 3.2.

У деяких випадках блок-схеми дуже наочно подають можливі процеси виконання програми. На зорі програмування вони використовувалися дуже широко, і перед написанням програм навіть необхідно було креслити блок-схеми. Тепер можна обходитися і без них.

Задачі

3.7. * Імітувати виконання операторів, де x, y – імена змінних цілого типу:

readln(x);

if x=1 then y:=16 else

if x=2 then y:=256 else

if x=3 then y:=4096 else

y:=10000;

writeln(y),

якщо при читанні x одержує значення:

а) 1; б) 2;

в) 3; г) 4.

3.8. Написати програму обчислення та друкування дійсних коренів квадратного рівняння, заданого коефіцієнтами a, b, c,

а) де a¹ 0; б) де, можливо, a =0.

3.9. * Написати програму дослідження, тобто обчислення кількості коренів рівняння ax ²+ bx + c =0 за його коефіцієнтами a, b, c (можливо, a =0).

3.10. Написати програму дослідження вигляду множини розв'язань нерівності ax ²+ bx + c >0 (два інтервали, інтервал і т.п.).

3.11. Зобразити аналогічно рис.3.2 алгоритми розв'язання задач 3.8–3.10.

3.12. Написати програму визначення виду трикутника за трьома довжинами його сторін (можна припускати, що вони додатні й задовольняють нерівності трикутника):

а)* рівносторонній, рівнобедрений і не рівносторонній, різнобічний;

б) гострокутний, прямокутний, тупокутний.

 

Функція та її виклики

Status in statu.

(лат.: Держава в державі)

Розглянемо задачу: обчислити мінімальну з відстаней між точками площини A (x1; y1), B (x2; y2) і C (1;2). Алгоритм розв'язання цієї задачі очевидний:

1) обчислити відстані d1 = AB, d2 = AC, d3 = BC;

2) обчислити m = min{ d1, d2, d3 }.

Відстань між точками з довільними координатами (x; y), (x'; y') виражається формулою d = , і для обчислення відстаней нам необхідно тричі написати "Паскалівський" варіант цієї формули з різними наборами координат: x1, y1, x2, y2, потім x1, y1, 1, 2, потім x2, y2, 1, 2. Ці вирази досить громіздкі й задають по суті ті самі обчислення, тільки з різними наборами значень. Все це можна записати інакше.

Мова Паскаль дозволяє описати повторювані обчислення один раз, дати цьому опису ім'я і далі не описувати самі обчислення, а тільки позначати їх цим ім'ям.

Отже, у мові Паскаль є описи обчислень і є їх позначення. Опис обчислень, як правило, є параметризованим, подібно до алгоритму обчислення коренів квадратного рівняння, де параметрами були коефіцієнти рівняння. Конкретні значення, з якими треба зробити обчислення, вказуються в позначенні обчислень разом із ім'ям цього опису й називаються аргументами. Опис обчислень деякого значення називається функцією, а їх позначення – викликом функції.

У даному випадку параметрами будуть чотири координати двох точок. Назвемо їх a1, b1, a2, b2. Опис обчислень задається у вигляді функції, якій ми дамо ім'я dd:

function dd(a1, b1, a2, b2: real):real;

Begin

dd:=sqrt(sqr(a1-a2)+sqr(b1-b2))

end;

Цей опис є означенням імені dd, тому поміщається серед інших означень програми. Позначення цієї функції, тобто виклики її з конкретними аргументами записуються в тілі програми:

program minimdis(input, output);

var x1, y1, x2, y2, d1, d2, d3, m: real;

function dd(a1, b1, a2, b2: real):real;

Begin

dd:=sqrt(sqr(a1-a2)+sqr(b1-b2))

end;

Begin

writeln('введіть координати двох точок:');

readln(x1, y1, x2, y2);

d1:=dd(x1, y1, x2, y2);

d2:=dd(x1, y1, 1, 2);

d3:=dd(x2, y2, 1, 2);

if d1<d2 then m:=d1 else m:=d2;

if d3<m then m:=d3;

writeln('найменша відстань: ', m)

End.

При виконанні цієї програми після читання значень змінних виконується виклик функції dd: значення змінних x1, y1, x2, y2 присвоюються відповідним параметрам a1, b1, a2, b2 як звичайним змінним і потім обчислюється значення dd. Воно і є значенням виразу dd(x1, y1, x2, y2), що присвоюється змінній d1.

Так само, тільки з іншими аргументами, виконуються другий і третій виклики функції, і інші значення присвоюються змінним d2 і d3.

Отже, ми бачимо, що мова Паскаль дозволяє не тільки користуватися викликами "стандартних" функцій, наприклад, odd або sin, але й створювати свої власні.

Функція має такий загальний вигляд:

function ім'я (означення параметрів): ім'я типу;

означення

Begin

послідовність операторів

end;

У першому рядку функції записано заголовок, де вказано її ім'я й означення параметрів. Наприкінці заголовка обов'язково записується ім'я типу значень, що обчислюються в результаті виконання викликів функції. Ці значення називаються такими, що повертаються.

Параметрів у функції може не бути, тоді й дужки відсутні, а виклик такої функції є просто її ім'ям.

Після заголовка структура функції повторює структуру програми за винятком лише точки в кінці. У функції можна визначати свої змінні, сталі та функції. Проте функція істотно відрізняється від програми тим, що:

1) функція записується серед означень програми;

2) ім'я самої програми ніде в програмі не вказується, тоді як серед операторів функції обов'язково повинні бути оператори присвоювання з ім'ям функції в лівій частині, причому при виконанні виклику функції хоча б один із них повинен бути виконаним.

Виклик функції є виразом того типу, який указано в її заголовку. І він, як усякий вираз, може бути частиною складнішого виразу. Наприклад, за необхідності ми могли б написати d1:=sqr(dd(x1, y1, 1, 2)+1).

Повернемося до прикладу. Нескладно написати функцію обчислення меншого з двох значень:

function min(x1, x2: real):real;

Begin

if x1<x2 then min:=x1

else min:=x2

end;

і помістити її слідом за функцією dd у програмі minimdis. З її використанням обчислення мінімального зі значень змінних d1, d2, d3 можна в тілі програми задати так:

m:=min(d1, d2); m:=min(m, d3)

або навіть так:

m:=min(min(d1, d2), d3)

При обчисленні останнього виразу спочатку виконується "внутрішній" виклик min(d1, d2). Значення, обчислене при його виконанні, стає аргументом у "зовнішньому" виклику.

Задачі

3.13. * Написати функцію even, тобто "парне", що задає обчислення ознаки парності цілого.

3.14. Написати функцію обчислення за дійсним параметром x:

а) його знака (sign(x)=-1, 0 або 1 відповідно при x<0, x=0, x>0);

б)* ceil(x) – найменшого цілого, що не менше, ніж значення параметра (для від'ємних значень параметра можливі два варіанти означення).

3.15. Написати програму обчислення периметра й площі трикутника за координатами його вершин.

3.16. Написати тригонометричні функції з дійсним параметром, значення якого вимірюються в градусах.

3.17. Написати функцію означення за довжинами трьох відрізків, чи утворюють вони трикутник З її використанням написати програму обчислення, скільки трикутників можна утворити з чотирьох заданих різних відрізків.