_TPLab_My_Посібник

If Chr (i) In bukva Then Writeln (Chr (J)); {стандартна функція Chr (i) повертає символ під номером i } { в таблиці кодів ASCII }

Проілюструємо прийоми роботи з множинами на прикладі задачі виділення з першихN цілих чисел всіх простихчисел.

Для розв’язання цієї задачі скористаємось алгоритмом відомого методу, який називається «решето Ератосфена»(є ще «решето Сундарама» та «решето Аткіна»).

1. Аналіз задачі та математична модель.

Просте число – це натуральне число, яке має рівно два натуральних дільники – лише 1 і саме число. Математичну модель можемо записати в наступному вигляді:

А = {x | x ≤ N; (x div 1 = x) And (x mod x =0) }

Ще потрібно сформулювати умову виключення кратних чисел. Запропонуйте, як це записати?

2.Обґрунтування алгоритму. Суть алгоритму «решетаЕратосфена»полягає в наступному: 1) в множині натуральних чисел від 2 до N вибираємо 2 як перше просте число;

2) закреслюємо всі числа, кратні 2; 3) за наступне просте число вибираємо перше з незакреслених і більших 2 чисел;

4) закреслюємо всі числа, кратні вибраному простому числу; 5) повторюємо кроки 3)-4) поки не переберемо всі елементи заданої множини натуральних чисел. Всі

незакреслені елементи – прості числа.

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

– поки початкова множина не порожня; внутрішній цикл – видалення кратних з початкової множини і включення простого числа нову множину; ще один внутрішній цикл – для вибору наступного простого числа. Також в циклі будемо виводити знайдені прості числа – елементи нової множини.

3.Блок-схема алгоритму представлена на Рис.1.

71

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Begin

Exclude (BeginSet, n1);

Include (PrimerSet, next);

{Отримуємо наступне просте, яке є першим невидаленим }

КОНТРОЛЬНІ ЗАПИТАННЯ:

1.До якого типу даних відносяться множини?

2.Чи вірно описана множина? Якщо ні, то чому?

Var Bukva: set of (‘n’, ‘e’, ‘o’, ‘i’, ‘j’);

3.Який результат перерізу двох множин: [3..7,17,25..35] та [4,9]?

4.Який результат наступних операцій:

1)['A','B'] = ['A','C']

2)['A','B'] <> ['A','C']

3)['B'] <= ['B','C']

4)['C','D'] >= ['A']

5)2 in [1, 3, 6]

6)[‘A’..’D’, ‘K’..’M’] + [‘D’..’K’]

7)[7, 1, 3..6] = [1..7]

8)15 IN [1..10]

9)[‘A’, ‘B’, ‘C’] = [‘B’, ‘C’, ‘A’]

10)[3, 4, 6] <= [2..8]

11)[ ] >= [1, 2]

12)SUCC (‘C’) IN [‘B’ .. ‘D’]

13)[2] <> [2, 2, 2]

14)16 IN [16]

15)[1..14] * [5, 12..60] + [4..7] – [2..16] * [6]

5.Як здійснюється виведення значень елементів множини?

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ.

Варіанти завдань

1.Складіть програму, яка з діапазону [1..255] записує в цілочисельні множини A,B,C відповідно числа, кратні 3, 5 та 7 та виводить на екран елементи, що належать A*B, A+B, A-C.

2.Складіть програму для знаходження в діапазоні [1..255] всіх чисел, які можуть бути подані у виді 7i- 3, але не можуть бути подані у виді j2+2, де i, j ≥ 0.

3.Знайти суму цифр у рядку символів. Серед символів рядка зустрічаються символи-цифри.

4.Сформувати та вивести множину, в яку входять тільки прописні латинські літери, що містяться у заданому рядку.

5.З масиву чисел 0-100 видалити у множину М3 усі числа, що кратні 3. Роздрукувати множину М3 та множину – залишок масиву, що залишилася після процедури видалення.

6.Знайти добуток цифр рядка. Рядок містить будь-які символи.

7.Визначити кількість різних цифр у рядку.

73

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

8.Вивести всі голосні, що міститься в рядку.

9.Вивести всі розділові знаки, що міститься в рядку.

10.Надрукувати всі різні символи рядка, що складаються з малих латинських літер, в алфавітному порядку.

11.Заданий текст з малих латинських літер. Роздрукувати символи, що входять у текст не менше трьох разів.

12.Складіть програму, яка формує і виводить на екран набори випадкових чисел для гри в «Спортлото

5з 36».

13.Задана послідовність слів з російських малих літер, між сусідніми словами – кома, а за останнім словом – крапка. Вивести в алфавітному порядку всі приголосні літери, що входять тільки в одне слово.

14.Задана послідовність слів з малих латинських літер, між сусідніми словами – кома, а за останнім словом – крапка. Вивести в зворотному алфавітному порядку всі голосні літери, що входять до двох і більше слів.

15.Складіть програму для побудови множини і визначення серед 100 випадкових цілих чисел з діапазону [1..1000] таких, остання цифра у десятковому записі яких є 3 або 7.

16.Задана множина програм (мінімум 7), які можуть бути встановлені на комп’ютерах і відомі (побудувати) різні множини програм, встановлених на кожному комп’ютері (мінімум 3). Складіть програму, яка будує множини програм і виводить на екран назви програм, які:

a)встановлені на всіх комп’ютерах;

b)встановлені хоча б на одному комп’ютері;

c)відсутні на всіх комп’ютерах.

17.Умова завдання 13.

a)відсутні на першому комп’ютері;

b)встановлені на першому і другому комп’ютерах;

c)встановлені другому і третьому комп’ютерах але відсутні на першому.

18.Умова завдання 13.

a)встановлені на першому комп’ютері але відсутні на другому;

b)відсутні на другому і третьому комп’ютерах;

c)відсутні на третьому комп’ютері.

19.Задана множина видів спорту (мінімум 5), секції з яких працюють в університеті, та відомі (побудувати) різні множини студентів, які займаються в кожній секції. Складіть програму, яка будує множини студентів і виводить на екран прізвища студентів, які:

a)займаються тільки в одній секції;

b)займаються в будь-яких двох секціях;

c)займаються в першій секції але не займаються в п’ятій секції.

20.Умова завдання 16.

a)займаються тільки в першій секції;

b)займаються в другій і третій секціях, але не займаються в четвертій;

c)займаються в другій секції але не займаються в третій секції.

21.Умова завдання 16.

a)займаються в першій і четвертій секціях;

b)не займаються в другій, третій і п’ятій секціях;

c)займаються в другій секції але не займаються в третій секції.

22.У зростаючому порядку вивести всі цілі числа з діапазону 1..100, що подаються у вигляді 2n+2m, де n, m > 0.

23.Складіть програму формування двох множин символів на основі двох рядків, введених користувачем, та виведення тільки тих символів, які містяться в обох рядках.

24.Складіть програму, яка з діапазону [1..255] записує в цілочисельні множини A i B відповідно числа, кратні 2 і 6 та виводить на екран елементи, що належать A*B, A+B, A-C.

25.Складіть програму для побудови множини і визначення серед 100 випадкових цілих чисел з діапазону [1..1000] таких, перша цифра у десятковому записі яких є 5 або 6.

74

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЛАБОРАТОРНА РОБОТА № 8 Проектування та відлагодження програм опрацювання даних з використанням процедур та

функцій.

МЕТА РОБОТИ: Навчитись проектувати алгоритми та програми опрацювання даних з використанням підпрограм (процедур та функцій) користувача.

ЗАВДАННЯ:

Спроектувати алгоритми та програми розв’язання задач з використанням процедур та функцій користувача за варіантами завдань, номери яких визначає викладач.

МЕТОДИЧНІ ВКАЗІВКИ

1.Перед виконанням роботи необхідно пригадати:

логічну структуру програми на мові Turbo Pascal;

правила опису типів даних;

правила запису виразів;

синтаксис основних операторів;

синтаксис опису та правила застосування стандартних (бібліотечних) процедур і функцій.

2.Перед виконанням цієї роботи необхідно вивчити:

правила опису процедур та функцій, включаючи синтаксис опису формальних параметрів (параметрів-змінних та параметрів значень);

правила локалізації імен;

способи передачі параметрів у підпрограму;

3.Відлагодження програми здійснити шляхом контролювання та перевірки правильності проміжних результатів при покроковому виконанні програми з трасуванням підпрограм (Run → Trace info).

4.Перевірка правильності роботи програми здійснюється шляхом аналізу отриманих результатів та порівняння вихідного і результуючих рядків.

ВІДОМОСТІ З ТЕОРІЇ

При розробці програм іноді з’являються повторювані групи дій або виникає необхідність поділити програму на окремі модулі. Для цього застосовують підпрограми.

Означення 1. Підпрограма (англ. subroutine - підпорядок) – це іменована, логічно завершена група операторів мови, яка реалізує певний алгоритм опрацювання даних і допускає звернення до себе за іменем (виклик з метою виконання) довільну кількість разів з різних місць основної програми

Підпрограми мають таку ж логічну структуру як і основна програма на мові Turbo Pascal. В Turbo Pascal розрізняють два види підпрограм: функції та процедури.

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

Процедура не може використовуватись як операнд у виразах. Активізація процедури (виклик) здійснюється за її іменем.

Означення 3. Функція – це підпрограма, яка повертає в основну програму (в точку виклику) результат ординального, дійсного, рядкового або посилального типу як значення свого імені.

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

Ще однією відмінністю функції від процедури є те, що ім'я функції може використовуватись як операнд у виразах (зокрема, в якості правої частин оператора присвоювання).

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

Правила локалізації імен (або правила доступності об’єктів):

1.Імена об’єктів, описані в деякій підпрограмі є доступними в межах даної підпрограми і вкладених в неї підпрограмах.

2.Імена всіх об’єктів в межах підпрограми, в якій вони оголошені, повинні бути унікальними і не можуть співпадати з іменем самої підпрограми.

75

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

3. Імена, локалізовані в підпрограмі (тобто, імена локальних об’єктів, описаних в самій підпрограмі) можуть збігатися з раніше оголошеними глобальними іменами. У цьому випадку вважається, що локальне ім’я «закриває» (екранує) глобальне і робить його недоступним.

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

В мовах програмування високого рівня для обміну даними між програмою та її підпрограмами використовується механізм параметрів.

Означення 4. Параметри – це спеціальні об’єкти (змінні), які використовуються для контрольованої передачі даних у підпрограму і повернення результатів в основну програму.

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

Кількість і типи формальних і фактичних параметрів повинні співпадати з точністю до їх порядку в списках. Turbo Pascal контролює відповідність між кількістю і типами формальних і фактичних параметрів, а контроль за правильним порядком запису фактичних параметрів при звертання до підпрограми покладається на користувача.

Наприклад, якщо заголовок підпрограми такий:

Procedure Test (a : Real; b : String; c : Integer) : Byte;

то допустимим буде наступний виклик такої підпрограми з тіла програми:

Test (x, y, z); , де x : Real; y : String; z : Integer;

Існує кілька способів передачі параметрів у підпрограму, але в сучасних мовах програмування високого рівня (зокрема в Turbo Pascal) застосовуються два:

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

Передача параметрів за посиланням. В цьому випадку формальному параметру присвоюється значення фактичного параметра. Тобто, в підпрограму передається адреса комірки пам’яті (посилання), в якій зберігається значення фактичного параметра. Будь-яка зміни формального параметра в процесі виконання підпрограми є змінами фактичного параметра – отже з’являється можливість передачі даних з підпрограми в основну програму. При застосуванні цього способу передачі параметрів додаткова пам'ять не виділяється.

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

за допомогою параметрів-змінних підпрограма передає результати своєї роботи в основну програму;

якщо формальний параметр підпрограми описаний як параметр-значення, то в якості відповідного фактичного параметра можна використовувати довільний вираз;

параметр-константа не копіюється в додаткову тимчасову пам'ять, але будь-які його зміни в підпрограмі неможливі (контролюється компілятором);

