Алгоритми розгалуженого переходу

План.
Оператор безумовного переходу (goto).
Умовні оператори.
Складена команда.
Література: Я.М. Глинський. Інформатика. Алгоритмізація і програмування. Книжка 1. с. 67-85.
1 Оператор безумовного переходу (goto).
Команду переходу використовують щоб змінити порядок виконання команд у програмі.
Вона має такий вигляд:
goto – перекладається “перейти на”, де “мітка” – це адрес команди (оператора), на який потрібно перейти. Мітка може бути числом від 0 до 9999 або ідентифікатор, після якого є символ (:).
Приклади міток: 10:, 222:, m1:, alpha:. Усі мітки можна оголосити у розділі оголошення міток на початку програми так:

Наприклад:
label 10:, 222:, m1:, alpha:.
Задача Скласти програму обчислення функції:
для трьох різних значень x = 3,4,5 з клавіатури з використанням команди переходу goto.
Програма:
program FUN_Y;
label 10;
var x,y: real;
begin
10: write (’введіть значення х:’);
read ln (x);
y: = (3*5 sin (x) + cos (2*x)/(3.5-4*abs(x));
write ln (x:6:2, y:6:2)
goto 10;
end.
2. Умовні оператори.
У повсякденній діяльності часто доводиться аналізувати різноманітні ситуації, умови і залежно від них приймати ті чи інші рішення.
Команди розгалуження або умовні оператори змінюють порядок виконання дій у алгоритмі в залежності від виконання чи невиконання певних умов. Розгалуження бувають декількох видів. Найпростішим видом є “неповне розгалуження”.
Неповне розгалуження реалізується за допомогою команди if (якщо):
Виконання команди: може бути один оператор або група операторів. Якщо виконується умова (в блок-схемі – вітка “так”), то виконається оператори чи група операторів після слова then. Якщо ж умова не виконується (в блок-схемі – вітка “ні”), то ця команда не буде виконуватися і буде виконуватися наступний після if оператор (команда).
Умова – це логічний вираз, які бувають прості і складені.
Простий логічний вираз – це два арифметичні вирази, з’єднані символом відношення (порівняння).
У Паскалі символи відношень записуються так:>-більше,= - більше або дорівнює (не менше), <= - менше або дорівнює (не більше),
= - дорівнює, - не дорівнює.
Наприклад: x=2*x; xy.
Складені логічні вирази – це прості логічні вирази, до яких застосовані логічні операції not (не), and (і), or (або).
Наприклад. Побудувати вираз, який буде використовуватися для визначення студентів, які не отримали оцінки “2” з інформатики (тобто отримали інші оцінки). Для позначення оцінки використаємо числову змінну ocinka. Шуканий вираз можна записати так:
А). not(ocinka=z) або ocinka2.
Приклад.
Записати подвійну нерівність
0if a0 then y:=x+3 else y:=x-5;
write ln (‘y=’,y);
read ln
end.
Повне розгалуження.
Повне розгалуження реалізують за допомогою повної команди розгалуження if.
Виконання команди:
Якщо умова виконується (в блок-схемі – вітка “так”), то виконується команда 1 (або серія команд 1), якщо ні – то команда 2 (серія команд 2).
Зауваження. На місці команди 1 та команди 2 може бути теж команда розгалуження if.
Приклад. Визначимо більше число з-поміж двох чисел:
If a>=b then c:=a else c:=b;
де a i b – два числа, а с – проміжна змінна куди заносимо більше з 2-х чисел.
Оператор вибору case.
Якщо потрібно здійснити вибір з великої кількості варіантів, зручно використовувати оператор (команду) вибору case:
Виконання оператора:
Якщо значення виразу збігається зі значенням з найбільшого списку чи діапазону, то виконується відповідна команда, що записана після двокрапки “:” і на цьому виконання команди case закінчується, якщо ні, то виконується команда після слова else. Складової частини else може бути.
Задача. У багатьох університетах поточні знання студентів протягом семестру оцінюють за стобальною системою. Потім бали переводять в оцінки: <<відмінно>>,<<добре>>,<<задовільно>>,<<незадовільно>>.
Оцінки визначають так:
Бали Оцінка
88-100 <<відмінно>>
71-87 <<добре>>
50-70 <<задовільно>>
0-49 <<незадовільно>>
Скласти програму, яка для конкретного студента (name) і його кількості балів (bal) виводить його оцінку (mark).
program Marks;
var bal: integer; name, mark: string;
begin
write (‘Введіть прізвище’);
readln (name);
write (‘Введіть бали’);
readln (bal);
case bal of
88…100: mark:= ‘відмінно’;
71…87: mark:= ‘добре’;
50…70: mark:= ‘задовільно’;
0…49: mark:= ‘незадовільно’;
else mark: = ‘0’
end;
if mark ‘0’ then writeln (name:15, mark:15)
else writeln (‘помилка під час введення кількості балів’):
end.
або інший приклад:
case k of
1; cina:=22,
2,3: cina:=35;
4: cina:=50;
else cina:=97
end;
3. Складена команда.
Складена команда – це команда, в якій декілька команд об’єднано в одну за допомогою службових слів begin та end:
Задача. Скласти програму, яка дає довідку про назву столиці (St) та кількість населення (nas, у мільйонах) деякої країни (kr) з такого переліку: Угорщина, Італія, Україна.
program Countries;
var kr, st: string; nas: integer;
begin
write (‘Введіть назву країни’);
readln (kr);
if kr = ‘Угорщина’ then
begin
st:= ‘Будапешт’;
nas:=11
end;
if kr = ‘Італія’ then
begin
st:= ‘Рим’;
nas:=60
end;
if kr = ‘Україна’ then
began
st:= ‘Київ’;
nas:= 48
end;
writeln (‘Столиця - ’, st, ‘населення-’, nas, ‘млн осіб’)
end.
1. Алгоритм обчислення виразу за його ЗПЗ
Позначення операндів у ЗПЗ передують знакам операцій, які до них застосовуються, тому при читанні ЗПЗ спочатку обчислюються та запам'ятовуються операнди, а потім до них застосовується операція.
ЗПЗ виразу тепер читається, а для обчислень застосовується магазин. Але тепер це вже магазин операндів, а не знаків операцій. Числа, що є значеннями сталих чи змінних, переносяться в магазин. Якщо черговою лексемою є знак двомісної операції, то з магазина вилучаються два верхні елементи, і результат застосування операції до цих значень записується в магазин. За знаку одномісної операції з магазина вилучається лише один елемент. Ім'я функції на вході задає її застосування до елемента з верхівки магазина та вміщення результату в магазин. Після закінчення вхідного списку лексем у магазині зберігається лише одне число – значення всього виразу.
Процес обчислення можна подати послідовністю пар вигляду
(магазин операндів; непрочитана частина ЗПЗ).
Спочатку магазин порожній, а в кінці в ньому єдине значення.
Приклад 1. Обчислення ЗПЗ "2 3 * 4 +" подається так:
( ; 2 3 4 * - );
( 2 ; 3 4 * - ) – число 2 перенесено в магазин;
( 2 3 ; * 4 -) – те саме з 3;
( 6 ; 4 - ) – до операндів 2 і 3 застосовано множення;
( 6 4 ; - ) – число 4 перенесено в магазин;
(2 ; ) – до операндів 6 і 4 застосовано віднімання.
За обчислення ЗПЗ "2 3 4 * -" утвориться така послідовність:
( ; 2 3 4 * - );
(2 3 4 ; * -) – перенесено три числа в магазин;
(2 12 ; - ) – 3 і 4 перемножено;
(-10 ; ) – від 2 віднято 12. з
Уточнимо обробку ЗПЗ таким алгоритмом:
while на вході є лексема C do
case C of
стала чи ім'я змінної: заштовхнути її значення в магазин;
знак двомісної операції: виштовхнути з магазину два верхні елементи; обчислити результат застосування до них операції зі знаком С та заштовхнути результат в магазин;
знак одномісної операції: виштовхнути з магазину верхній елемент; обчислити результат застосування до нього операції зі знаком С та заштовхнути результат в магазин;
end;
видати верхній елемент магазина як результат.
2. Записи з варіантами.
У підрозділах 20.5, 20.6 ми уточнимо у вигляді підпрограм наведені вище алгоритми побудови ЗПЗ та обчислення значення виразу. Там ми скористаємося зручним засобом мови Паскаль, який досі не розглядався, – це записи з варіантами.
У нашій задачі ЗПЗ виразу будується у вигляді послідовності лексем. Послідовність можна подати масивом, списком, або файлом. У будь-якому разі це буде послідовність однотипних елементів. Проте у виразах є лексеми чотирьох різновидів: сталі, імена, знаки операцій і дужки. Природно у ЗПЗ зберігати не сталі чи імена змінних, а їх значення. Знаки операцій та дужки є символами, а імена функцій – рядками. Отже, доводиться говорити про кілька різних типів для подання лексем. Але незрозуміло, як різнотипні елементи зібрати в одну послідовність.
Одним із розв'язань цієї суперечності є використання записів із варіантами. Подивимося на лексеми як на пари вигляду (різновид, значення). Наприклад, стала 12 подається як (стала, 12), ім'я функції sin – (ім'я, 'sin'), відкриваюча дужка – як (дужка, '('). Для задання множини різновидів лексем означимо тип-перелік Ttlx:
type Ttlx = (con, nam, ops, par, err).
Ці імена є скороченнями від constant, name, operation sign, parenthesis та error – стала, ім'я, знак операції, дужка та помилка відповідно.
Отже, нам потрібен тип пар, першими компонентами яких є типи лексем, тобто елементи з переліку Ttlx, а другими – значення відповідних типів. У мові Паскаль для подання пар природно скористатися структурними типами, яких нам потрібно 5, разом із типом для помилкових лексем.
Об'єднати різні типи структур в один можна за допомогою означення типу структур (записів) із варіантами. Вираз, що задає тип таких записів, схожий на вирази, якими задаються типи записів, або структур. Його загальний вигляд такий:
record
спільна частина;
варіантна частина
end;
У спільній частині означаються поля, наявні в усіх об'єднуваних типах (їх список може бути порожнім). У варіантній частині після ключового слова case означається селектор – додаткове поле перелічуваного типу. Насправді воно є спільним в усіх об'єднуваних типах. Потім записуються значення селектора разом із відповідними варіантами наборів полів, якими відрізняються об'єднувані типи. Варіантом є список означень полів, записаний у дужках.
Звернімо увагу, що слово end в означенні лише одне – можна вважати, що воно є "закриваючою дужкою", яка відповідає як record, так і case.
Приклад 2. Нехай у виразах імена й помилкові лексеми мають не більше восьми символів, і діють означення типів st8 = string[8] та Ttlx. Тип лексем задається означенням
type Tlx = record { спільна частина порожня }
case stl : Ttlx of
con : (numb : real);
nam : (name : st8 );
ops : (sig : char);
par : (prt : char);
err : (wrlx : st8 )
end
Тут stl є ім'ям селектора, а в дужках указано варіанти – списки означень полів, поставлені у відповідність його значенням. Щоправда, тут усі ці списки мають по одному елементу.з
Тип селектора задається тільки ім'ям, а імена полів повинні бути унікальними в межах означення типу запису. Синтаксис списку полів варіанта такий самий, як і списку полів запису (зокрема, можливі спільна й варіантна частини з таким самим синтаксисом).
Приклад. 3. Означити тип записів для подання таких відомостей про студента: прізвище, ім'я, курс, оцінки останньої сесії, а також рік народження та відношення до військової служби юнаків, або знак Зодіаку та колір очей дівчат.
Зберемо означення спільних даних для юнаків та дівчат у спільну частину означення, а селектор статі та означення відповідних полів – у варіантну:
type Sex=(male, female); {тип "стать" – чоловіча або жіноча}
type Student=
record
surname, name : string[30]; {прізвище та ім'я – рядкові}
course : integer; marks : string[10]; {курс та оцінки}
case sexslc : Sex of
male : (year : integer; military : boolean);
female : ( Zodiak : string[10]; eyecolor : string[10])
end з
Під варіантні частини змінних-записів виділяється стільки пам'яті, скільки її потрібно для "найдовшого" з варіантів. Так, селектор змінних типу Tlx займає 1 байт, а довжина варіантної частини визначається "найдовшим" типом st8 (9 байтів у Турбо Паскаль). Дані типу Student займають 31+31+1+11+11=85 байтів.
Селектор призначений для відображення типу варіантної частини запису. Але доступ до ділянок пам'яті варіантної частини запису здійснюється через імена полів незалежно від значення селектора в записі, тобто засоби мови не забезпечують відповідності значень селектора й варіантів у змінних-записах. Тому потрібна особлива увага, щоб не робити помилок на зразок наступної:
var lx : Tlx; a : real; …
lx.stl := con;
lx.nam := 'sin'; { створено невідповідність !!! }
if lx.stl = con then a:= lx.numb { значення a – ??? }

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать