Тема №6 СИМВОЛЬНИЙ ТИП ДАНИХ, РЯДКИ
Теоретичні відомості
Символьний тип являє собою тип даних, призначених для збереження одного символу (літери, знака або коду). Розрізняють символьні константи та змінні. Символьна константа - один символ в лапках (наприклад, ’?’, ’F’, ’7’). Символьна змінна - описується словом char.
Наприклад, рядок програми var S, Litera, CapsLitera : char; означає, що в програмі буде використано 3 символьних змінних S, Litera, CapsLitera.
В зв’язку з тим, що символи закодовані в таблиці ASCII, над ними можна виконувати операції порівняння (за кодом). Деякі символи не мають графічного зображення тому для звернення до них (а взагалі до кожного ASCII-символу) можна використати таку форму запису, яка складається із символу дієз (#) і числового коду символу, наприклад, #13. Будь-який об’єкт типу char (константа, змінна) займає 1 байт пам’яті.
До стандартних функцій над символьними даними відносять:
Chr(n) - визначення символу за порядковим номером n (ASCII-коду);
Ord(s) - визначення порядкового номера за символом s;
UpCase(s) - перетворення рядкових латинських літер у прописні.
Тип даних string (рядок) спеціально призначений для обробки рядків (ланцюжків символів). Змінна типу string складається з елементів типу char. Кажуть, що рядок - це масив символів, що компактно зберігаються. Змінні типу string можуть бути оголошені в такий спосіб:
Var
Ім'я_змінної_1 : string;
Ім'я_змінної_2 : string[n];
Тобто вказується Ім'я_змінної (ідентифікатор) і зарезервоване слово string. Якщо існує необхідність економити ресурси статичної пам’яті, в квадратних дужках вказується максимальний розмір рядка - кількість символів рядка, що можуть зберігатися в цій змінній. Якщо максимальний розмір рядка не зазначений, то він автоматично приймається рівним 255 - максимально можлива довжина рядка. Реально у пам’яті резервується на одиницю довший масив - додається нульовий елемент.
До стандартних функцій над даними типу string відносять:
· функція Length® - визначення фактичної довжини вказаного текстового рядка R (рядкової константи або змінної);
Зауваження: Ця функція читає значення нульового елементу рядка, де зберігається фактична його довжина.
· функція Copy(R,bp,k) - копіювання фраґмента деякого рядка R в інший рядок, bp - номер позиції символу, з якого треба почати копіювати, k - кількість символів для копіювання;
Зауваження: Результатом роботи функції є новий рядок.
· функція Pos(SubR,R) - визначення позиції входження деякого рядка символів SubR у заданий рядок R;
Зауваження: Дає змогу знайти тільки перше входження, якщо шуканий ланцюжок символів у заданому рядку міститься декілька разів. Дає результатом 0, якщо такий ланцюжок у рядку відсутній.
· функція Сoncat(R1,R2,R3,…) - з'єднання декількох рядків в один;
Зауваження: Результатом роботи функції є новий рядок.
· процедура Delete(R,bp,k) - з рядка R видаляє частину, де bp - номер позиції символу, з якого треба почати видаляти, k - кількість символів для видалення;
· процедура Insert(SubR,R,np) - вставка рядка SubR в рядок R, де np - номер позиції, починаючи з якої SubR буде розміщено в новому рядку R.
Зауваження: Застосування процедур Delete та Insert змінює фактичну довжину рядків.
До операцій над рядковим типом відносять порівняння (=, <>, <, >) та конкатенацію (об’єднання, позначається знаком +).
Зауваження: Вищезазначені операції над символьним та рядковим типами обумовлені тим, що кожен символ має свій зафіксований код (номер) у так званій таблиці символів ASCII. Це дає змогу впорядковувати масиви рядків.
Приклад
У тексті слова відокремлені символом пробіл. Написати програму, що змінює у найдовшому слові тексту порядок букв на протилежний, не змінюючи інші частини тексту.
Враховуючи особливості структури даних, що визначається типом string, при розробці алгоритму можна скористатися тим, що рядок складається з окремих символів (об’єктів типу char) і виконувати перегруповування символів всередині тексту. Інший підхід полягає в розбитті тексту на слова, пошук і перетворення найдовшого слова, злиття слів у вихідний рядок.
Наведемо два з багатьох можливих варіантів розв’язання цієї задачі.
У першому варіанті всі перетворення реалізовані в одному рядку.
Program p6_1;
var s:string;
n,maxd,ds,i,d,j,p,k:integer;
c:char;
Begin
readln(s);{введення початкового тексту}
s:=s+' ';{для спрощення подальших перетворень у кінець тексту дописується символ пробіл}
{пошук слів у тексті та визначення найдовшого}
n:=1;{початок першого слова}
maxd:=0;
ds:=length(s);{визначення довжини тексту}
for i:=1 to ds do{визначення в тексті початку і кінця слів}
if s[i]=' ' then{}
Begin
d:=i-n;{визначення довжини знайденого слова}
if d>maxd then{визначення найдовшого слова}
Begin
maxd:=d;
j:=n;{початок найдовшого слова}
End;
n:=i+1;{початок наступного слова}
End;
p:=(maxd div 2)-1;
k:=j+maxd-1;{кінець найдовшого слова}
for i:=0 to p do{зміна в найдовшому слові порядку букв}
Begin
c:=s[i+j];
s[i+j]:=s[k-i];
s[k-i]:=c;
End;
delete(s,ds,1);{видалення останній пробіл}
writeln(s);{виведення тексту після перетворень}
End.
Другий варіант більш технологічний, ніж перший, але й більш обмежений ресурсами пам’яті, бо використовується допоміжний рядковий масив.
Program p6_2;
var r,s:string;
b:array[1..20] of string;
n,i,j,k:integer;
Begin
readln(s);{вводиться текст}
s:=s+' ';{для спрощення обробки в його кінець додається пробіл}
k:=0;{лічильник знайдених слів}
while length(s)>0 do{доки в тексті нічого не залишиться}
Begin
n:=pos(' ',s);{знайдено пробіл, тобто знайдено кінець слова}
k:=k+1;{збільшується значення лічильника знайдених слів}
b[k]:=copy(s,1,n-1);{копіювання слова в масив}
delete(s,1,n);{видалення з тексту вже скопійованого слова}
End;
j:=1; {пошук найдовшого слова}
for i:=2 to k do
if length(b[i]) > length(b[j]) then j:=i;
r:='';{перевернення найдовшого слова}
for i:=length(b[j]) downto 1 do
r:=r+b[j,i];
b[j]:=r;
s:=b[1];{формування нового тексту з окремих слів}
for i:=2 to k do
s:=s+' '+b[i];
writeln(s);{виведення результату}
End.
Варіанти завдань
1. У рядку слова відокремлені символом пробіл. Переставити слова так, щоб вони були впорядковані за алфавітом.
2. 9-значне число закодоване у вигляді 18-символьного рядка, на кожному парному місці якого записана цифра, а на непарному - положення цієї цифри в початковому числі. Знайти в початковому числі найдовшу частину, де цифри розташовані в порядку зростання.
3. У текст, довжина якого не перевищує 80 символів, рівномірно вставити поміж словами символ пробіл, щоб його довжина дорівнювала 80.
4. У рядку слова відокремлені символом пробіл. Надрукувати тільки симетричні слова.
5. Рядок символів закодований так, що букви та числа йдуть парами (число показує місце букви в тексті). Відновити початковий текст.
6. Слова в рядку відокремлені символом пробіл. Надрукувати слова, що зустрічаються найчастіше (якщо такі є).
7. Рядок символів складається з цифр, кожна пара цифр - ASCII-код букви (двозначне число), що записаний у зворотному порядку цифр. Відновити текст.
8. У тексті поміж словами розташована кома, за останнім словом - крапка. Вивести на екран усі слова, що зустрічаються в послідовності лише один раз.
9. Про рядок символів відомо, що серед них є хоча б два символи «!». Серед символів, що знаходяться поміж першим і другим знаками «!», замінити всі символи «+» на «*».
10. Текст, що передається телеграфом, містить слова, відокремлені знаками пробіл (розділові знаки передаються спеціальними комбінаціями букв - ТЧК, ЗПТ, ВСКЛ, ВПРС). Вивести текст у звичайному вигляді.
11. Написати програму переведення числа з десяткової системи числення в шістнадцяткову.
12. У тексті, що складається з маленьких латинських букв, усі букви замінили подвоєним ASCII-кодом. Відновити з отриманого таким чином рядка цифр початковий текст.
13. У тексті визначити кількість слів, що починаються на вказану букву. Результат отримати у формі фрази: «Знайдено k слів», узгодивши закінчення з числом k.
14. У послідовності слів поміж ними розташовано не менше одного символу пробіл, закінчується текст символом крапка. Вивести тільки такі слова тексту, що відмінні від останнього слова.
15. Перетворити рядок символів за правилом: перемістити всі цифри в кінець, а інші символи на початок рядка, зберігаючи порядок взаємного розташування символів у кожній з цих двох груп.
16. Написати програму переведення числа з римської форми в десяткову (для римської нумерації мають місце позначення M=1000, D=500, C=100, L=50, X=10, V=5, I=1, CM=900, CD=400, XC=90, XL=40, IX=9, IV=4).
17. Вивести текст, видаливши з нього зайві символи пробіл, тобто з кількох розташованих поряд залишити тільки один.
18. Кожну цифру цілого числа замінили двійковим кодом, що записаний у зворотному порядку цифр. Відновити початкове число.
19. У рядку слів вставити символ пробіл після розділових знаків, якщо це необхідно.
20. Перевірити баланс скобок у арифметичному виразі за наступним алгоритмом. Порівнювати по черзі кожен символ із “(“ та з “)”. Якщо черговий символ “(“, тоді деяку числову змінну (напочатку її треба обнулити) збільшуємо на 1, якщо символ “)”, тоді зменшуємо на 1. Якщо закриваюча дужка з’явилась раніше, ніж відкриваюча, тоді значення числової змінної стане від’ємним - дужки не збалансовані, подальшу перевірку можна припинити. Якщо текст перевірений до кінця та значення змінної дорівнює 0, тоді дужки збалансовані.
21. Розділити текст на рядки, довжина яких не перевищує 20 символів. Перенесення на новий рядок є можливим лише на місці пробілу.
22. У тексті, що складається з латинських букв, кожну голосну букву замінили на наступну за алфавітом букву, а кожну приголосну букву замінили на попередню за алфавітом букву. Відновити початковий текст.
23. Перевірити, чи можна з наведеного набору символів скласти необхідний рядок.
24. У двох рядках знайти найдовшу спільну частину.
25. У рядку зберігається арифметичний вираз, що складається з чисел і знаків + та - поміж ними. Визначити значення виразу.
Запитання для контролю та самоконтролю
1. У чому полягають основні характеристики символьного та рядкового типів даних? Як вони пов’язані між собою?
2. Які обмеження існують для рядка?
3. Як вирішується проблема обробки довгих рядків?
4. Які дії використовуються над символами та рядками символів?
5. Які існують стандартні підпрограми для обробки символьних та рядкових даних? Чи можна без них обійтися?
6. У чому полягає особливість нульового елементу рядка?
7. Які можливості надає рядковий тип даних для обробки числової інформації?
8. Як за допомогою рядків організовується захист від некоректного введення?
9. Як у разі необхідності виконати перетворення числових даних в рядкові і навпаки?
10. Як виконується порівняння символьних та рядкових даних?
11. Як можна за символом отримати його код і навпаки?
12. Як можна зекономити пам'ять, описуючи об’єкти рядкового типу?
Тема № 7 ВИКОРИСТАННЯ ДОПОМІЖНИХ ПРОГРАМ
Теоретичні відомості
У випадку, коли одна й та сама послідовність дій (операторів) повинна виконуватися багаторазово на різних етапах обробки даних, раціонально (із погляду технології структурного програмування) використовувати підпрограми (тобто допоміжні програми). У мові Turbo Pascal виділяють два види підпрограм - процедури та функції. Крім того вони поділяються на стандартні (зберігаються в стандартних бібліотечних модулях компілятора мови Turbo Pascal) та нестандартні (розроблені користувачами), які в свою чергу класифікуються як внутрішні (оголошені та зберігаються в самій програмі) та зовнішні (оголошені та зберігаються за межами програми).
Загальний вигляд заголовка процедури наступний:
procedure Ім’я_процедури (Список параметрів);
Список параметрів - перелік імен для позначення вхідних даних і результатів роботи процедури з указівкою їхніх типів. Константи, змінні, типи, описані в блоці program,є глобальними стосовно підпрограми, на відміну від локальних, описаних у самій підпрограмі. Допускається розробка процедур, в яких відсутній Список параметрів.
Оператор виклику процедури має вигляд:
Ім’я_процедури (Список параметрів);
Функції - це процедури особливого виду, результатом роботи яких є деяке значення (одне), аналогічне змінній. Результат роботи функції привласнюється імені функції. Загальна структура функцій схожа зі структурою процедури, за винятком заголовка та оператора, що виконується останнім.
Заголовок функції має наступний вигляд:
function Ім’я_функціі (Список параметрів) : Тип_результату;
Оператор, що виконується останнім у функції завжди є оператором присвоєння. Він має структуру Ім’я_функціі : = вираз; . Тобто, обчислюється вираз і його значення стає значенням функції.
Як правило, виклик функції здійснюється у операторі присвоєння або до функції звертаються безпосередньо за ім’ям .
Наприклад:
y:=sin(argument);
if sin(argument)=0 then writeln(‘ котангенс не можна визначити ‘);
writeln(sin(argument));
Параметри, перераховані при описуванні процедури (функції) в Списку параметрів, називаються формальними.
Параметри, що містяться в Списку параметрів при виклику процедури (функції), називаються фактичними.
Зауваження: Якщо елементом Списку параметрів є структура даних (наприклад, масив), тоді необхідно у розділі описування типів ввести новий структурний тип і скористатись ним при описуванні цього елементу списку параметрів (див. Приклад нижче).
Усі об’єкти, що оголошені в основній програмі є по відношенню до будь-якої підпрограми глобальними. Об’єкти, оголошені у підпрограмі називають локальними, бо вони діють у межах цієї підпрограми.
Підпрограми, самі можуть вміщувати інші, вкладені підпрограми, й навіть звертатися (передавати управління) під час роботи до самих себе (насправді до своєї копії) - рекурсивні підпрограми.
Під час взаємодії основної програми та підпрограми використовується відділ пам’яті, що має назву стек (це динамічна структура даних, що організована за принципом “Останній прийшов, першим обслуговується”). У ньому компактно зберігаються дані основної програми в той час, коли управління передається підпрограмі. Враховуючи можливість використання вкладених підпрограм (різних рівнів вкладеності), стек має багаторівневу організацію. Розміри його обмежені, але є можливість їх зміни, наприклад, за допомогою спеціальної директиви компілятора.
У мові Turbo Pascal існує можливість створення користувачем власних бібліотечних модулів – програм з жорсткою структурою. Заголовок починається службовим словом unit замість program; далі йде розділ interface, де записаний перелік заголовків підпрограм, до яких дозволений доступ ззовні; далі йде розділ implementation, де розміщуються повні тексти включених до модуля підпрограм; далі йде розділ реалізації begin end. (як правило пустий). Модулі мають бути відкомпільовані зовнішнім компілятором tpc.exe (перетворені на готовий до використання tpu-файл).
Практично оволодівши використанням підпрограм при розв'язанні задач набагато легше зрозуміти зміст таких понять обєктно-орієнтованого програмування, як клас, метод та ін.
Приклад
Скласти програму для обчислення значення виразу 
, де 
та 
- максимальні елементи одновимірних масивів A і B, 
та 
- мінімальні елементи тих же масивів. Для знаходження найбільшого та найменшого елементів масивів скористатися процедурами.
1) A і B - дійсні одновимірні масиви.
2) змінній 
присвоюється перший елемент масиву A й у циклі від 2 до n порівнюють з 
. Якщо 
присвоюють 
.
3) Алгоритм:
 | |||||
 | |||||
 | |||||
4) Типи даних вибираємо наступним способом: Amax, Amin, Bmax, Bmin, z - дійсні, i, k, n, m - цілі.
5) Текст програми:
Program p7;
type matr=array[1..100] of real;
var i,k,n,m: integer;
Amax,Amin,Bmax,Bmin,z:real;
A,B: matr;
procedure nmax(c:matr;n1:integer;var cmax:real);
var i:integer;
Begin
cmax:=c[1];
for i:=2 to n1 do
if c[i]>cmax then cmax:=c[i];
End;
procedure nmin(c:matr;n1:integer;var cmin:real);
var i:integer;
Begin
cmin:=c[1];
for i:=2 to n1 do
if c[i]<cmin then cmin:=c[i];
End;
Begin
writeln('Введіть кількість елементів масиву A < 100');
Readln(n);
writeln('Введіть масив A по одному елементу через ПРОБІЛ);
for i:=1 to n do
read(A[i]);
Nmax(a,n,Amax);
Nmin(a,n,Amin);
writeln('Введіть кількість елементів масиву B < 100');
Readln(m);
writeln('Введіть масив B по одному елементу через ПРОБІЛ);
for i:=1 to m do
read(B[i]);
Nmax(b,m,Bmax);
Nmin(b,m,Bmin);
z:=Amax*Bmin+Amin*Bmax;
writeln(‘Результат:’,z);
Readln
End.
6) Тестовий приклад:
Введіть кількість елементів масиву А < 100
Введіть масив А по одному елементу через ПРОБІЛ
1 3 2
Введіть кількість елементів масиву B < 100
Введіть масив B по одному елементу через ПРОБІЛ
2 5 3 7
Результат: 1.3000000000E+01
7) Робочий розрахунок:
Введіть кількість елементів масиву А < 100
Введіть масив А по одному елементу через ПРОБІЛ
45 23 2 5 6 22
Введіть кількість елементів масиву B < 100
Введіть масив B по одному елементу через ПРОБІЛ
12 9 -2 34 5
Результат: -2.2000000000E+01
Варіанти завдань
1. Інформація про виготовлення підприємством продукції 10 видів за рік по місяцях зведена в таблицю. З’ясувати, в якому місяці середня кількість виробів найбільша. Обчислення середньомісячної кількості виробів оформити в виді допоміжної програми.
2. Відомі три квадратні матриці A, B, C. Знайти мінімальне з трьох чисел x, y, z, де x - сума всіх діагональних елементів матриці A, y - сума всіх діагональних елементів матриці B, z - сума всіх діагональних елементів матриці C. Обчислення суми діагональних елементів реалізувати допоміжною програмою.
3. А, B, C - значення довжинсторін деякого трикутника. Користуючись допоміжною програмою знайти медіани трикутника, сторонами якого є медіани початкового трикутника.
4. Поліноми n-го степеня U(x) та V(x) задані своїми дійсними коефіцієнтами. Обчислити значення V(c-V(1-c)/U(c+1)), використовуючи допоміжну програму.
5. X, Y, Z - одновимірні масиви. Впорядкувати за зростанням значення чисел a, b і c, де a - мінімальний елемент масиву X, b - мінімальний елемент масиву Y, c - мінімальний елемент масиву Z. Пошук мінімального елемента оформити в виді допоміжної програми.
6. Обчислити значення виразу (x1-x2)*(y1-y2), де x1 , x2 - корені рівняння 
; y1 , y2 - корені рівняння 
. Для обчислення коренів рівнянь застосувати допоміжну програму.
7. Відомі координати точок A, B, C, D та K, L, M, N, що утворюють два опуклих чотирикутники. Визначити більший за площею чотирикутник.
8. Знайти всі корені рівняння qx2+cx+s=0, де q, c, s - довжини векторів відповідно 
, 
, 
. Обчислення довжини вектора оформити в виді допоміжної програми.
9. Скласти програму для обчислення значення функції 
, де a - середнє арифметичне від’ємних елементів масиву 
, b - середнє арифметичне від’ємних елементів масиву 
. Для обчислень середнього арифметичного розробити допоміжну програму.
10. За формулою 
визначити кут 
між двома векторами 
та 
. Обчислення скалярного добутку реалізувати у допоміжній програмі.
11. Використовуючи допоміжну програму визначити, чи належить точка (x,y,z) контурові трикутника ABC (просторові координати точок А, В, С вводяться користувачем).
12. Для векторів 
, 
, 
, 
визначити менший з скалярних добутків (x,y) та (z,p), використовуючи допоміжну програму.
13. Знайти мінімальне значення серед дійсних коренів квадратних рівнянь 
, 
, 
, використовуючи допоміжну програму.
14. На площині знаходяться точки. Використовуючи допоміжну програму знайти ті точки, що утворюють замкнений контур цієї множини.
15. Використовуючи підпрограму визначити, чи знаходиться точка (x,y) всередині чотирикутника ABCD.
16. Використовуючи допоміжну програму в послідовності натуральних чисел визначити таке, що в двійковому виді містить найменшу кількість нулів.
17. На площині трикутник задається координатами своїх вершин, а коло - координатами центру та радіусом. Визначити кількість та координати перетинань трикутника і кола.
18. Два круги задаються на площині координатами центрів і радіусами. Визначити площу їх перетинання.
19. У тривимірному просторі задається n точок (3 £ n £ 100). Визначити, чи належать вони одній площині.
20. Для квадратної матриці А визначити її n-й ступінь. Скористатися допоміжною програмою визначення добутку двох матриць.
21. Визначити, чи є матриця ортонормованою, тобто такою, що скалярний добуток кожної пари рядків дорівнює нулю, а кожного рядка на себе - дорівнює одиниці.
22. Відсортувати елементи парних рядків матриці за зростанням значення, а непарних - за зменшенням значення.
23. Відомі координати n точок площини. Визначити, котрі з них створюють мінімальну опуклу оболонку цієї множини точок.
24. Для n предметів відомими є вага та ціна. Визначити, які предмети необхідно покласти до рюкзака, щоб загальна вага не перевищувала В, а загальна ціна була максимальною.
25. У купі лежать Р золотих самородків відомої ваги. Розділити самородки на дві купи, найбільш близькі за вагою.
Запитання для контролю та самоконтролю
1. Як пояснити зміст поняття підпрограма?
2. Як використання підпрограм пов’язане з головними засадами технології структурного програмування?
3. Які можна навести класифікації підпрограм?
4. У чому особливості структури та використання функцій?
5. Які особливості структури та використання мають процедури?
6. Що таке формальні та фактичні параметри?
7. У чому полягає різниця між глобальними та локальними параметрами?
8. Проаналізувати можливості функцій та процедур з точки зору ефективного використання?
9. Які особливості використання вкладених та рекурсивних підпрограм?
10. У чому полягає механізм використання стеку при роботі з підпрограмами?
11. В яких випадках та як змінюють розміри стеку?
12. Чи можна розробникам програм створювати як доповнення до стандартних – власні бібліотечні модулі? Яку структуру має бібліотечний модуль?
13. Які правила використання бібліотечних модулів?
14. Які поняття технології об'єктно-орієнтованого програмування є логічним розвитком понять допоміжна програма та бібліотечний модуль?