76

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

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

чим менше параметрів оголошено параметрами-змінними і чим менше в підпрограмі використовується глобальних змінних, тим менше небезпека одержання непередбачуваних програмістом побічних ефектів, пов'язаних з викликом підпрограми і тим простіша програма в розумінні і відлагодженні.

Таким чином, формальний параметр підпрограми може бути або параметром-значенням, або параметром-змінною, або параметром-константою.

Всі процедури і функції мови Turbo Pascal діляться на дві групи – вбудовані (стандартні) та визначені користувачем. Перші входять до складу мови і викликаються для виконання за фіксованим іменем. Другі розробляються та іменуються самим користувачем.

Всі стандартні процедури і функції розміщуються в спеціалізованих бібліотечних модулях, які мають системні імена. В систему Turbo Pascal версії 7.0 входять модулі System, Crt, Dos, Graf, Graf3, Overlay, Printer, Strings, Turbo3, WinAPI, WinCrt, WinDos, WinPrn, WinProcs, WinTypes і спеціалізована бібліотека TurboVision. Модуль System підключається за замовчуванням (автоматично), а решту модулів повинен підключати програміст за допомогою зарезервованого слова Uses одразу після заголовку програми. Наприклад: Uses Crt, Strings;

ПРОЦЕДУРИ І ФУНКЦІЇ КОРИСТУВАЧА.

Синтаксис опису процедури:

