Матвієнко Ю.С. Програмування та математичне моделювання
Подождите немного. Документ загружается.
Матвієнко Ю.С. Програмування та математичне моделювання.
61
Домашнє завдання
1. Напишіть функцію, яка повертає максимальне з двох цілих чисел,
отриманих в якості аргументу.
2. Напишіть функцію, яка порівнює два цілих числа та повертає
результат порівняння у вигляді одного із знаків >, < або =.
3. Напишіть функцію обчислення факторіалу.
§11 Рекурсія
В цьому параграфі ви вивчите:
- поняття рекурсії;
- структуру рекурсивного алгоритму;
- використання рекурсивного алгоритму при складанні програм.
Теоретичні відомості
З поняттям допоміжного алгоритму пов’язане більш складне поняття
рекурсивного алгоритму – алгоритму, який використовує в якості
допоміжного самого себе. Такі алгоритми досить широко використовуються
в програмуванні, що ґрунтується на рекурсивній природі багатьох структур
даних та математичних алгоритмів.
Матвієнко Ю.С. Програмування та математичне моделювання.
62
Зазвичай усяке визначення, яке вводить нове поняття, пояснює його за
допомогою інших понять, які вже відомі. Але в математиці і в програмуванні
зустрічаються визначення, які не вкладаються в цю схему. Наприклад в
формулах
( )
>⋅
=
=
>−⋅
=
=
−
0,
,0,1
;0,!1
,0,1
!
1
nякщоxx
nякщо
x
nякщоnn
nякщо
n
n
n
обчислення факторіалу та степеня числа з цілим невід’ємним показником для
знаходження кожного наступного значення потребує знати попереднє. Це
рекурсивне визначення.
Рекурсивне визначення – часто використовуваний в математиці спосіб
задання функції, при якому значення шуканої функції в даній точці
визначається через її значення в попередній точці.
Потужність рекурсивного визначення полягає в тому, що воно дозволяє
за допомогою кінцевого висловлення визначити нескінченну множину
об’єктів. Аналогічно за допомогою кінцевої рекурсивної програми можна
описати нескінченні обчислення, причому програма не буде містити явних
повторень.
Ми вже знаємо, що існує можливість вийти з основної програми,
звернутися до підпрограми і, закінчивши її, повернутися в основну програму
до оператора, наступного після звернення до підпрограми. А чи може
підпрограма звернутися сама до себе? В паскалі це дозволено.
Підпрограма, що звертається сама до себе як до підпрограми
(безпосередньо або через ланцюг підпрограм), називається рекурсією.
Для виразу рекурсивних програм необхідно й достатньо мати поняття
процедури або підпрограми, оскільки вони дозволяють дати будь-якому
оператору ім’я, за допомогою якого до нього можна звертатися. Саме слово
«рекурсія» означає «повернення».
Рекурсія – спосіб визначення функцій, які є об’єктом вивчення в теорії
алгоритмів та інших розділах математики. Цей спосіб давно
використовується в арифметиці для визначення числових послідовностей
(прогресій, чисел Фібоначчі). Суттєву роль грає рекурсія і в обчислювальній
математиці (рекурентні методи).
Роботу рекурсивної функції розглянемо на прикладі обчислення 5!.
Визначення вказує на те, що 5!=4!*5. Таким чином, щоб обчислити 5! Ми
повинні спочатку обчислити 4!. Використаємо означення ще раз. 4!=3!*4,
тобто треба шукати 3!. Продовжуючи цей процес ми кожен раз звертаємося
до факторіалу попереднього числа. Аж поки не дійдемо до 0!=1.
Рекурсивний виклик процедури мало чим відрізняється від виклику
іншої процедури. Все проходить так, нібито звернення відбулося до іншого
екземпляру тієї ж процедури. Виконується той самий код, але с іншим
Матвієнко Ю.С. Програмування та математичне моделювання.
63
значеннями параметрів та внутрішніми змінними. Схематично внутрішній
механізм рекурсії виглядає так:
1. розміщуються в пам’яті параметри, що передаються
процедурі;
2. зберігаються в пам’яті значення внутрішніх змінних;
3. запам’ятовується адреса повернення до процедури, що
викликається;
4. передається керування викликаній процедурі.
Логічна складність рекурсивних підпрограм полягає в зміні параметрів
та особливостях отримання проміжних результатів при послідовному
зверненні підпрограми до себе. Важливим для розуміння ідеї рекурсії є те,
що в подібних підпрограмах можна виділити дві серії кроків. Перша серія –
ЦК кроки рекурсивного занурення підпрограми в себе до тих пір, поки
обраний параметр не досягне граничного значення. Ця важлива вимога
завжди повинна виконуватися, щоб підпрограма не створила нескінченну
послідовність викликів сама до себе. Кількість таких кроків (кількість копій
змінних, що одночасно знаходяться в пам’яті) називається глибиною рекурсії.
Друга серія – це кроки рекурсивного виходу до тих пір, поки обраний
параметр не досягне початкового значення. Вона, як правило, забезпечує
отримання проміжних та кінцевих результатів.
Практичні завдання
1. Написати програму, яка за допомогою рекурсивної підпрограми
знаходить n!.
2. Запрограмувати рекурсивний алгоритм перемноження двох
натуральних чисел, використовуючи рекурсивне співвідношення
>+⋅−
=
=⋅
.1,)1(
,1,
abba
ab
ba
3. Запрограмувати рекурентний алгоритм обчислення квадрату
натурального числа, використовуючи рекурентне співвідношення
>−++−
=
=
.1,1)1(
,1,1
2
2
nnnn
n
n
Матвієнко Ю.С. Програмування та математичне моделювання.
64
Контрольні питання
1. Що називається рекурсією?
2. Який принцип дії рекурсивного алгоритму?
3. Як схематично можна описати механізм рекурсії?
4. В чому полягає логічна складність рекурсивних
підпрограм?
5. Наведіть приклади використання рекурсії в математиці.
Домашнє завдання
1. Маємо ціле невід’ємне число n. Перетворити його в двійкове.
2. Складіть власну програму, в якій би використовувався
рекурсивний алгоритм.
Матвієнко Ю.С. Програмування та математичне моделювання.
65
§12 Рядкові величини
В цьому параграфі ви вивчите:
- структуру рядка та методи роботи з ним;
- рядковий тип даних та методи його обробки;
- операції над рядковими змінними;
- процедури та функції обробки рядків .
Теоретичні відомості
Для роботи з текстом в паскалі використовується структурований тип
string (рядок).
Рядок – це ланцюг, складений з символів. Символи беруться з кодової
сторінки, яка підтримується в комп’ютері.
Значення рядкового типу String – послідовність символів. Кількість
символів в рядку від 0 до 255. Рядок, як і символ, обмежується одинарними
лапками. До окремих символів рядка, які сумісні за типом зі значенням Char,
можна звертатися по номеру (індексу) даного символу в рядку. Для
визначення даних рядкового типу використовується ідентифікатор String, за
яким слідує у квадратних дужках значення максимально можливої довжини
рядка даного типу. Якщо це значення не вказується, то довжина рядка за
замовченням вважається рівною 255 байт, а при спробі записати у змінний
рядок більше символів, а ніж вказано в описі, «зайва» частина відсікається.
Рядкові дані використовуються в програмах і в якості констант. Перед
використанням рядка необхідно ініціалізувати порожніми або визначеними
значеннями. Порожній рядок позначається двома одинарними лапками
поспіль.
Отже рядкові змінні повинні бути визначені в розділі опису змінних,
наприклад:
Var
Text1: string;
T1: string [20];
T2: string [125];
де в квадратних дужках, як вже зазначалося вище, вказується максимальна
довжина рядка.
Можна задати рядковий тип, наприклад:
Type
Матвієнко Ю.С. Програмування та математичне моделювання.
66
Atten = string [100]
Var
B1: Atten
Рядкові константи визначаються текстом в лапках:
const
name = ‘Константи’
Над рядковими даними можливі елементарні операції, які дозволяють
складати рядкові вирази. До цих операцій належать конкатенація та операції
відношення.
Операції відношення виконуються шляхом порівняння рядків на основі
алфавіту. Порівняння відбувається щосимвольно зліва направо. Більшим
вважається рядок, в якому перший символ, що не співпадає, має більший
номер в алфавіті. Рядки вважаються рівними, якщо кожний символ одного
рядка співпадає з кожним символом іншого в черзі слідування. Результат
операції відношення має булевий тип.
У випадку рядків різної довжини алгоритм порівняння наступний.
Порівняються щосимвольно обидва рядки, починаючи з першого символу.
Якщо трапиться, що всі символи коротшого рядка співпадає з початковою
частиною довшого, то більше значення має довший рядок. Наприклад, вирази
‘міст’<’місток’
‘depend’>=’dependence’
мають відповідно значення True та False.
Присвоювання значення рядковій змінній можна виконати за
допомогою операції присвоювання:
T1:=’Герасименко Валерій’;
T2:=’Богдан Олександр’;
T3:=T1+’ та ‘+T2+’ – друзі’;
В одному виразі можна записати змінні як рядкового, так і символьного
типів.
Часто густо корисними операціями є перетворення даних символьного
типу в ціле число – код ASCII, а також обернене перетворення. Перетворення
символу в число виконується функцією Ord, а обернене перетворення –
функцією Chr. Запишемо елементарну програму переведення символів, що
вводяться з клавіатури, у числовий код:
Program SymbolCode;
Var
Xsymbol: char;
Begin
Write(‘Введіть символ: ‘);
Readln(Xsymbol);
Writeln(Xsymbol, ‘
має код’, Ord(Xsymbol));
End.
Матвієнко Ю.С. Програмування та математичне моделювання.
67
При виведенні символів числовий код може приймати значення від 0 до
255.
Обробка рядків за допомогою процедур та функцій
В паскалі є низка стандартних процедур та функцій для роботи з
рядками. Розглянемо їх структуру та дії, яку вони виконують:
Функції та процедури Призначення
Length(Z: String): Integer Повертає довжину рядка Z
Concat(Z
1
, [Z
2
,…,Z
n
]: String): String Повертає об’єднання (конкатенацію)
рядків Z
1
, Z
2
,…,Z
n
Copy(Z: String; Index: Integer; Count:
Integer): String
повертає підрядок рядка Z довжиною
Count, що починається з позиції Index
Pos(Substr: String; Z: String): Byte Визначає перше входження підрядка
в рядок і повертає 0, якщо Z не
містить Substr або номер першого
символу Substr в Z
Insert(Source: String; var Z: String;
Index: Integer)
Вставляє в рядок Z підрядок Source,
починаючи з позиції Index
Delete(var Z: String; Index, Count:
Integer)
Видаляє з рядка Z підрядок
довжиною Count, що починається з
позиції Index
Str(N:[:Width[:Decimals]]; var Z:
String)
Перетворює числове значення N в
рядкове Z. Можливе задання формату
для N
Val(Z; var N; var Code: Integer) Перетворює рядкове значення Z
(рядок цифр) в значення числової
змінної N
При побудові алгоритмів обробки рядків корисно знати та
використовувати наступні можливості:
• стандартні процедури та функції для рядків;
• впорядкованість множини символів;
• механізм динамічних рядків та їх внутрішнє представлення;
• два способи обробки змінних типу String;
Стандартні процедури та функції для рядків наведені в таблиці вище.
Впорядкованість множини символів стандартного набору ASCII
розуміється так: всі символи пронумеровані, і з двох символів більше той,
номер якого більше. (Стандартний набір ASCII дивись в додатку №2)
Внутрішнє представлення рядка можна пояснити малюнком (нижче) та
програмою, яка ілюструє прямий доступ до байту довжини та виводить на
дисплей послідовності символів:
0 1 2 3 … і і+1 … n-1 N
Chr(i) Зайнята частина рядку Вільна частина рядку
Матвієнко Ю.С. Програмування та математичне моделювання.
68
Const z: String[26]=’ABCDEFGHIJKLMNOPQRSTUVWXYZ’
Var i: 1..26;
Begin
For i:=1..26 do
Begin
z[0]:=Chr(i); {зміна байту довжини рядку}
writeln(z); {виведення підрядка}
end;
end.
Оголошується довжина рядка, а потім змінюється її показник довжини
та береться початковий фрагмент рядка необхідної довжини.
В паскалі є два способи обробки змінних типу String. Перший спосіб
передбачає обробку всього рядка як єдиного цілого, тобто єдиного об’єкту.
Другий спосіб розглядає рядок як складений об’єкт, який складається з
окремих символів, тобто елементів типу Char.
Практичні завдання
1. Напишіть програму, яка запитує ім’я користувача та вітається з
ним.
2. Перетворіть рядок „\/\/\/\/\/\/\/\/\/\/\/\/, заміняючи усяке входження
символу „\” на символ „/”.
3. Задані рядок і два слова. Після кожного першого заданого слова,
що зустрічається в даному рядку, вставити інше задане слово.
4. Знайдіть та виправте помилки в програмному коді, якщо вони є:
Const Z: string:=’*?** * ? ?**’;
ch: Char:=’?’;
i:= byre=0;
begin
writeln(z);
while Poz(ch, Z)<>0 do
begin
writeln(Poz(ch)+i)
delet(Z,Poz(ch),1);
Inc(i)
End;
Writeln(Z); readln
End.
Матвієнко Ю.С. Програмування та математичне моделювання.
69
Контрольні питання
1. Що називається рядком в розумінні мови програмування Турбо
Паскаль?
2. Яка структура даних рядкового типу String?
3. Назвіть елементарні операції, які можна проводити над даними
рядкового типу?
4. Що називається конкатенацією?
5. Які існують способи обробки змінних типу String в Турбо
Паскалі?
Домашнє завдання
1. В заданому рядку слова розділені у крайньому разі одним
пробілом. Видаліть зайві пробіли між словами, залишивши між
ними тільки по одному.
2. Підрахуйте в заданому рядку кількість символів В та видаліть ті з
них, яким передує (у вихідному рядку) символи А.
3. *Визначте, чи заданий рядок (фраза) є паліндромом?
Матвієнко Ю.С. Програмування та математичне моделювання.
70
§13 Графічні побудови
В цьому параграфі ви вивчите:
- роботу в графічному режимі в Турбо Паскалі;
- графічну бібліотеку;
- процедури та функції графічної бібліотеки.
Теоретичні відомості
Як Вам вже відомо, будь-який монітор ПЕОМ може працювати в
одному з двох режимів:
• текстовому;
• графічному.
Перший з них дозволяє виводити на екран будь-який символ ASCII-
таблиці (дивись в додатку №2) у визначене знакомісце екрану, що
знаходиться на перетині рядка та стовпчика. Кількість знакомісць залежить
від текстового режиму, але найчастіше дорівнює 25 рядкам по 80 колонок в
кожному. В цьому режимі можна керувати кольором та яскравістю символів,
забезпечуючи за бажанням їх миготіння, та кольором тіла.
В графічному режимі будь-яке зображення отримується як сукупність
різнокольорових точок - пікселів. Кількість елементів зображення теж
задається відповідним режимом, але стандартно дорівнює 640 на 480
відповідно по горизонталі та вертикалі.
Для роботи в графічному режимі в Паскалі використовується модуль
Graph, який складається з більш ніж 90 графічних процедур і функцій
широкого профілю. Усі стандартні засоби модуля Graph стають доступними
після його підключення до програми в розділі Uses:
Uses Graph;
Зверніть увагу на те, що для того, щоб графічна бібліотека стала
доступною, необхідно прописати до неї шлях доступу в пункті меню Options
->Directories ->Unit directories оболонки Паскаль. За замовчанням цей шлях
доступу наступний: BP\UNITS відповідного диску.
Екран у графічному режимі може адресуватися за допомогою системи
координат, причому значення Х (номера стовпчика) збільшується зліва
праворуч, а значення Y (номера рядка) збільшується зверху до низу. За
замовчанням координати екрана мають такий вигляд:
(0,0) - лівий верхній кут;