Мови та технологія програмування 2

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство загальної та професійної освіти
Російської Федерації
Уральський державний університет
ім. А.М. Горького
Лахтін А.С., Іскакова Л.Ю.
Мови та технологія програмування.
Початковий курс.
Навчальний посібник
Єкатеринбург
1998

Лахтін А.С., Іскакова Л. Ю. Мови та технологія програмування. Початковий курс. Учеб. посібник. Єкатеринбург, 1998.
Даний навчальний посібник являє собою першу частину однойменного лекційного курсу, який читається студентам математико-механічного факультету в 1 семестрі.
Початковий курс присвячений викладу основ створення програм. Виклад ведеться з використанням мови програмування Турбо Паскаль. Розглядаються деякі класичні алгоритми. Наводяться приклади розв'язання типових задач.
Посібник призначений для студентів дистантной форми навчання спеціальності "Інформаційні системи", а також може бути використано для студентів денної форми навчання за цією спеціальністю.
ãА.С. Лахтін, Л.Ю. Іскакова, 1998.

ЗМІСТ
"1-3"
ВСТУП
ОСНОВИ МОВИ
АЛГОРИТМИ
Алфавіт мови
СТРУКТУРА ПРОГРАМИ
ТИПИ ДАНИХ
Цілі типи
Речові типи
Логічний тип
Символьний тип
ВИРАЖЕННЯ
СУМІСНІСТЬ ТИПІВ ДАНИХ
ЛІНІЙНІ АЛГОРИТМИ
ПОРОЖНІЙ І Складовою оператор
Оператор присвоєння
Простий ввод І ВИСНОВОК
Розгалужується АЛГОРИТМИ
ОПЕРАТОР ПЕРЕХОДУ
УМОВНИЙ ОПЕРАТОР
ОПЕРАТОР ВИБОРУ
ЦИКЛІЧНІ АЛГОРИТМИ
Цикл з параметром.
ЦИКЛИ з умовою.
Користувацькі типи ДАНИХ
ПЕРЕРАХОВУВАТИ ТИП
ТИП-ДІАПАЗОН
МАСИВИ
ЗАПИСИ
Роботи з рядками
ПРОЦЕДУРИ І ФУНКЦІЇ
Параметри-значення
Параметри-змінні
Параметри-константи
ВІДКРИТІ ПАРАМЕТРИ-МАСИВИ
Безтипових ПАРАМЕТРИ
Процедурні ТИПИ
Рекурсія
Типізовані константи
МОДУЛІ
АЛГОРИТМИ ПОШУКУ
ЛІНІЙНИЙ ПОШУК
ПОШУК з бар'єром
Двійкові (бінарний) ПОШУК
АЛГОРИТМИ СОРТУВАННЯ
СОРТУВАННЯ ВИБОРОМ
СОРТУВАННЯ Обмінів (методом "бульбашки")
ШЕЙКЕРНАЯ СОРТУВАННЯ
СОРТУВАННЯ ВКЛЮЧЕННЯМ
СОРТУВАННЯ Хоара
СОРТУВАННЯ З ВИКОРИСТАННЯМ ВЕКТОРА ІНДЕКСІВ
МОДУЛЬ CRT (основні можливості)
ЛІТЕРАТУРА

ВСТУП
Перша версія мови Паскаль була розроблена швейцарським вченим Никлаусом Віртом в 1968 році. Спочатку мова призначався для цілей навчання, оскільки він є досить детермінованим, тобто все підпорядковується певним правилам, винятків з яких не так багато. Основні характеристики: відносно невелика кількість базових понять, простий синтаксис, швидкий компілятор для перекладу вихідних текстів у машинний код.
У 1992 р . фірма Borland International випустила два пакети, заснованих на мові Паскаль: Borland Pascal 7.0 і Turbo Pascal 7.0. Перший може працювати у трьох режимах - звичайному і захищеному режимах MS DOS і в системі Windows. Для нього необхідно близько 30 Мбайт на жорсткому диску і близько 2 Мбайт оперативної пам'яті. Турбо Паскаль 7.0 працює тільки в звичайному режимі MS DOS і менш вимогливий до характеристик комп'ютера. Оскільки основні компоненти, які ми будемо розглядати в нашому курсі, збігаються в обох продуктах, надалі буде використовуватися назва Турбо Паскаль.
Пакет включає в себе алгоритмічну мову програмування високого рівня, вбудований редактор і середу, призначену для налагодження та запуску програм. Крім того, пакет містить великий обсяг довідкової інформації (англомовної). Як відомо, мови програмування діляться на два типи: інтерпретатори і компілятори. Турбо Паскаль відноситься до компіляторним мов.