Procedure <ім’я_процедури> [(<cп.форм.парам.>)] [Директива компілятора] [<Декларативна частина – опис локальних об'єктів>]

Begin

<Виконавча частина - оператори>

End;

Синтаксис опису функції:

Function < ім’я_функції> [ (<cп.форм.парам.>)]: <тип>; [Директива компілятора] [<Декларативна частина – опис локальних об'єктів>]

Begin

<Виконавча частина - оператори>

End;

Тут: <сп_форм_параметрів > - список формальних параметрів, <тип> - тип результату, який повертає функція, [Директива компілятора] - одна із стандартних локальних директив компілятора - Assembler, External, Far, Forward, Inline, Interrupt, Near.

ПАРАМЕТРИ ПРОЦЕДУР І ФУНКЦІЙ КОРИСТУВАЧА.

Якщо формальні параметри описуються як параметри-змінні, то перед ними необхідно ставити зарезервоване слово Var, а якщо як параметри-константи – слово Const, наприклад:

Procedure MyProc (Var a: Real; b: Real; Const c: String);

Типом будь-якого параметра в списку формальних параметрів може бути тільки стандартний або попередньо (раніше) оголошений тип.

Тому не можна, наприклад, оголосити наступну процедуру:

Procedure MyProc (Маs: Array [1..10] Of Real);

так як в списку формальних параметрів фактично оголошується тип-діапазон, який вказує границі індексів масиву.

Параметри-масиви і параметри-рядки.

Якщо в підпрограму потрібно передати деякий елемент масиву, то це здійснюється одним з вищеописаним способом (передача як параметр-значення чи параметр-змінна), але якщо в підпрограму передається весь масив, то необхідно спочатку описати його тип.

77

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Наприклад:

Type Mas_type = Array [1..10] Of Real;

Procedure MyProc (Mas: Mas_type);

.......

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

Type S1 = String [20] ;

S2 = String [30] ;

Function St (S: S1): S2;

.......

Передати в підпрограму одномірний масив (а, отже, і рядок) змінної довжини можна з використанням нетипізованих параметрів.

Параметр вважається нетипізованим, якщо тип формального параметра-змінної в заголовку підпрограми не зазначений, при цьому відповідний йому фактичний параметр може бути змінної будьякого типу. Нетипізованими можуть бути тільки параметри-змінні.

Версія Turbo Pascal 7.0 підтримує так названі відкриті масиви, за допомогою яких легко вирішити проблему передачі підпрограмі одномірних масивів змінної довжини.

Відкритий масив являє собою формальний параметр підпрограми, що описує базовий тип елементів масиву, але не визначає його розмірність і границі:

Procedure MyProc (OpenArray: Array of Integer);

Всередині підпрограми такий параметр трактується як одномірний масив з нульовою нижньою границею. Верхня границя відкритого масиву повертається функцією HІGH. Використовуючи 0 як мінімальний індекс і значення, що повертає функцією HІGH, як максимальний індекс, підпрограма може обробляти одномірні масиви довільної довжини.

Якщо, наприклад, в процедуру формування (заповнення) масиву передати як параметр-змінну відкритий масив довжиною n

Procedure ArrayIn (OpenArray : Array Of Integer; n : Integer); ,

то процедура сформує і передасть в основну програму масив довжиною n+1.

Виклик підпрограми здійснюється за іменем та необов’язковим набором параметрів – списком фактичних параметрів.

Виклик процедури:

Procedure <ім’я_процедури> [(<cп.факт.парам.>)];

Виклик функції:

< ім’я_змінної> := < ім’я_функції> [ (<cп. факт.парам.>)];

Приклад тривіальної програми з використанням процедури і функції:

78

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ.

Завдання 1. Процедури.

Модифікувати свою програму сортування масиву (лаб. роб. № 4) наступним чином:

1.Ввести три масиви різної довжини (процедура);

2.Відсортувати масиви за заданим варіантом завдання (процедура);

Завдання 2. Функції.

Обчислити визначений інтеграл від функції на трьох інтервалах методом прямокутників із заданою точністю (наприклад, ε=0,001).

МЕТОДИЧНІ ВКАЗІВКИ.

1.Використати табличні інтеграли для оперативної перевірки правильності обчислень.

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

b n

f (x)dx Sn h f (xi ),

a i 1

де h=(b-a)/n – крок розбиття (ширина i –го прямокутника), f(xi) - значення підінтегральної функції в точці xi., xi a hi h/2(середина ширини прямокутника).

3. Задана точність досягається, якщо

| Sm - Sn | < ε,

де m – нова (більша) кількість прямокутників (наприклад, m=2n). Тоді Sm приймається за шукане наближене значення інтегралу.

4. Обчислення суми S необхідно оформити у вигляді підпрограми-функції.

Додаткові завдання.

Завдання 1 (функції):

1. Обчислити значення виразу: n!m! (n m)!

2.Обчислити площу правильного n-кутника.

3.Обчислити значення виразу: sin( f (x)) cos(f (x)), де f(x) x2 2x 3

4.Обчислити значення виразу: max(x, y)

79

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

9.Обчислити значення виразу: f f (x) (x), де f (x) x2 2x

10.Підрахувати число точок, які знаходяться в крузі радіусом R з центром в початку координат; координати точок задані масивами X(100), Y(100).

Завдання 2 (процедури):

1.Підрахувати кількість нульових елементів трьох матриць.

2.Знайти найбільші елементи та їх порядкові номери масивів X(N) и Y(M)

3.Знайти медіани трикутника, сторонами якого є медіани деякого трикутника з сторонами a, b, c.

4.Обчислити суми елементів кожного стовпця матриць A и B.

5.Обчислити z = (s1+s2)/k1k2, де s1 и k1 – сума і кількість додатних елементів масиву X(N); s2 и k2 – сума і кількість додатних елементів масиву Y(M).

6.Обчислити z = (es1+es2)/k1k2, де s1 и k1 – сума і кількість від’ємних елементів масиву X(N); s2 и k2 – сума і кількість від’ємних масиву Y(M).

7.Обчислити z = (xmax-ymin)/2, де xmax – максимальний елемент масиву X(50); ymin – мінімальний елемент масиву Y(40).

8.Обчислити z = (x1+y1)/(x2-y2), де x1 и x2 – корені рівняння аx2+bx+c= 0, y1 и y2 – корені рівняння my2+ny+k = 0.

9.Визначити, який з двох трикутників, заданих координатами вершин має більшу площу і периметр.

10.Перетворити масиви X(50) і Y(60), розмістивши в них підряд тільки додатні елементи. Замість решти елементів записати нулі.

80

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)