ОСНОВИ МОВИ
АЛГОРИТМИ
Алгоритмом називають опис послідовності дій, необхідних для вирішення певної задачі. Головною рисою цього алгоритму є обчислювальна складність і емкостная складність. Обчислювальна або, інакше, часова складність алгоритму - це кількість елементарних операцій у процесі його виконання. Розрізняють обчислювальну складність в середньому і в гіршому випадку. Ємнісна складність алгоритму - це обсяг використовуваних даних, а також обсяг коду самої програми. При створенні алгоритму метою є скорочення як його обчислювальної, так і ємнісної складності.
Алгоритми можуть записуватися різними способами, наприклад, у вигляді блок-схем або у вигляді програм. Програма це набір вказівок виконавцю, тобто в нашому випадку - комп'ютера.
Алфавіт мови
Під алфавітом мови розуміють сукупність допустимих символів. У мові Турбо Паскаль використовуються символи ASCII (американський стандартний код обміну інформацією). Можна виділити чотири основні групи символів: символи, використовувані в ідентифікаторах, роздільники, спеціальні символи і невикористовувані символи.
Ідентифікатор - це ім'я будь-якого об'єкта мови. Він може складатися з латинських букв (a. .. z), цифр (0 ... 9) і знака підкреслення і не повинен починатися з цифри. Прописні і малі літери в ідентифікаторах і зарезервованих словах вважаються ідентичними, вони розрізняються лише в строкових константах. Довжина ідентифікатора не обмежена, але значущими є лише перші 63 символу.
Роздільники використовуються для відділення один від одного ідентифікаторів, чисел і зарезервованих слів. До розділювачам відносяться, наприклад, пробіл і коментар. У будь-якому місці програми, де дозволяється один пробіл, їх можна вставити будь-яку кількість.
Коментарі полягають або у фігурні дужки {коментар 1}, або в символи (* коментар 2 *) і можуть займати будь-яку кількість рядків. Послідовність з трьох символів (*) починає коментар до кінця рядка. Текст коментаря ігнорується при компіляції, якщо це не директиви компілятора, які мають вигляд {$}.
ПРИКЛАД:
(* Допустимий {{{в (* програмі} коментар *).
(* Не допустимий {{{в (* програмі *) коментар *).
До спеціальних знаків відносяться знаки пунктуації (. () [] ..:;), Знаки операцій і зарезервовані слова. Знаки операцій можуть бути як символьні (+, -, *, / і т.д.), так і літерними (mod, div, not). Зарезервовані слова є службовими і не можуть бути перевизначені користувачем, тобто їх не можна використовувати як імена для користувача об'єктів. Невикористані символи - це коди ASCII, які використовуються тільки в коментарях і символьних рядках, але не в мові. До них відносяться всі російські літери, а також символи%, &,! І т.п.
СТРУКТУРА ПРОГРАМИ
У програмі, написаній на Турбо Паскалі, можуть бути наступні розділи:
Program ... ; {Тема програми}
Uses ... ; {Підключення модулів}
Label ... ; {Розділ оголошення міток}
Const ... ; {Розділ оголошення констант}
Type ... ; {Розділ оголошення нових типів}
Var ... ; {Розділ оголошення змінних}
Procedure ... ; {Опис своїх процедур}
Function ... ; {Опис своїх функцій}
Begin {початок основної програми}
...;
{Оператори}
...;
End.
Обов'язковою частиною є лише тіло програми, що починається словом begin, а закінчується словом end з точкою. Оператори в Паскалі розділяються крапкою коми. Тема програми є хоч і необов'язковим, але бажаною елементом і складається із зарезервованого слова program та ідентифікатора - імені програми, за який варто крапка з комою. Порядок оголошень і описів не регламентується.
ПРИКЛАД: Найпростіша програма.
program prim_1; {демонстрація структури програми}
{Ця програма не вимагає ніяких оголошень і описів}
begin
write ('Привіт! Ось ми і почали.') (* цей рядок тексту з'явиться на екрані *)
end.
ТИПИ ДАНИХ
Поняття типу даних є ключовим у мові Паскаль. Тип даних характеризує внутрішнє уявлення, безліч допустимих значень для цих даних, а також сукупність операцій над ними. Серед типів даних розрізняють стандартні (зумовлені розробниками мови) і призначені для користувача (визначені програмістом у своїй програмі). Ми будемо розглядати наступні стандартні типи: цілі числа, дійсні числа, логічний тип, символьний і строковий типи. Програміст може описати свій тип на основі цих базових у розділі опису типів, який починається словом Type. Потім для кожного типу слід конструкція виду:
ідентифікатор типу = визначення типу;
Розглянемо спочатку прості типи даних, кожен з яких визначає впорядкована множина значень: цілі типи, логічний тип, символьний тип, речові типи. Всі ці типи, крім речових є порядковими. Кожному значенню порядкового типу функція Ord ставить у відповідність натуральне число - порядковий номер даного значення в множині допустимих значень. До будь-яких порядковим типам також можна застосовувати функції Pred - повертає попереднє значення і Succ - таке значення. Тип відноситься до впорядкованим якщо для змінних і виразів цього типу визначені операції відносини або порівняння: =, <>, <,>, <=,> =. Будь-який порядковий тип є впорядкованим, але не навпаки. Так речові типи і тип string впорядковані, але не порядкові.
Цілі типи
У мові Турбо Паскаль визначено 5 цілих типів:
Shortint (-128 ... 127, 1 байт),
Integer (-32 767 ... 32768, 2 байти),
Longint (-2147483648 ... 2147483647, 4 байти),
Byte (0 ... 255, 1 байт),
Word (0 ... 65535, 2 байти).
Для цілих чисел визначені такі операції. Унарні: +, -. Бінарні: додавання, віднімання, множення, отримання приватного (div) і залишку (mod) при целочисленном поділі та деякі інші. Також з цілими числами можна робити операції, результати яких не цілі числа. Це звичайний поділ і операції відношення. Крім того, є велика кількість вбудованих функцій для роботи з цілими числами: abs, sqr, sqrt, sin, cos, exp, ln та ін
Речові типи
У Турбо Паскалі є 5 речових типів.
Real (займає 6 байт, діапазон від 2.9E-39 до 1.7E +38 за модулем, точність 11-12 значущих цифр)
Single (займає 4 байти, діапазон від 1.5E-45 до 3.4E +38 за модулем, точність 7-8 значущих цифр)
Double (займає 8 байт, діапазон від 5.0Е-324 до 1.7Е +308 по модулю, точність 15-16 значущих цифр)
Extended (займає 10 байт, діапазон від 3.4E-4932 до 1.1E +4932 за модулем, точность19-20 значущих цифр).
Comp (займає 8 байт, діапазон від-9.2E-18 до 9.2E +18, зберігаються точно, оскільки це цілі числа)
Речові типи є впорядкованими, але не порядковими. Операції над числами: додавання, віднімання, множення, ділення і операції відношення. Крім того, є велика кількість вбудованих функцій для роботи з числами: abs, sqr, sqrt, sin, cos і т.п.
Речові числа зберігаються неточно. Кожен з наявних речових типів гарантує правильне зберігання лише певної кількості значущих цифр, їх називають вірними цифрами. З математичної точки зору, через особливості внутрішнього уявлення мова йде про відносну похибки.
Неточності у зберіганні дійсних чисел можуть призвести до того, що при вирахуванні близьких чисел може відбутися втрата значущості. Це ж пояснює, чому слід уникати порівняння речових величин на точне рівність.
ПРИКЛАД: тип Single - зберігається 7-8 знаків після десяткової точки, тип Double - 15-16, тип Extended - 19-20.
program sravnenie;
var x: single; y: double; z: extended;
begin
x: = 1 / 3; y: = 1 / 3;
z: = abs (xy);
writeln ('z =', z);
end.
Ця програма видасть в результаті число z = 9.93410748106882E-0009. Зазвичай прийнято вважати, що a = b, якщо виконується умова abs (ab) <eps. Число eps можна визначати наступним чином: min (abs (a), abs (b)) * 10 ^ (-m), де m - необхідне число співпадаючих десяткових розрядів.
Логічний тип
Змінні логічного типу Boolean займають у пам'яті один байт і можуть приймати одне з двох значень False - помилкове або True - істинне. Цей тип є порядковим (Ord (False) = 0, Ord (True) = 1) і, отже, упорядкованим. Результат будь-яких операцій порівняння має логічний тип і може бути присвоєний логічної змінної. Для операндів типу boolean визначені такі логічні операції: NOT - заперечення (перетворює false в true, а true в false), AND - логічне множення "і", OR - логічне додавання "або", XOR - виключає або (true якщо операнди різні) . Принцип дії цих операцій можна проілюструвати такими схемами:
AND
false
true
false
false
false
true
false
true

OR
false
true
false
false
true
true
true
true
XOR
false
true
false
false
true
true
true
false
Символьний тип
Символьний тип Char також називають літерним. Він дозволяє працювати з символами, які записуються двома способами: в одинарних лапках або по їх коду, наприклад 'a', 'B', '*' або, що те ж саме, # 97, # 130, # 42. На відміну від тексту програми на паскалі, символи, що відповідають регістру розрізняються. Безліч значень типу Char представляє собою повний набір ASCII - символів (американська стандартна кодування). У комп'ютері зберігаються шістнадцяткові коди символів (1 байт), які і використовуються в операціях відносини (порівняння). Функція Ord видає код відповідного символу, який може бути від 0 до 255. Зворотною функцією, яка за кодом видає відповідний символ, є функція Chr.
ВИРАЖЕННЯ
Вислів - це одиниця мови, яка визначає спосіб обчислення деякого значення. Вирази формуються з констант, змінних, функцій, знаків операцій і круглих дужок за певними синтаксичним правилам.
Константами називаються параметри програми, значення яких не змінюються в процесі її виконання. Вони зустрічаються або безпосередньо у вигляді значення, або у вигляді ідентифікатора константи, описаного в розділі, що починається зі слова Const. Для кожної константи в розділі вказується конструкція виду:
ідентифікатор константи = значення;
Цілі константи містять лише цифри і знак: -214, 23, речові можуть містити також десяткову точку, показник ступеня і символ e, який замінює підставу 10 в запису числа: -0.5,-1e-5, 7.2e +15. Логічні константи - це значення False або True. Символьна константа являє собою символ ASCII, укладений в апострофи. Якщо символ не має фізичного зображення, то пишеться знак # і поруч ASCII-код символу без апострофів.
Змінними називаються параметри програми, які можуть змінювати своє значення в процесі її виконання. Усі без винятку змінні повинні бути описані в розділі програми, що починається зі слова VAR. Потім слідують конструкції види:
список ідентифікаторів змінних: тип1;
список ідентифікаторів змінних: тип2;
У списку імена змінних перераховуються через кому. Крім базових типів Турбо Паскаля тут можна використовувати свої типи (описані раніше в розділі Type). У Турбо Паскалі є велика кількість вбудованих функцій для роботи з даними кожного типу. Імена (покажчики) цих функцій з аргументом у круглих дужках можуть також зустрічатися у виразах. Знаки операцій залежать від типу використовуваних у вираженні операндів та розглянуті вище.
Круглі дужки використовуються для зміни порядку обчислення частин висловлювання. Вирази без дужок обчислюються в порядку, відповідному пріоритету операцій. Пріоритети розставлені таким чином:
обчислення в круглих дужках;
обчислення значень функцій;
унарні операції (not, +, -);
операції типу множення (*, /, div, mod, and);
операції типу додавання (+, -, or, xor);
операції відносини (=, <>, <,>, <=,> =).
У логічному вираженні 2 <= 4 and 5> 3 Паскаль видасть помилку, оскільки операція and буде виконана раніше операцій порівняння. Вірна запис - (2 <= 4) and (5> 3).
СУМІСНІСТЬ ТИПІВ ДАНИХ
Коли в операціях або операторах вашої програми присутні дані різних типів, то постає питання про їх сумісності. У мові Турбо Паскаль цьому питанню приділяється дуже велика увага, розроблені суворі правила, що визначають ідентичність, сумісність в загальному випадку і сумісність з присвоюванню різних типів.
Нам на початку курсу достатньо пам'ятати наступне. Змінні або висловлення одного типу є цілком сумісними. Іншим поняттям є сумісність за присвоюванню. Присвоєння змінній одного типу виразу іншого типу припустиме в тому випадку, коли безліч значень другого типу є підмножиною значень першого. Наприклад, результат складання двох цілих змінних типу integer та word може присвоюватися в цілу змінну, тип якої тільки longint, оскільки тільки цей цілий тип містить у собі весь можливий діапазон значень як для типу integer, так і для типу word. Також, можна привласнювати цілий вираз в речову змінну або символьне вираз в рядок.
ЛІНІЙНІ АЛГОРИТМИ
Алгоритмічні дії над вихідними даними та робочими об'єктами мови, необхідні для вирішення поставленого завдання описуються за допомогою операторів Турбо Паскаля. Оператори розділяються крапкою з комою, їх послідовність і складає тіло програми. Найбільш простий випадок є лінійними алгоритми. При виконанні лінійних ділянок алгоритму оператори виконуються послідовно один за одним в тому порядку, в якому вони перераховані в програмі. При цьому можуть використовуватися оператори присвоювання, операції введення і виведення.
ПОРОЖНІЙ І Складовою оператор
У програмі може застосовуватися порожній оператор, який не виконує ніякої дії. Він являє собою крапку з комою.
Складовим оператором вважається послідовностей довільної операторів, укладена в операторні дужки - зарезервовані слова begin ... end. Допускається довільна глибина вкладеності складових операторів. Складовою оператор застосовується там, де за синтаксичним правилам мови може стояти тільки один оператор, а нам треба виконати декілька дій. У цьому випадку набір необхідних команд повинен бути оформлений як складової оператор. По суті, все тіло програми представляє собою один складений оператор.
Оператор присвоєння
Оператор присвоювання використовується для завдання значення змінних і має такий синтаксис:
ім'я_змінної: = вираз;
Обчислюється вираз, що стоїть у правій частині оператора, після чого його значення записується в змінну, ім'я якої стоїть зліва. Тип вираження і тип змінної повинні бути сумісні, тобто безліч допустимих значень для типу виразу міститься у безлічі допустимих значень для типу змінної.

Простий ввод І ВИСНОВОК
Розглянемо найпростіші процедури введення і виведення. За замовчуванням введення здійснюється з клавіатури, а вивід на екран. До операторів введення відносяться:
Read (<список змінних через кому>);
Readln (<список змінних>);
Readln;
Другий відрізняється від першого тим, що після введення переводить курсор на новий рядок, точніше, в кінці своєї роботи зчитує з клавіатури код клавіші <Enter>. Третій оператор використовується для організації паузи - виконання програми продовжиться, як правило, тільки після натискання на клавіатурі клавіші <Enter>. До операторів виведення відносяться:
Write (<список виведення>);
Writeln (<список виведення>);
Writeln;
У списку виведення крім імен змінних можна писати рядкові константи (послідовність символів у апострофа) і навіть виразу (виводяться їх значення). Другий оператор відрізняється від першого тим, що після виведення переводить курсор на новий рядок. Третій оператор просто переводить курсор на новий рядок.
Існує так званий форматований висновок. Можна задати кількість позицій, що відводяться під число. Для цілих - після висловлення або змінної через двокрапку вказується менше якої кількості позицій не може бути виділено значенням. Для дійсних - додатково через двокрапку можна вказати кількість цифр в дробовій частині. При цьому відбувається округлення у ближню бік.
ПРИКЛАД: Прості обчислення.
program vvod_vyvod;
const n = 1.5;
var y1, y2: real; x: byte;
begin
writeln ('Введіть натуральне число <= 255');
readln (x);
y1: = cos (n); y2: = cos (x);
write ('Навіщо щось порахували:');
writeln ('n =', n, 'y1 =', y1: 7:4, cos (Pi / 2): 8:4);
{Надрукується
Навіщо щось порахували: n = 1.50000000000000E +0000
y1 = 0.0707 1.0000}
writeln ('x =', x: 3, 'y2 =', y2: 7:4);
end.
Розгалужується АЛГОРИТМИ
У Турбо Паскалі є можливість нелінійного ходу програми, тобто виконання операторів не в тому порядку, в якому вони записані. Таку можливість нам надають розгалужуються алгоритми. Вони можуть бути реалізовані одним з трьох способів: з використанням операторів переходу, умовного оператора або оператора вибору.
ОПЕРАТОР ПЕРЕХОДУ
Оператор переходу має вигляд
GOTO <мітка>.
Він дозволяє передати управління безпосередньо на потрібний оператор програми. Перед цим оператором повинна розташовуватися мітка відділена від нього двокрапкою. У Турбо Паскалі в якості міток виступають або цілі числа від 0 до 9999, або ідентифікатори. Всі мітки повинні бути описані в розділі оголошення міток наступним чином:
label <список міток через кому>;
Кожній міткою у програмі може бути помічений лише один оператор. Операторів переходу з однієї і тієї ж міткою можна писати будь-яку кількість. Необхідно, щоб розділ опису мітки, сама позначка і оператор переходу з її використанням розташовувалися в межах одного блоку програми (див. тему процедури і функції). Крім того, не можна передавати управління всередину структурованих операторів (наприклад, if, for, while, repeat та ін.)
УМОВНИЙ ОПЕРАТОР
Умовний оператор IF дозволяє змінити порядок виконання команд залежно від деякого логічного умови, тобто він здійснює розгалуження обчислювального процесу. Умовний оператор має вигляд:
IF <умова> THEN <оператор1> [ELSE <оператор2>];
У разі істинності логічного виразу, що стоїть в умові, виконується <оператор1>, а <оператор2> пропускається. При помилковому значенні логічного виразу пропускається <оператор1> і виконується <оператор2>.
Оператор IF може бути повним (присутні обидві гілки) або неповним (Else-гілки немає, за помилкової умови нічого не робиться). За правилами кожна з гілок може містити або один виконуваний оператор, або кілька, об'єднаних в складовою. Крапка з комою перед Else вважається помилкою.
ПРИКЛАД: Ввести ціле число. Вивести відповідний йому символ ASCII-таблиці, або повідомити, що такого символу немає (0-31 - керуючі коди, потім до 256 - друковані символи).
program ascii_symbol;
var i: word;
begin
write ('Введіть ціле число:'); readln (i);
if (i> 31) and (i <256) then
writeln ('Відповідний символ -', Chr (i))
else writeln ('Такого символу немає');
readln
end.
ОПЕРАТОР ВИБОРУ
Якщо у вас не два можливих варіанти виконання програми, а більше, то може використовуватися оператор вибору CASE. Структура цього оператора в Турбо Паскалі:
CASE <ключ_вибора> OF
C1: <оператор1>;
C2: <оператор2>;
CN: <операторN>;
[ELSE <оператор0>;]
END;
Тут <ключ_вибора> - це вираз порядкового типу, в залежності від значення якого приймається рішення; C1 ,..., CN - значення, з якими порівнюється значення <ключа>; <оператор1 >,..., <операторN> - оператор ( можливо складові), з яких виконується той, з константою якого відбувається перший збіг значення <ключа>, <оператор0> виконається, якщо значення ключа не збігається ні з однією з констант C1 ,..., CN.
Гілка Else не обов'язкова, і на відміну від оператора if, перед нею можна ставити крапку з комою. Якщо для кількох значень <ключа> дії збігаються, то ці константи можна перерахувати через кому перед двокрапкою або навіть поставити діапазон значень (нижня межа .. верхня межа).
ПРИКЛАД: Вводиться ціле число, якщо це цифра, то визначити парна вона чи ні, а якщо число, то визначити чи попадає воно в діапазон від 10 до 100, якщо ні, то видати відповідне повідомлення.
program chislo;
var i: integer;
begin
write ('Введіть ціле число:');
readln (i);
case i of
0,2,4,6,8: writeln ('Парна цифра');
1,3,5,7,9: writeln ('Непарна цифра');
10 ... 100,200: writeln ('Кількість від 10 до 100 або 200');
else writeln ('Кількість або негативне, або> 100, але не 200');
end;
readln
end.
ЦИКЛІЧНІ АЛГОРИТМИ
Турбо Паскаль дозволяє використовувати три різних оператора для організації повторюваних послідовностей дій, які називають циклами.
Циклу з параметром
Оператор циклу For організовує виконання одного оператора заздалегідь визначене число разів. Його ще називають "цикл з лічильником. Існує дві форми оператора:
FOR <параметр>: = <nz> TO <kz> DO <оператор>;
FOR <параметр>: = <nz> DOWNTO <kz> DO <оператор>;
Тут параметр циклу (лічильник) являє собою змінну порядкового (ординальні) типу; <nz> і <kz> - вирази, що визначають початкове і кінцеве значення лічильника; <оператор> - один (можливо складовою) оператор, який називають тілом циклу, що повторюється певне кількість разів.
На першому кроці циклу параметр приймає значення nz. У цей же момент відбувається обчислення kz - значення параметра на останньому кроці циклу. Після кожного виконання тіла циклу, якщо параметр циклу не дорівнює kz, відбувається зміна параметра на наступне більший чи менший значення в залежності від форми оператора for, тобто неявно відбувається виконання одного з двох операторів:
<Параметр>: = Succ (<параметр>);
<Параметр>: = Pred (<параметр>);
У разі nz> kz у першій формі оператора або nz <kz у другій його формі помилки не відбувається, але цикл не виконується жодного разу. Після завершення роботи циклу значення параметра залишається рівним kz.
РЕКОМЕНДАЦІЇ: Використовувати цикл for при заздалегідь відомому кількості повторень. Не змінювати параметр у тілі циклу. При використанні кратних (вкладених) циклів застосовувати різні змінні в якості параметрів. Визначати до циклу значення всіх використовуваних в ньому змінних. Не ставити крапку з комою після do.
ПРИКЛАД: Вводяться 10 чисел, порахувати серед них кількість позитивних.
program cycle_for1;
var i, kn: byte; x: real;
begin
kn: = 0;
for i: = 1 to 10 do
begin
writeln ('Введіть', i, 'число:');
readln (x);
if x> 0 then kn: = kn +1 {збільшуємо кількість на 1}
end;
writeln ('Ви ввели', kn, 'позитивних чисел.');
readln
end.
ПРИКЛАД: Надрукувати букви від 'Z' до 'A'.
program cycle_for2;
var c: char;
begin
for c: = 'Z' downto 'A' do write (c);
readln
end
ПРИКЛАД: Обчислити N-е число Фіббоначчі. Числа Фіббоначчі будуються таким чином: F (0) = F (1) = 1; F (i +1) = F (i) + F (i-1); для i> = 1. Це приклад обчислень за рекурентним формулами.
program Fib;
var a, b, c: word; i, n: byte;
begin
write ('введіть номер числа Фіббоначчі');
readln (N);
a: = 1; {a = F (0), a відповідає F (i-2)}
b: = 1; {b = F (1), b відповідає F (i-1)}
for i: = 2 to N do
begin
c: = a + b; {c відповідає F (i)}
a: = b; b: = c; {в якості a і b береться наступна пара чисел}
end;
writeln (N, '-е число Фіббоначчі =', b); {для N> = 2 b = c}
readln
end.
ЦИКЛИ З УМОВАМИ
Якщо заздалегідь невідома кількість повторень циклу, то використовуються цикли з умовою. У паскалі є два типи таких циклів. Цикли While називають циклами з передумовою. Вони мають вигляд
WHILE <логіч.вираженіе> DO <оператор>;
Цикл While організовує виконання одного (можливо складеного) оператора поки істинно логічне вираз, що стоїть в заголовку циклу. Оскільки значення логічного виразу перевіряється на початку кожної ітерації, то тіло циклу може не виконатися жодного разу. Таким чином, в цьому циклі логічне вираз - це умова продовження роботи в циклі.
Інший варіант циклів з ​​умовою - це цикли Repeat. Їх називають циклами з постусловіем. Вони мають вигляд
REPEAT
<Оператор 1> ... <Оператор N>
UNTIL <логіч.вираженіе>
Оператор Repeat організовує повторюване виконання декількох операторів до тих пір поки не стане істинним умова, що стоїть у Until-частини. Тіло циклу обов'язково виконується хоча б один раз. Таким чином, в цьому циклі логічне вираз - це умова виходу з циклу.
При створенні циклічних алгоритмів Турбо Паскаль дозволяє використовувати процедури Continue і Break. Процедура Continue достроково завершує черговий крок циклу, передає управління на заголовок. Процедура Break реалізує негайний вихід з циклу.
РЕКОМЕНДАЦІЇ: Для того, щоб уникнути зациклення програми необхідно забезпечити зміну на кожному кроці циклу значення хоча б однієї змінної, що входить до умова циклу. Після виходу з циклу зі складним умовою (з використанням операцій and, or, xor) як правило необхідна перевірка того, яким умові цикл завершений.
ПРИКЛАД: Пари невід'ємних дійсних чисел вводяться з клавіатури. Порахувати твір для кожної пари і суму всіх чисел.
program cycle_while;
var x, y, sum: real; otv: char;
begin
sum: = 0;
otv = 'Д';
while (otv = 'Д') or (otv = 'д') do
begin
write ('Введіть числа x, y> 0');
readln (x, y);
writeln ('Їх твір =', x * y: 8:3);
sum: = sum + x + y;
write ('Завершить програму (Д / Н)?');
readln (otv);
end;
writeln ('Загальна сума =', sum: 8:3);
readln
end.
ПРИКЛАД: У тому ж завданні можна використовувати інший цикл з умовою:
program cycle_repeat;
var x, y, sum: real; otv: char;
begin
sum: = 0;
repeat
write ('Введіть числа x, y> 0');
readln (x, y);
writeln ('Їх твір =', x * y: 8:3);
sum: = sum + x + y;
write ('Завершить програму (Д / Н)?');
readln (otv);
until (otv = 'Д') or (otv = 'д');
writeln ('Загальна сума =', sum: 8:3);
readln
end.
ПРИКЛАД: Знаходження найбільшого загального дільника двох цілих чисел за допомогою Алгоритму Евкліда.
program Evklid;
var a, b, c: integer;
begin
write ('введіть два цілих числа:');
readln (a, b);
while b <> 0 do
begin
c: = a mod b;
a: = b;
b: = c;
end;
writeln ('найбільший загальний дільник =', a);
readln
end.

Користувацькі типи ДАНИХ
У Турбо Паскалі передбачений механізм створення нових типів, які прийнято називати користувача або конструюються. Їх можна створювати на основі стандартних і раніше створених типів. Опис нових типів відбувається в розділі TYPE. Після цього можна в розділі Var створювати змінні цих типів. Також, можна відразу описувати новий тип при створенні змінної в розділі Var. У цьому розділі ми розглянемо такі користувацькі типи:
перераховується тип,
тип-діапазон,
масиви,
запису.
ПЕРЕРАХОВУВАТИ ТИП
Перераховується тип задається перерахуванням тих значень, які він може отримувати. Кожне значення має бути ідентифікатором (див. розділ Алфавіт мови) і розташовуватися в круглих дужках через кому. Кількість елементів у перерахуванні не більше 65536. Вводити і виводити змінні перечисляемого типу заборонено. Перераховувані тип є порядковим (див. розділ Типи даних), тому до змінних такого типу можна застосовувати функції Ord, Pred, Succ. Функція Ord повертає порядковий номер значення починаючи з нуля.
ПРИКЛАД: Оголошення перелічуваних типів.
Type Colors = (Red, Green, Blue);
Numbers = (Zero, One, Two, Three, Four, Five);
var c: Colors; n: Numbers;
begin
c: = Red; write (Ord (c)); {0}
n: = Four; write (Ord (n)); {4}
c: = Succ (c); {c = Green}
for n: = One to Five do write (Ord (n)); {12345}
end.
Слід зазначити, що стандартні типи byte, word, char і boolean також можна вважати варіантами перечислимого типу.
ТИП-ДІАПАЗОН
Тип-діапазон також називають обмеженим або інтервальним типом. Він є підмножиною свого базового типу, в якості якого може виступати будь-який порядковий тип крім типу-діапазону. Тип-діапазон успадковує всі властивості свого базового типу. Є дві стандартні функції, які працюють із цим типом: High (x) - повертає максимальне значення типу-діапазону, до якого належить змінна x; Low (x) - повертає мінімальне значення.
ПРИКЛАД: Оголошення типу-діапазон.
type Numbers = (Zero, One, Two, Three, Four, Five);
Num = Two .. Four; {діапазон на базі типу Numbers}
Abc = 'A' .. 'Z'; {всі англійські букви: діапазон на базі типу Char}
Digits = 0 .. 9; {цифри}
var n: Num; c, d: Abc; x: integer;
begin
n: = Four; writeln (Ord (n)); {4 як в базовому типі}
n: = Succ (n); {ПОМИЛКА (таке значення поза діапазоном)}
read (c, d);
if c = d then write ('однакові букви');
writeln (Low (c), '..', High (c)); {A .. z}
writeln (Low (x), '..', High (x)); {-32768 .. 32767}
end.
У тексті програми на Турбо Паскалі можуть зустрічатися директиви компілятору, які також називають опціями. Опції {$ R +} і {$ R-} дозволяють включати і відключати перевірку дотримання меж при роботі з діапазонами. Коли перевірка включена, у разі порушення кордонів діапазонів відбувається аварійне завершення роботи програми. В іншому разі відповідальність за можливі помилки лежить на програмістові.
МАСИВИ
Масив - це впорядкована структура однотипних даних, яка зберігає їх послідовно. Доступ до елемента масиву здійснюється через його індекс. Масиви описуються наступним чином:
Ім'я типу = ARRAY [діапазони індексів] OF тип елемента масиву;
В якості типу для елементів масиву можна використовувати будь-які типи Турбо Паскаля крім файлових. Діапазони індексів являють собою один або кілька діапазонів, перераховані через кому. Як діапазонів індексів не можна використовувати діапазони з базовим типом Longint.
ПРИКЛАД: Три способи опису одного і того ж типу масиву:
type {1} M1 = array [0 .. 5] of integer;
M2 = array [char] of M1;
M3 = array [-2 .. 2] of M2;
{2} M3 = array [-2 .. 2] of array [char] of array [0 .. 5] of integer;
{3} M3 = array [-2 .. 2, char, 0 .. 5] of integer;
var A: M3;
{Звертатися до елементів масиву можна наступним чином:}
begin
read (A [-1, 'a', 3]);
read (A [1] ['x'] [0]);
A [1] ['c', 1]: = 100;
end.
Глибина вкладеності, тобто кількість індексів, при визначенні масивів не обмежена. Грає роль тільки сумарний обсяг даних в програмі. У стандартному режимі роботи Турбо Паскаля цей обсяг обмежений розмірами сегмента, тобто 64 кілобайт. Цілком над масивами допускається застосування тільки операції привласнення масивів (подмассивов) однакових типів. Інші операції повинні виконуватися поелементно.
ПРИКЛАД: Обчислення значення многочлена степені N, коефіцієнти якого знаходяться в масиві A в точці X за схемою Горнера.
Pn (x) = A [0] * X ^ n + A [1] * X ^ (n-1) + ... + A [n-1] * X + A [n] =
= (...(( A [0] * X + A [1]) * X + A [2]) * X + ... + A [n-1]) * X + A [n].
program Scheme_Gorner;
type Mas = array [0 .. 100] of integer;
var A: Mas; i, j, n: integer; x, p: real;
begin
write ('ступінь многочлена ='); read (n);
writeln ('введіть цілі коефіцієнти:');
for i: = 0 to n do read (A [i]);
write ('значення X ='); read (x);
p: = 0;
for i: = 0 to n do p: = p * x + A [i];
writeln ('Pn (X) =', p);
end.
ЗАПИСИ
Запис - це стpуктуpа даних, яка може містити інформацію різних типів, об'єднану під однією назвою. Компоненти записи називаються полями. Їх фіксіpованное число. Опис записів має наступну стpуктуpу:
Ім'я типу = RECORD
список полів 1: тип 1;
- - -
список полів N: тип N;
CASE поле вибору: тип OF
значення 1: (полів 1: тип 1)
END;
Типи полів записи можуть бути будь-якими. У свою чергу, тип запис може використовуватися для створення масивів і нових записів. Ступінь вкладеності не обмежена.
Список полів може складатися з двох розділів: постійної і варіантної частини. У постійній частині йде перерахування полів запису (ідентифікаторів) із зазначенням їх типів. Синтаксис такий же, як у розділі var.
ПРИКЛАД: Приклад оголошення типу запис.
type Men = Record
FIO, Adress: string;
Year: byte;
End;
var A, B: Men;
Для звернення до полів запису вказується ім'я змінної типу запис, точка, ім'я поля, наприклад:
begin
A. FIO: = 'Іванов І.І.';
A. Adress: = 'пp. Леніна, буд 40, кв. 10 ';
A. Year: = 1981;
end.
Після опису постійних полів може слідувати варіантна частина, яка може бути тільки одна і має вигляд
CASE поле вибору: тип OF
значення 1: (список полів 1);
- - -
значення N: (список полів N);
Поле вибору може бути відсутнім. Якщо воно є, то його сприймають як постійне полі запису. Якщо його немає, зазначається лише тип, який повинен бути порядковим, але він не впливає ні на кількість перерахованих нижче значень, ні на типи цих значень.
Всі варіанти розташовуються в одному і тому ж місці пам'яті, якої виділяється стільки, скільки потрібно для максимального по pазмеpа варіанту. Це призводить до того, що зміна одного варіантного поля впливає на всі інші. Це збільшує можливості пpеобpазования типів, ПРИКЛАД: Запис з варіантами.
var R = Record
rem: string;
Case byte of
3: (n: integer);
5: (x, y, z: char);
'A': (i, j: byte);
end;
begin
R.rem: = 'запис з варіантами';
Rn: = 25000;
write (Ri, Rx, Rj, Ry); {168і97a}
{Ord ('і') = 168, ord ('a') = 97, 168 +97 * 256 = 25000}
end.
Значення вибору можуть повторюватися. Імена полів запису не є змінними і, отже, можуть повторюватися, але тільки на різних рівнях, наприклад:
var Rec: Record
x: real;
Sr: Record a: real; x, y: integer; end;
I: byte;
end;
Для зручності звернення до полів записів може використовуватися опеpатоpа приєднання
WITH мінлива DO опеpатоpа;
Тут змінна - це запис, за якою може слідувати список вкладених полів, напpимеp наступні три опеpатоpа еквівалентні:
With Rec, Sr Do a: = x / y;
With Rec.Sr Do a: = x / y;
Rec.Sr.a: = Rec.Sr.x / Rec.Sr.y;
Роботи з рядками
Тип String (рядок) в Турбо Паскалі широко використовується для обробки текстів. Цей тип є стандартним і багато в чому схожий на одновимірний масив символів Array [0 .. N] of Char. Значення N відповідає кількості символів в рядку і може змінюватися від 0 до 255. Символи, що входять в рядок, займають позиції з 1 до N. Початковий байт рядка з індексом 0 містить інформацію про її довжині, тобто це символ з кодом, рівним довжині рядка.
Можна, також описувати змінні типу String [K], де K - ціле число не більше 255. Так визначаються рядки з довжиною не більше K. Цей тип вже не є стандартним. З символами рядка можна працювати як з елементами масиву із символів, але на відміну від масивів, рядки можна вводити цілком, порівнювати один з одним і зчіплювати операцією "+".
ПРИКЛАД: Робота з рядками.
var s, x, y, z: string;
begin
x: = 'turbo';
y: = 'pascal';
z: = x + '' + y; {z = 'turbo pascal'}
s :=''; {порожній рядок}
for c: = 'a' to 'z' do s: = s + c; {s = 'abcd .. xyz'}
writeln (s);
end.
Порівняння рядків виконується посимвольний відповідно до їх кодами до першого неспівпадіння. Якщо один з рядків закінчилася до першого розбіжності, то вона вважається меншою. Порожній рядок менше будь-якого рядка.
ПРИКЛАД: Порівняння рядків.
'Abcd'> 'abcD' {'d'> 'D'}
'Abcd'> 'abc' {'d'>''}
'Abc' <'axxc' {'b' <'x'}
'Abcd' = 'abcd'
Існує ряд стандартних функцій і процедур для роботи з рядками.
Функція Length (s) видає довжину рядка s.
Функція Concat (s1, s2, .., sn) повертає рядок s1 + s2 + .. + sn.
Функція Copy (s, p, k) повертає фрагмент рядка s, що починається у позиції p і має довжину k.
Функція Pos (s1, s) шукає перше входження підрядка s1 в рядок s і повертає номер першого символу s1 в рядку s або 0 якщо не знайшли.
Процедура Delete (s, p, k) видаляє з рядка s фрагмент, який починається у позиції p і має довжину k.
Процедура Insert (s, s1, p) вставляє в рядок s підрядок s1, починаючи з заданої позиції p.
Турбо паскаль дозволяє виробляти перетворення числових значень у рядкові та навпаки. Для цього використовуються процедури Str (X: n: d, S) і Val (S, X, e). Перша отримує їх числа X рядок S з зображенням цього числа, в якому не менш n символів і з них d знаків після коми. Параметри n і d необов'язкові. Друга процедура отримує з рядка S число X. При успішному результаті e = 0.
ПРОЦЕДУРИ І ФУНКЦІЇ
Турбо Паскаль дозволяє виділяти фрагменти програми у допоміжні алгоритми (ВА). Це дозволяє писати добре структуровані програми. Мови програмування, в яких передбачені ВА, називаються процедурно-орієнтованими. Структуровані програми зазвичай простіше в розумінні і налагодженні.
Наявність ВА в мові програмування дозволяє застосовувати більш досконалі методи при розробці і проектуванні складних програмних комплексів. Відомі два найбільш широко застосовуваних підходу. Перший називається методом спадного програмування або розробкою програм "зверху - вниз". При цьому спочатку створюється головна програма, припускаючи наявність деяких ВА, які вирішують певні завдання. Потім переходять до детальної розробки згаданих вище необхідних ВА.
Іншим підходом у розробці програм є метод висхідного програмування чи проектуванням "знизу - вгору". У цьому випадку все починається зі створення невеликих ВА, з яких потім створюються більш складні ВА і, нарешті, основна програма.
У Турбо Паскалі ВА оформляються у вигляді процедур або функцій. Кожен ВА має власне ім'я. Виклик процедури на виконання здійснюється окремим оператором за допомогою її імені. Виклик функції може бути складовою частиною будь-якого висловлювання за умови узгодженості типів. Опис процедур і функцій має передувати їх викликом і розташовується перед початком основної програми. Не можна викликати на виконання ті ВА, які містяться всередині інших процедур і функцій. Опис процедури має наступну структуру.
Procedure Ім'я (Список формальних параметрів);
label
const Опис локальних міток,
type констант, типів і змінних
var
procedure Опис внутрішніх процедур
function і функцій
begin
Оператори
end;
Опис функції має наступну структуру.
Function Ім'я (Список формальних параметрів): Тип результату;
label
const Опис локальних міток,
type констант, типів і змінних
var
procedure Опис внутрішніх процедур
function і функцій
begin
Оператори, серед яких хоча б один, який
присвоює імені функції значення результату
end.
Типом результату у функціях може бути будь-який зі стандартних типів Турбо Паскаля крім файлових типів. Використання конструйованих типів тут неприпустимо.
Існують поняття локальних і глобальних міток, констант, типів і змінних. Пояснимо ці поняття на прикладі змінних. Змінні, описані в основній програмі, є глобальними по відношенню до процедур і функцій, які описані пізніше цих змінних. Аналогічно, змінні, описані у процедурах та функціях, є глобальними по відношенню до внутрішніх процедур і функцій, які описані пізніше. Інші змінні називаються локальними. Їх область дії локалізована, тобто обмежена, тим ВА, де вони описані.
Вихідні дані для роботи ВА можна передавати через глобальні змінні, а також через параметри. Параметри при виклику ВА називаються фактичними, а параметри у заголовку ВА називаються формальними.
Формальні параметри ВА також відносяться до його локальним змінним. Локальні дані створюються, тобто їм виділяється пам'ять, при виклику ВА, а звільнення цієї пам'яті відбувається при завершенні роботи тимчасової адміністрації. У тому випадку, коли локальна змінна має той же ідентифікатор, що і глобальна, алгоритм працює з локальної. При цьому, значення глобальної змінної зберігається в спеціальній області пам'яті, яка називається стек.
За способом передачі параметри в Турбо Паскалі діляться на три типи:
параметри-значення,
параметри-змінні,
параметри-константи.

Параметри-значення
При виклику процедур і функцій формальним параметрам-значенням виділяється нове місце в пам'яті і присвоюються значення фактичних параметрів. При цьому на місці фактичних параметрів можуть стояти вираження. Працює з типів визначається можливостями присвоєння. Після виконання підпрограми місце формальних параметрів звільняється. Зміна формальних параметрів не позначається на значенні фактичних. Заголовок процедури з параметрами-значеннями має вигляд:
Procedure MyProc1 (par1, par2: type1; par3, par4: type2);
Параметри-змінні
При виклику процедур і функцій формальні параметри-змінні займають те ж саме місце в пам'яті, що і відповідні їм фактичні параметри. Таким чином, додаткове місце в пам'яті не виділяється і зміни формального параметра призводять до змін фактичного. Параметри-змінні, як правило, використовуються для передачі результатів з процедур в викликає алгоритм.
Такий механізм передачі даних вимагає, щоб фактичні параметри були змінними, причому в точності того ж типу, що й формальні параметри. При описі ВА перед параметрами-змінними повинне бути присутнім слово var. Заголовок процедури з параметрами-змінними має вид:
Procedure MyProc2 (var par1, par2: type1; var par3, par4: type2);
Параметри-константи
Робота з формальними параметрами-константами всередині ВА ведеться як зі звичайними локальними константами. Тільки ці константи приймають значення виразів, які перебувають у фактичних параметрах. Їм не виділяється нова пам'ять як локальним змінним. Забороняється змінювати їх значення під час виконання підпрограми і контроль за цим здійснюється на рівні компілятора, як для звичайних констант.
Використовувати параметри-константи рекомендується при передачі даних великого об'єму з гарантією збереження їх значень. Заголовок процедури з параметрами-константами має вигляд:
Procedure MyProc3 (const par1, par2: type1; const par3, par4: type2);
ВІДКРИТІ ПАРАМЕТРИ-МАСИВИ
Відкриті параметри-масиви можуть бути параметрами-значеннями, параметрами-змінними і параметрами-константами. Вони використовуються для передачі масивів довільної розмірності. Заголовок процедури з відкритими параметрами-масивами має вигляд:
Procedure OpenArray (Vector: array of MyType);
Формальний параметр при цьому є масивом елементів деякого типу MyType з нульовою базою, тобто Array [0 .. N-1] of MyType; де N - кількість елементів масиву, яке можна визначити за допомогою стандартної функції High.
ПРИКЛАД: Збільшення вдвічі всіх елементів масиву.
program DoubleProgram;
const n = 10; m = 20;
type T1 = array [1 .. n] of integer;
T2 = array [-m .. m] of integer;
var A: T1; B: T2; k: integer;
Procedure Double (var X: array of integer);
var i: byte;
begin
for i: = 0 to High (X) -1 do X [i]: = X [i] * 2;
end;
begin
for k: = 1 to n do read (A [k]);
for k: =- m to m do read (B [k]);
Double (A); {збільшення у 2 рази елементів масиву A}
Double (B); {збільшення у 2 рази елементів масиву B}
Double (k); {те ж саме, що і присвоювання k: = k * 2}
writeln ('k =', k); {надрукується: k = 40}
for k: = 1 to n do write (A [k], '');
writeln;
for k: =- m to m do write (B [k], '');
end.
Безтипових ПАРАМЕТРИ
У Турбо Паскалі існує можливість створення процедур і функцій з параметрами, що не мають типу. Безтипових параметри можуть бути параметрами-змінними і параметрами-константами, так як передаються лише за адресою. Заголовок процедури з параметрами, що не мають типу може виглядати таким чином:
Procedure MyProc (var par1, par2; const par3, par4);
Перед використанням формальних параметрів необхідно виконати їх приведення до якого-небудь типу. Використання безтипових параметрів дає велику гнучкість програмі, але відповідальність за їх коректне застосування покладається на програміста.
ПРИКЛАД: Складання перших N байт, починаючи з того ж місця, що і X.
program without_type;
var N: word; s: string;
{$ R-} (* відключення контролю за кордонами діапазонів *)
function Sum (var X; N: byte): word;
type A = array [1 .. 1] of byte;
var i: byte; s: word;
begin
s: = 0;
for i: = 1 to n do S: = S + A (X) [i];
Sum: = s;
end;
begin
readln (s);
writeln (Sum (s, ​​1)); {довжина рядка s}
writeln (Sum (s [1], 1)); {код першого символу рядка s}
writeln (Sum (s [1], length (s)));
{Сума кодів всіх символів рядка s}
read (N);
writeln (Sum (N, 2));
{Сума двох байт, з яких складається N типу word}
end.
Процедурні ТИПИ
У Турбо Паскалі існує два процедурних типу: тип-процедура і тип-функція. Для оголошення процедурного типу використовується заголовок процедури або функції без імені.
ПРИКЛАД:
type Proc1 = Procedure (a, b, c: integer; x: real);
Proc2 = Procedure (var a, b);
Proc3 = Procedure;
Func1 = Function: real;
Func2 = Function (n: integer): boolean;
Можна описувати змінні цих типів, наприклад: var p1, p2: Proc1; f1, f2: Func2; Змінним процедурних типів можна присвоювати як значення імена відповідних ВА. При цьому не можна використовувати стандартні процедури і функції. Після такого присвоювання ім'я змінної стає синонімом імені ВА. Змінні процедурного типу можна, також передавати в підпрограми у вигляді параметрів. Завдяки цьому, є можливість створення більш гнучких допоміжних алгоритмів.
Рекурсія
Рекурсія - це спосіб організації обчислювального процесу, при якому підпрограма в ході виконання звертається сама до себе. З ідейної точки зору рекурсія аналогічна методу математичної індукції. Базі індукції відповідає база рекурсії. Припущенням індукції відповідає припущення про те, що потрібний ВА вже написаний. Нарешті, кроку індукції відповідає виклик створюваного рекурсивного ВА. У будь-якій рекурсії необхідно передбачити умову завершення процесу, тобто коли виклику більше не відбувається.
ПРИКЛАД: Обчислити N-е число Фіббоначчі. (Дивись тему Цикли)
program Fib;
var n: byte;
function F (k: byte): word;
begin
if k<2 then F:=1 else F:=F(k-1)+F(k-2); {рекурсивный вызов}
end ;
begin
write ('введите номер числа Фиббоначчи ');
readln (N);
writeln (N,'-е число Фиббоначчи =',F(N));
readln
end .
Рекурсивний виклик може бути непрямим, чи неявним. Наприклад це відбувається у випадку, коли один ВА викликає інший, а той у свою чергу - перший. При использовании такой программной конструкции необходимо опережающее описание процедур и функций с директивой Forward . Сначала пишется только заголовок ВА со словом Forward , а реализация приводится ниже. При цьому, в ній можна писати в заголовку або тільки ім'я ВА, або повністю повторювати заголовок.
ПРИМЕР : Неявная рекурсия.
Procedure B(x:byte); forward;
Procedure A(y:byte);
begin
- - -
B (y);
- - -
end ;
Procedure B;
begin
- - -
A (x);
- - -
end ;
РЕКОМЕНДАЦИИ : Необходимо по возможности избегать применения рекурсии, так как большая глубина рекурсивных вызовов часто приводит к переполнению стека. У деяких випадках проблему можна усунути, встановивши новий розмір стека від 1024 до 65520 байт за допомогою директиви
{ $M размер стека, нижняя граница, верхняя граница памяти}

Типізовані константи
Крім звичайних констант в Турбо Паскалі можна використовувати типізовані константи, які фактично є змінними з початковими значеннями. Они описываются в разделе Const в форме:
<Ім'я типізованої константи>: <тип> = <значення>;
ПРИМЕР:
const x : integer = 10; y : real = 3.14;
A : array [1..5] of integer = (1,2,-3,24,0);
B : array [1..2,-1..1] of byte = ((1,2,3),(4,5,6));
R : record m : string[10]; d,y : integer; end =
(M: 'January'; d: 20; y: 1999);
S: string [4] = 'abcd';
Типізовані константи можуть бути будь-якого типу окрім файлів. При роботі вони практично нічим не відрізняються від змінних. Різниця полягає тільки в тому, що якщо типизированная константа описана в процедурі чи функції, то при першому виклику цієї підпрограми типизированная константа приймає початкове значення, а при наступних викликах зберігає значення від попереднього виклику. Таким способом можна, наприклад, контролювати кількість викликів процедур або функцій.
ПРИМЕР : Использование типизированных констант
program typed_const;
var N:integer;
procedure Test;
const k:integer=1;
begin
if k<N then
begin
writeln (k,'-й вызов процедуры');
k: = k +1;
Test;
end
else writeln ('последний вызов процедуры');
end ;
begin
read (N);
if N>0 then Test;
end .
МОДУЛІ
Модуль ( Unit ) в паскале - это специальным образом оформленная библиотека определений типов, констант, переменных, а также процедур и функций. Модуль компилируется отдельно, в результате чего создается файл с расширением tpu (turbo pascal unit). Він не може бути запущений на виконання самостійно, а може використовуватися тільки з інших програм. Для этого в программах указывается список имен используемых модулей в разделе Uses , после чего программа может использовать константы, типы и переменные, описанные в этих модулях.
В Турбо Паскале существует несколько стандартных модулей: System , Crt , Dos , Printer , Overlay , которые составляют библиотеку Турбо Паскаля: файл turbo.tpl (turbo pascal library). К числу стандартных модулей также относится модуль Graph .
Існує можливість створювати нові модулі. Файл модуля має наступну структуру:
UNIT <имя модуля>;
INTERFACE
<Розділ оголошень>
IMPLEMENTATION
<Розділ реалізації>
Begin
<Розділ ініціалізації>
End.
Ім'я модуля повинно співпадати з ім'ям файлу, в якому він зберігається. Розділ оголошень або інтерфейсна частина містить оголошення всіх глобальних об'єктів модуля (типів, констант, змінних і підпрограм), які будуть доступні програмами, що використовують цей модуль. Підпрограми у цьому розділі оголошуються тільки заголовками. У інтерфейсної частини модулів не можна використовувати випереджувальний опис, тобто директиву forward .
Раздел реализации или исполняемая часть модуля содержит описание локальных объектов модуля: типов, констант, переменных и подпрограмм. Тут же міститься опис підпрограм, оголошених в інтерфейсній частини. Для цих підпрограм заголовок може вказуватися або без параметрів, або з параметрами, які в точності повторюють опис з розділу оголошень. Локальні об'єкти модуля доступні в межах модуля, але не доступні програмами, що використовують модуль.
Розділ ініціалізації може бути відсутнім. В этом случае можно даже не писать слово Begin , а сразу завершать модуль, написав End . В розділ ініціалізації входять оператори, які будуть виконуватися при запуску програми, що використовує модуль, перед виконанням основної програми. Розділ ініціалізації виконуються в тому порядку, в якому підключаються модулі.
ПРИМЕР : Модуль для работы с одномерными массивами до 100 целых чисел.
{Модуль описів, глобальних для основної програми та всіх модулів}
Unit Globals;
Interface
const Len=100;
type Vector = array [1..Len] of integer;
Implementation
End.
Unit Vectors;
Interface
uses Globals;
{Знаходить максимальний елемент масиву}
function Max_V(A:Vector; n:byte):integer;
{Поелементне складання двох векторів}
procedure Add_V(A,B:Vector; n:byte; var C:Vector);
{Скалярний добуток векторів}
function Scal_V(A,B:Vector; n:byte):integer;
Implementation
function Max_V; {заголовок без параметров}
var i,max:integer;
begin
max: = A [1];
for i:=2 to n do if A[i]>max then max:=A[i];
Max_V: = max;
end ;
procedure Add_V;
var i:integer;
begin
for i:=1 to n do C[i]:=A[i]+B[i];
end ;
function Scal_V(A,B:Vector; n:byte):integer;
{Заголовок з interface}
var s:integer; i:byte;
begin
s: = 0;
for i:=1 to n do s:=s+A[i]*B[i];
Scal_V: = s;
end ;
End. {Розділ ініціалізації модуля відсутній}
АЛГОРИТМИ ПОШУКУ
Алгоритми пошуку застосовуються для знаходження, наприклад, в масиві елемента з потрібними властивостями. Зазвичай розрізняють постановки задачі пошуку для першого і останнього входження елемента. У всіх нижче викладених алгоритмах будемо вважати, що проводиться пошук в масиві A з N цілих чисел елемента, рівного X.
ЛІНІЙНИЙ ПОШУК
Линейный поиск осуществляется циклом ( while или repeat - until ) с двойным условием. Перша умова контролює індекс на приналежність масиву, наприклад, (i <= N). Друга умова - це умова пошуку. В нашем случае в цикле while это условие продолжения поиска: (A[i]<>X), а в цикле repeat - until это условие завершения поиска: (A[i]=X). У тілі циклу зазвичай пишеться тільки один оператор: зміна індексу в масиві.
Після виходу з циклу необхідно перевірити, за яким з умов ми вийшли. В операторе if обычно повторяют первое условие цикла. Можно говорить об успешном поиске с циклом while при выполнении этого условия, а с циклом repeat - until при его нарушении.
ПРИМЕР : Линейный поиск
program Poisk1;
var A: array [1..100] of integer;
N, X, i: integer;
begin
read (N); {N<=100}
for i:=1 to N do read (A[i]);
read (X);
i: = 1; {i: = 0;}
while (i<=N) and (A[i]<>X) do i:=i+1;
{ repeat i:=i+1; until (i>N) or (A[i]=X);}
if i<=N then write ('первое вхождение числа ',X,'
в масив A на ', i,' місці ')
else write ('не нашли');
end .
При пошуку останнього входження після введення повинні йти оператори:
i: = N; {i: = N +1;}
while (i>=1) and (A[i]<>X) do i:=i-1;
{ repeat i:=i-1; until (i<1) or (A[i]=X);}
if i>=1 then write ('последнее вхождение числа ',X,' в массив A на ',i,' месте')
else write ('не нашли');
ПОШУК з бар'єром
Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти кожен раз в циклі умова, пов'язане з межами масиву. Це можна забезпечити, встановивши в масив так званий бар'єр: будь-який елемент, який задовольняє умові пошуку. Тим самим буде обмежено зміна індексу.
Вихід з циклу, в якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Таким чином, після виходу з циклу перевіряється, не бар'єр ми знайшли? Обчислювальна складність пошуку з бар'єром менше, ніж у лінійного пошуку, але також є величиною того ж порядку, що і N - кількість елементів масиву.
Існує два способи установки бар'єру: додатковим елементом або замість крайнього елемента масиву.
ПРИМЕР : Поиск с барьером
program Poisk2a;
var A: array [1..101] of integer;
N, X, i: integer;
begin
read (N); {N<=100}
for i:=1 to N do read (A[i]);
read (X);
A [N +1]: = X; {установка бар'єру додатковим елементом}
i: = 1; {i: = 0;}
while A[i]<>X do i:=i+1;
{ repeat i:=i+1; until A[i]=X;}
if i<=N then write ('первое вхождение числа ',X,' в массив A на ',i,' месте')
else write ('не нашли');
end .
program Poisk2b;
var A: array [1..100] of integer;
N, X, i, y: integer;
begin
read (N); {N<=100}
for i:=1 to N do read (A[i]);
read (X);
y: = A [N]; {збереження останнього елемента}
A [N]: = X; {установка бар'єру на останнє місце масиву}
i: = 1; {i: = 0;}
while A[i]<>X do i:=i+1;
{ repeat i:=i+1; until A[i]=X;}
if (i<N) or (y=X) then
write ('первое вхождение числа ',X,' в массив A на ',i,' месте')
else write ('не нашли');
A [N]: = y; {відновлення останнього елемента масиву}
end .
Двійкові (бінарний) ПОШУК
Алгоритм двійкового пошуку можна використовувати для пошуку елемента із заданою властивістю тільки в масивах, упорядкованих по цій властивості. Так при пошуку числа з заданим значенням необхідно мати масив, упорядкований за зростанням або за спаданням значень елементів. А, наприклад, при пошуку числа із заданою сумою цифр масив повинен бути впорядкований за зростанням або за спаданням сум цифр елементів.
Ідея алгоритму полягає в тому, що масив щоразу ділиться навпіл і вибирається та частина, де може знаходитися потрібний елемент. Розподіл триває поки частина масиву для пошуку більше одного елемента, після чого залишається перевірити цей залишився елемент на виконання умови пошуку.
Існують дві модифікації цього алгоритму для пошуку першого і останнього входження. Все залежить від того, як вибирається середній елемент: округленням в меншу або більшу сторону. У першому випадку середній елемент належить до лівої частини масиву, а в другому - до правої.
У процесі роботи алгоритму двійкового пошуку розмір фрагмента, де цей пошук повинен тривати, щораз зменшується приблизно в два рази. Це забезпечує обчислювальну складність алгоритму порядку логарифма N за основою 2, де N - кількість елементів масиву.
ПРИМЕР : Поиск в упорядоченном по возрастанию массиве первого вхождения числа X.
program Poisk3a;
var A: array [1..100] of integer;
N, X, left, right: integer;
begin
read (N); {N<=100}
write ('введите упорядоченный по возрастанию массив');
for i:=1 to N do read (A[i]);
read (X);
left: = 1; right: = N;
{Ліва і права межа фрагмента для пошуку}
while left<right do
begin
c:=(left + right) div 2;
{Середина з округленням в меншу сторону}
if X>A[c] then
{если массив упорядочен по убыванию, то if X<A[c]}
left: = c +1
{Вибираємо праву половину без середини, змінюючи left}
else right:=c;
{Вибираємо ліву половину з серединою, змінюючи right}
end ;
if X=A[left] then {здесь left = right, но не всегда = c}
write ('первое вхождение числа ',X,' в массив A на ',left,' месте')
else write ('не нашли');
end .
ПРИМЕР : Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X.
program Poisk3b;
var A: array [1..100] of integer;
N, X, left, right: integer;
{Функція вважає суму цифр числа a, тут a - локальна змінна}
function Sum(a:integer):integer;
var s:integer;
begin
s: = 0; a: = abs (a);
while a>0 do
begin
s:=s + a mod 10;
a:=a div 10;
end ;
Sum: = s;
end ;
begin
read (N); {N<=100}
write ('введите массив, упорядоченный по возрастанию сумм цифр');
{Наприклад, для N = 4: 122, -432, 88, 593}
for i:=1 to N do read (A[i]);
read (X);
left: = 1; right: = N;
{Ліва і права межа фрагмента для пошуку}
while left<right do
begin
c:=(left+right+1) div 2;
{Середина з округленням у більшу сторону}
if X>=Sum(A[c]) then left:=c
{Вибираємо праву половину з серединою, змінюючи left}
else right:=c-1;
{Вибираємо ліву половину без середини, змінюючи right}
end ;
if X=Sum(A[left]) then {здесь left = right, но не всегда = c}
write ('последнее число с суммой цифр=',X,' равно',A[left], ' находится в массиве A на ',left,' месте')
else write ('не нашли');
end .
АЛГОРИТМИ СОРТУВАННЯ
Найпростіша задача сортування полягає в упорядкуванні елементів масиву за зростанням або спаданням. Іншим завданням є упорядкування елементів масиву у відповідності з деяким критерієм. Зазвичай в якості такого критерію виступають значення певної функції, аргументами якої виступають елементи масиву. Цю функцію прийнято називати впорядкує функцією.
Існують різні методи сортування. Будемо розглядати кожен з методів на прикладі задачі сортування за зростанням масиву з N цілих чисел.
СОРТУВАННЯ ВИБОРОМ
Ідея методу полягає в тому, що знаходиться максимальний елемент масиву і міняється місцями з останнім елементом (з номером N). Потім, максимум шукається серед елементів з першого до передостаннього і ставиться на N-1 місце, і так далі. Необхідно знайти N-1 максимум. Можна шукати не максимум, а мінімум і ставити його на перше, друге і так далі місце. Також застосовують модифікацію цього методу з одночасним пошуком максимуму і мінімуму. В этом случае количество шагов внешнего цикла N div 2.
Обчислювальна складність сортування вибором - величина порядку N * N, що зазвичай записують як O (N * N). Це пояснюється тим, що кількість порівнянь при пошуку першого максимуму дорівнює N-1. Потім N-2, N-3, і так далі до 1, разом: N * (N-1) / 2.
ПРИМЕР : Сортировка выбором по возрастанию массива A из N целых чисел.
program Sort_Vybor1;
var A: array [1..100] of integer;
N, i, m, k, x: integer;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
for k:=n downto 2 do { k - количество элементов для поиска max }
begin
m: = 1; {m - місце max}
for i:=2 to k do if A[i]>A[m] then m:=i;
{Міняємо місцями елементи з номером m і номером k}
x: = A [m]; A [m]: = A [k]; A [k]: = x;
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
ПРИМЕР : Та же задача с одновременным выбором max и min.
program Sort_Vybor2;
var A: array [1..100] of integer;
N, i, m, k, x, p: integer;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
for k:=1 to n div 2 do { k - номер пары max и min }
begin
m: = k; {m - місце max}
p: = k; {p - місце min}
{Max і min шукаються серед елементів з k до n-k +1}
for i:=k+1 to n-k+1 do
if A[i]>A[m] then m:=i
else if A[i]<A[p] then p:=i;
{Міняємо місцями елементи з номером p і номером k}
x: = A [p]; A [p]: = A [k]; A [k]: = x;
if m=k then m:=p;
{Якщо max стояв на місці k, то зараз він на місці p}
{Міняємо місцями елементи з номером m і номером n-k +1}
x: = A [m]; A [m]: = A [n-k +1]; A [n-k +1]: = x;
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
СОРТУВАННЯ Обмінів (методом "бульбашки")
Ідея методу полягає в тому, що послідовно порівнюються пари сусідніх елементів масиву. Якщо вони розташовуються не в тому порядку, то робимо перестановку, міняючи місцями пару сусідніх елементів. Після одного такого проходу на останньому місці номер N виявиться максимальний елемент ("сплив" перший "бульбашка"). Наступний прохід повинен розглядати елементи до передостаннього і так далі. Всього потрібно N-1 прохід. Обчислювальна складність сортування обміном O (N * N).
ПРИМЕР : Сортировка обменом по возрастанию массива A из N целых чисел. (Базовый вариант)
program Sort_Obmen1;
var A: array [1..100] of integer;
N, i, k, x: integer;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
for k:=n-1 downto 1 do { k - количество сравниваемых пар }
for i:=1 to k do
if A[i]>A[i+1] then
{Міняємо місцями сусідні елементи}
begin x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
Можна помітити, що якщо під час виконання чергового проходу в сортуванні обміном не вироблено жодної перестановки, то це означає, що масив вже впорядкований. Таким чином, можна модифікувати алгоритм, щоб наступний прохід робився тільки при наявності перестановок у попередньому.
ПРИМЕР : Сортировка обменом с проверкой факта перестановки.
program Sort_Obmen2;
var A: array [1..100] of integer;
N, i, k, x: integer; p: boolean;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
k: = n-1; {кількість пар при першому проході}
p: = true; {логічна змінна p істинна, якщо були
перестановки, тобто потрібно продовжувати сортування}
while p do
begin
p: = false;
{Початок нового проходу. Поки перестановок не було.}
for i:=1 to k do
if A[i]>A[i+1] then
begin
x: = A [i]; A [i]: = A [i +1]; A [i +1]: = x;
{Міняємо елементи місцями}
p: = true; {і запам'ятовуємо факт перестановки}
end ;
k: = k-1;
{Зменшуємо кількість пар для наступного проходу}
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
Наступна модифікація алгоритму сортування обміном виходить при запам'ятовуванні місця останньої перестановки. Якщо при черговому проході останньою парою елементів, які помінялися місцями, були A [i] і A [i +1], то елементи масиву з i +1 до останнього вже стоять на своїх місцях. Використання цієї інформації дозволяє нам зробити кількість пар для наступного проходу рівним i-1.
ПРИМЕР : Сортировка обменом с запоминанием места последней перестановки.
program Sort_Obmen3;
var A: array [1..100] of integer;
N, i, k, x, m: integer;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
k: = n-1; {кількість пар при першому проході}
while k>0 do
begin
m: = 0;
{Поки перестановок на цьому проході немає, місце дорівнює 0}
for i:=1 to k do
if A[i]>A[i+1] then
begin
x: = A [i]; A [i]: = A [i +1]; A [i +1]: = x; {міняємо елементи місцями}
m: = i; {і запам'ятовуємо місце перестановки}
end ;
k: = m-1; {кількість пар залежить від місця останньої перестановки}
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
ШЕЙКЕРНАЯ СОРТУВАННЯ
Цей алгоритм, по суті, є модифікацією сортування обміном. Відмінність полягає лише в тому, що якщо в сортуванні обміном проходи здійснювалися тільки в одному напрямку, то тут напрямок щоразу змінюється. У шейкерной сортування також можна перевіряти факт перестановки або запам'ятовувати місце останньої перестановки. В базовом алгоритме количество двойных проходов равно N div 2. Обчислювальна складність шейкерной сортування O (N * N).
ПРИМЕР : Шейкерная сортировка по возрастанию массива A из N целых чисел.
program Shaker;
var A: array [1..100] of integer;
N, i, k, x, j, d: integer;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
d: = 1; i: = 0;
for k:=n-1 downto 1 do { k - количество сравниваемых пар }
begin
i: = i + d;
for j:=1 to k do
begin
if (A[i]-A[i+d])*d>0 then
{Міняємо місцями сусідні елементи}
begin x:=A[i]; A[i]:=A[i+d]; A[i+d]:=x; end ;
i: = i + d;
end ;
d: =- d;
{Міняємо напрямок руху на протилежний}
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
СОРТУВАННЯ ВКЛЮЧЕННЯМ
Ідея даного методу полягає в тому, що кожного разу, маючи вже впорядкований масив з K елементів, ми додаємо ще один елемент, включаючи його у масив таким чином, щоб впорядкованість не порушилася. Сортування може проводитися одночасно з введенням масиву.
На початку сортування впорядкована частина масиву містить тільки один елемент, який вводиться окремо або, якщо масив вже є, вважається єдиним, хто стоїть на потрібному місці. Різні методи пошуку місця для включається елемента призводять до різних модифікацій сортування включенням.
При використанні лінійного пошуку обчислювальна складність сортування включенням становить O (N * N), а при використанні двійкового пошуку - O (N * LogN) (мається на увазі логарифм за основою 2).
ПРИМЕР : Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.
program Sort_Include1;
var A: array [1..100] of integer;
N, i, k, x: integer;
begin
write ('количество элементов массива ');
read (N);
read (A[1]); { for i:=1 to n do read (A[i]);}
{K - кількість елементів в упорядкованій частині масиву}
for k:=1 to n-1 do
begin
read (x); {x:=A[k+1];}
i: = k;
while (i>0) and (A[i]>x) do
begin
A [i +1]: = A [i];
i: = i-1;
end ;
A [i +1]: = x;
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
ПРИМЕР : Сортировка по возрастанию массива A из N целых чисел включением с двоичным поиском.
program Sort_Include2;
var A: array [1..100] of integer;
N, i, k, x, c, left, right: integer;
begin
write ('количество элементов массива '); read (N);
read (A[1]); { for i:=1 to n do read (A[i]);}
{K - кількість елементів в упорядкованій частині масиву}
for k:=1 to n-1 do
begin
read (x); {x:=A[k+1];}
left: = 1; right: = k;
{Ліва і права межа фрагмента для пошуку}
while left<right do
{Двійковий пошук останнього входження}
begin
c:=(left+right+1) div 2;
{Середина з округленням у більшу сторону}
if x>=A[c] then left:=c
{Беремо праву половину з серединою}
else right:=c-1; {берем левую половину без середины}
end ;
if x>=A[left] then left:=left+1;
{Зрушуємо на 1 вправо частину масиву, звільняючи місце
для включення x}
for i:=k downto left do A[i+1]:=A[i];
A [left]: = x;
end ;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .

СОРТУВАННЯ Хоара
Цю сортування також називають швидкої сортуванням. Метод був розроблений в 1962 році професором Оксфордського університету К. Хоаром. Це прекрасний приклад використання рекурсії. Розглянемо принцип роботи алгоритму при упорядкуванні масиву A з N елементів за зростанням.
Значення якого-небудь елемента, зазвичай центрального, записується в змінну X. Проглядаються елементи масиву. При русі зліва-направо шукаємо елемент більше або дорівнює X. А при русі праворуч-ліворуч шукаємо елемент менше або рівний X. Знайдені елементи міняються місцями і триває зустрічний пошук.
Після цього масив виявиться розділеним на дві частини. У першій знаходяться елементи менше або рівні X, а праворуч - більше або рівні X. Можна замінити вихідну завдання про сортування масиву A на дві підзадачі про сортування отриманих частин масиву.
Обчислювальна складність одного виклику даного рекурсивного алгоритму пропорційна кількості елементів сортованого фрагмента масиву. У кращому випадку поділ на частини здійснюється навпіл, тому обчислювальна складність всього алгоритму швидкого сортування складає величину порядку N * LogN (логарифм за основою 2). Обчислювальна складність у середньому того ж порядку.
ПРИМЕР : Быстрая сортировка по возрастанию массива A из N целых чисел.
program Quick_Sort;
var A: array [1..100] of integer;
N, i: integer;
{У процедуру передаються ліва і права межі сортованого фрагмента}
procedure QSort(L,R:integer);
var X,y,i,j:integer;
begin
X:=A[(L+R) div 2];
i: = L; j: = R;
while i<=j do
begin
while A[i]<X do i:=i+1;
while A[j]>X do j:=j-1;
if i<=j then
begin
y: = A [i]; A [i]: = A [j]; A [j]: = y;
i: = i +1; j: = j-1;
end ;
end ;
if L<j then QSort(L,j);
if i<R then QSort(i,R);
end ;
begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
QSort (1, n); {порядок елементи з першого до n-го}
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end .
СОРТУВАННЯ З ВИКОРИСТАННЯМ ВЕКТОРА ІНДЕКСІВ
На відміну від усіх раніше викладених методів сортування, цей не є самостійним алгоритмом, а являє собою ідею, яку можна застосовувати до будь-якого з них. Ідея полягає в тому, що вводиться додатковий масив B, який прийнято називати вектором індексів. Числа в нем говорят о том, в каком порядке нужно смотреть на элементы из A, например: Массив A : 4 7 Массив B : 3 1 4 2 { A[3] A[1] A[4] A[2] }
На початку програми у вектор індексів B записуються послідовно натуральні числа від 1 до N. При роботі будь-якої сортування замість елемента A [i] звертаються до елемента A [B [i]]. Це зроблено для того, щоб міняти місцями не елементи масиву A, а їх індекси, тобто елементи масиву B.
МОДУЛЬ CRT (основні можливості)
Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl (Turbo Pascal Library). Для подключения модуля достаточно написать uses Crt . Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой.
На екрані використовуються два активних кольору: колір тексту і колір фону. Их можно установить с помощью процедур TextColor и TextBackground , которые имеют по одному параметру: целому числу, задающему номер цвета. Для кольору тексту використовуються числа від 0 до 15, а для кольору фону - від 0 до 7. Обидві ці процедури мають вплив тільки на наступний висновок.
Координати на екрані задаються наступним чином. Лівий верхній кут має координати (1,1), а правий нижній (80,25). Можно вводить относительные координаты, объявляя окно с помощью процедуры Window (x1,y1,x2,y2), где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты. Вернуться к работе со всем экраном можно, написав Window (1,1,80,25). С помощью процедуры GotoXY (x,y) можно установить курсор в заданную позицию окна, а с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона.
Модуль Crt позволяет осуществлять контроль клавиатуры. Відомо, що інформація про натиснутих клавішах надходить спочатку в буфер клавіатури і тільки потім прочитується комп'ютером. Також відомо, що клавіші і комбінації клавіш діляться на звичайні, і керуючі. У результаті натиснення звичайної клавіші в буфер клавіатури надходить її код, який може бути від 1 до 255, а при натисканні клавіші керуючої в буфер клавіатури надходить два коди, перший з яких 0. Функция KeyPressed не имеет параметров и возвращает истинный результат если буфер не пуст. При цьому вміст буфера не змінюється. Функция ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу символ (тип char), код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре.

ЛІТЕРАТУРА
1. Абрамов А.Г., Трифонов Н.П., Трифонова Г.М. Введення в мову Паскаль. М., Наука, 1988.
2. Абрамов С.О., Гнєздилова Г.Г., Капустіна Є.М., Селюн М.І. Завдання з програмування. М., Наука, 1988.
3. Ахо А., Хопкрофта Дж., Ульман Дж. Побудова та аналіз обчислювальних алгоритмів. М., Мир, 1979.
4. Вірт Н. Алгоритми і структури даних. М., Мир, 1989.
5. Епанешников А., Епанешников В. Програмування в середовищі Turbo Pascal 7.0. М., Діалог-Міфи, 1993.
6. Зуєв Є.А. Система програмування Turbo Pascal. М., Радіо і зв'язок, 1992.
7. Зуєв Є.А. Програмування на мові Турбо-Паскаль 6.0,7.0. М. Радіо і зв'язок. Веста. 1993.
8. Йодан Е. Структурне програмування та конструювання програм. М.: Світ, 1979.
9. Кенін А.М., Печонкіна Н.С. Робота на IBM PC. М., АТ "Книга і бізнес", 1992.
10. Кнут Д. Мистецтво програмування на ЕОМ. М.: СВІТ, т.1, 1976; т.2, 1977; т.3, 1978.
11. Липський В. Комбінаторика для програмістів. М., Мир, 1988.
12. Майерс Г. Мистецтво тестування програм. М.: Фінанси і статистика, 1982. Гласс Р., Нуазі Р. Супровід програмного забезпечення, М.: Світ, 1983.
13. Пильщиків В.М. Збірник вправ з мови Паскаль. М., Наука, 1989.
14. Поляков Д.Б., Круглов І.Ю. Програмування в середовищі Турбо Паскаль (версія 5.5). Вид-во МАІ, 1992.
15. Рейнгольд Е., Нівергельт Ю., Део М. Комбінаторні алгоритми. М., Мир, 1980.
16. Фаронов В.В. Турбо Паскаль 7.0. Початковий курс. М., Нолидж, 1997.
17. Фаронов В.В. Турбо Паскаль 7.0. Практика програмування. М., Нолидж, 1997.
18. Шень А. Програмування: Теореми та завдання. М., МЦНМО, 1995.
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Книга
156.1кб. | скачати


Схожі роботи:
Мови та технологія програмування
Мови програмування 2
Мови програмування
Програмування в LE-технологія Microsoft Windows
Мови та системи програмування
Алгоритмічні мови програмування
Операції мови програмування С
Мови програмування їх класифікація та розвиток
Історія мови програмування Lisp
© Усі права захищені
написати до нас