Масив – це великий простір чогось однорідного за типом.

Зі словника іноземних слів, 1954 р.

Масив у програмуванні – це тип структури даних, що має складені значення.

З Оксфордського словника

англійської мови, 1995 р.

1. Одновимірні масиви

В розділі 7 ми познайомилися зі структурами, в які об'єднуються дані, пов'язані своїм змістом. Структури – це змінні, складені з кількох змінних-полів, взагалі, різнотипних. Кожне поле повинно мати своє власне ім'я. Коли полів небагато, підібрати їм імена неважко. А якщо треба об'єднати кілька сотень або тисяч значень? Як правило, якщо значень багато, то всі або майже всі вони мають той самий тип. Отже, нам потрібні структури, в яких змінні однотипні й відрізняються не іменами, а номерами.

Наведемо приклад, де виникають такі дані. У прикладі 5.1 (п.5.5) спочатку читалося число – точка, в якій треба було обчислити значення полінома. Потім читалися його коефіцієнти. Але більш природно спочатку прочитати поліном, а потім одну або більше точок для обчислень. В цьому разі весь поліном доведеться запам'ятати. І якщо його степінь може сягати 101, то потрібно 102 змінні. Означати їх та описувати їх обробку – не найкращий спосіб убити час. Краще означити масив – змінну, складену із 102 змінних, які ідентифікуються ім'ям масиву та номерами від 0 до 101. Можна й від 1 до 102 – це справа смаку.

Уточнимо нарешті, що ж таке масив. Масив – це змінна, утворена послідовністю змінних, причому:

• усі вони (компоненти, або елементи масиву) мають той самий тип;

• кожний компонент має свій номер у послідовності (індекс) і відрізняється ним від інших елементів (ідентифікується);

• множина індексів (індексова множина) скінченна й зафіксована в означенні масиву та в процесі виконання програми не змінюється;

• можливість обробки компонента, або його доступність, не залежить від його місця в послідовності (елементи рівнодоступні).

Кількість елементів індексової множини називається довжиною масиву.

Подивимося на масив із точки зору математики. Нехай компоненти масиву мають тип T, а індекси – тип I. Значенням змінної-масиву є послідовність значень типу T, занумерованих значеннями типу I, тобто функція типу I T. Множина всіх таких функцій утворює носій для типу, який у мові Паскаль означається виразом вигляду

array [I ] of T.

Наприклад, масив, у якому треба зберігати коефіцієнти полінома, міг би мати тип array[0..101]of real. У такому масиві 102 компоненти дійсного типу із номерами від 0 до 101. Або масив, у якому треба зберігати кількості символів, прочитаних десь, міг би мати тип array [ char ] of integer. У ньому 256 цілих змінних, а їх номерами є символи.

Типом компонентів може бути довільний тип, окрім файлів (розділ 13). Типом індексів I – будь-який перелічуваний тип. Щоправда, система Турбо Паскаль не дозволяє вказувати типи integer та word, а тим паче тип longint, як типи індексів. Там занадто багато елементів. Але це не страшно, оскільки система дозволяє створювати масиви навіть із ще більшою кількістю елементів (див. підрозділ 16.5).

Якщо тип індексів означається виразом у дужках [ ] як діапазон, то, зрозуміло, там пишуться дві сталі, і ніяких змінних там не може бути.

В означенні масивів як змінних немає ніяких особливостей. Наприклад, ми можемо написати як

type ART=array[0..101]of real; var A : ART;

так і

var A : array[0..101]of real;

В обох випадках змінна A складається зі 102 дійсних змінних. Вони ідентифікуються виразами A[0], A[1], … , A[101]. Або виразами вигляду A[індексовий-вираз], де індексовий-вираз має значення від 0 до 101.

З точки зору математики, для масивів означена операція індексування []. За масивом типу I T та номером компонента в ньому вона породжує змінну типу T. Нехай ім'я означено як масив типу array[I] of T, E – вираз типу I. Тоді вираз ім'я[E] задає елемент цього масиву, тобто змінну типу T, номер якої в масиві є значенням виразу E.

Вирази з операцією [] допустимі в операторах скрізь, де вживається змінна відповідного типу, за винятком того, що елемент масиву не може бути параметром циклу. Наприклад, якщо діє означення типу ART та змінної A, то можна писати щось на зразок

A[1] :=1; A[2] := A[1]+2;

for k := 3 to 101 do readln(A[k]);

writeln(A[1]+A[2]+A[3]+A[4]).

Індексування – це єдина операція над масивами як цілісними об'єктами. Тому обробка масивів описується через обробку їх компонентів. Щоправда, в мові Турбо Паскаль можна присвоювати однотипні масиви. Наприклад, за дії означень

var a, b : array[char] of integer; ch : char;

можна замість циклу

for ch:= chr(0) to chr(255) do b[ch]:=a[ch];

написати лаконічно

b := a;Зупинимося на підстановці аргументу-масиву на місце параметра підпрограми. Якщо параметр-масив є параметром-значенням, то на початку виконання виклику підпрограми в локальній пам'яті цього виклику створюється копія аргументу. Якщо у масиві багато елементів, то можлива ситуація, коли автоматичної пам'яті для такого аргументу не вистачить. Проте за виконання підпрограми масив або залишається без змін, або змінюється, причому саме змінений масив і потрібний для подальшої обробки за програмою. У першому випадку його можна підставляти за посиланням, а не за значенням; в другому – треба. Випадки, коли параметри-масиви необхідно означати як параметри-значення, трапляються досить рідко. Звичайно, використання параметрів-змінних типу масив вимагає підвищеної акуратності.

Задачі

1.* Нехай масив має тип array [ 1..20 ] of integer. Написати процедуру читання його перших n елементів, де n 20, за умови:

а) спочатку задається n, потім n значень. За n>20 слід повернутися до читання n.

б) вхідних значень довільна кількість; їх кінець задається у спосіб (2) або (3) з параграфа 5.6. Якщо прочитано 20 елементів, а ознаки закінчення вводу немає, то виконання процедури повинно завершатися.

2.* На вхід програми подається N цілих чисел X1, ... , XN із діапазону 0 ..100; N>0. Написати програму обчислення:

1) їх середнього арифметичного значення M та дисперсії D, тобто середнього арифметичного квадратів різниць між числами та M:

D = ( ( X1 - M )2 + … + ( XN - M )2 ) / N;

2) кількостей повторень K1, K2, … , K100 кожного з чисел 1, 2, … , 100.

Числа надходять у програму

а) від стандартного пристрою введення, тобто клавіатури;

б) від генератора випадкових чисел.

3. Коефіцієнти A0, A1, … , An полінома

A0 + A1*X + … + An*Xn,

де n 99, задаються елементами масиву типу array [0..99] of real. Окрема змінна зберігає степінь полінома n. Написати модуль, що має означення типу поліномів і задає обчислення значення полінома в точці v, похідної полінома (це поліном степеня n-1), суми, різниці та добутку двох поліномів, частки та остачі від ділення полінома на біном x - c.

4.* Риби народжуються навесні й живуть не більше 9,5 років. Навесні на кожну рибину припадає в середньому B новонароджених мальків. Кількість риб незалежно від їхнього віку за рік (від весни до весни) зменшується в D разів. Навесні першого року у водоймище випустили M новонароджених мальків. Написати програму обчислення, скільки риби та якого віку буде у водоймищі навесні через Y років.

5. Черга – це така послідовність, що елементи додаються в її кінець, а вилучаються з її початку. Написати модуль роботи з чергою цілих, поданою в масиві. У модулі повинні бути підпрограми:

1) ініціалізації модуля;

2) скидання черги (вилучення всіх її елементів);

3) обчислення кількості елементів у черзі;

4) перевірки, чи порожня черга;

5) обчислення обсягу вільного місця в черзі (кількість елементів, які можна додати до її заповнення);

6) додавання елемента в кінець черги;

7) добування та вилучення елемента з її початку.

6. Стек, або магазин – це така послідовність, що елементи додаються й вилучаються з її початку. Написати модуль роботи зі стеком цілих, поданим у масиві. У модулі повинні бути підпрограми:

1) ініціалізації модуля;

2) скидання стека (вилучення всіх його елементів);

3) обчислення кількості елементів стека;

4) перевірки, чи порожній стек;

5) обчислення обсягу вільного місця в стеку (кількість елементів, які можна додати до його заповнення);

6) додавання елемента до початку стека;

7) добування й вилучення елемента з початку стека.

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

Означити умови коректності подання та написати процедуру їх перевірки.

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

8.* Нехай {a1, a2, … , an} – множина цілих чисел. Написати процедуру пошуку всіх її підмножин, таких, що сума елементів кожної з них дорівнює заданому числу M.

9. Написати процедуру формування масиву, що подає n-й рядок біноміальних коефіцієнтів.

2. Рядки

Рядок у загальному значенні цього слова – скінченна послідовність символів. У програмуванні для подання рядків використовують масиви символів. У діалектах мови Паскаль означено спеціальні типи, в основі яких лежать масиви. Типи рядків мають свої специфічні операції, не означені над масивами символів, тобто рядки та символьні масиви є цілком різними типами.Змінна-рядок є масивом символів разом із додатковим компонентом. В означенні типу задається довжина n послідовності символьних компонентів, індексованих цілими 1,…,n. Додатковий компонент указує довжину послідовності символів, поданої в масиві. Ця довжина значення-рядка може змінюватися в процесі виконання програми від 0 до довжини масиву n.

У мові Турбо Паскаль тип рядків задається виразом вигляду

string[n],

де n – ціла стала з діапазону 1..255 (можливо, іменована). Наприклад, string[80]. Змінна такого типу є масивом символів із індексами від 0 до n. Значення-рядок подається змінними з індексами від 1 до n, змінна з індексом 0 подає довжину рядка. Точніше, якщо її значення c, то m=ord© розглядається як довжина значення-рядка. У процесі виконання програми вона може мінятися від 0 до n.

Елементи масиву з індексами від m+1 до n недоступні; їх значення можна розглядати як "сміття". Спроба присвоїти щось цим елементам або взяти їх значення призведе до аварійного завершення програми.

Оскільки невід'ємна довжина значення-рядка подається в одному байті, вона не може перевищувати 255. Звідси "маємо, те що маємо", тобто обмеження 255 на довжини рядків. Ім'я типу string еквівалентне виразові string[255].

Найпростішими виразами типу рядок є ім'я змінної-рядка, рядкова стала (літерал), або вираз типу char. Над рядками означена бінарна операція катенації (або дописування); її знаком є '+'. Результат одержується дописуванням правого операнда до лівого: значенням виразу '123'+'45' є '12345'. Ціла довжина рядка повертається з виклику функції length із аргументом-рядком: length('123') = 3.

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

Вираз типу "рядок" можна присвоїти змінній-рядку. Його символи присвоюються елементам змінної, починаючи з першого. Якщо довжина значення більша максимально можливої довжини n змінної, то присвоюються лише n перших символів. При цьому довжина значення (або n) неявно присвоюється додатковому компоненту змінної-рядка (як символ нульовому елементу масиву). Наприклад, нехай змінна s означена як string[3]. Після присвоювання

s:='12345'

чотири її компоненти з індексами 0, 1, 2, 3 матимуть значення chr(3), '1', '2', '3', а після

s:='12'

– chr(2), '1', '2', а останній компонент буде недоступним, і його значення буде "сміттям". За останнього значення змінної s виконання оператора

s:=s+'9'

надасть їй значення '129', а оператора

s:='9'+s

– значення '912'. В обох випадках s[0]=chr(3). Після присвоювання s:='' змінна s подає порожній рядок: s[0]=chr(0), а решта елементів недоступні.

Змінити довжину значення можна явно, змінивши нульовий символ. Якщо після s:='' виконати s[0]:=2, то значення компонентів із індексами 1 і 2 зі "сміття" перетворяться на значення-рядок. Присвоювання іншим елементам рядка не змінює довжини його значення.

У типах рядків означено операції порівняння =, , Процедура з заголовком

procedure delete(var s : string; start, len : integer)

задає знищення len символів, починаючи з позиції start у рядку s. Наприклад, за s='abcdef' після виклику delete(s, 3, 3) рядок s матиме значення 'abf'. За start=0 або len=0 або start>length(s) рядок не змінюється. За start+len>length(s) з s вилучається підрядок до кінця рядка.

Задачі

10.* Що друкується в результаті виконання програми:

а) program strconc ( input, output );

var a: integer; c: char; s: string;

begin

s :='';

for a := 0 to 2 do

begin

c := chr ( ord ( '0' ) + a ); s := c + s + c; writeln ( s )

end

end.

б) program concstr ( input, output );

var a: integer; c: char; s: string;

begin

s :=''; c:= chr ( 47 );

while length ( s ) < 7 do

begin

c := succ ( c ); s := s + c + s; writeln ( s )

end

end.

11. Застосовуючи операцію "+", функцію length та подання рядка масивом із додатковою змінною, що задає довжину рядка, написати модуль із такими підпрограмами обробки рядків:

1)* функції eq, ne, lt, le, gt, ge лексикографічного порівняння пари рядків відповідно на =, , =;

2) процедура addsym вставлення символу в указане місце рядка зі збільшенням його довжини на 1(якщо збільшення неможливе, то останній символ "витісняється");

3)* процедура delsym вилучення символу з указаним номером із рядка зі зменшенням його довжини на 1;

4)* функція substr повернення підрядка даного рядка, що починається в ньому з заданого місця та має задану довжину;

5) процедура delete вилучення з рядка його підрядка, що починається в ньому з заданого місця та має задану довжину.

12. Натуральне число в десятковому вигляді подано рядком, довжина якого не більша 80. Написати функцію перевірки ознаки подільності числа на:

а) 5; б) 4; в) 3; г) 11.

13. Номер із контрольним розрядом є зображенням числа, перша цифра якого 1, а остання є остачею від ділення на 10 суми значень цифр із другої до передостанньої включно (контрольний розряд).

Написати модуль, в якому перша функція задає побудову відповідного номера з контрольним розрядом із 10 цифр за натуральним числом, а друга – перевірку, чи є послідовність із 10 цифр правильним номером із контрольним розрядом.

14. Нехай рядкове подання цілого невід'ємного числа в десятковій системі починається з будь-якої цифри, крім '0' (за винятком числа 0), у вісімковій – починається символом '0', у шістнадцятковій – символами '0x', у двійковій – символами '0b'. Далі записано цифри відповідної системи числення. У записі від'ємного числа знак '-' передує першій цифрі. Написати модуль із функціями перетворення рядкових зображень цілих чисел у стандартний тип і навпаки.

15. Написати модуль із функціями перетворення рядкових зображень натуральних чисел із римської системи запису в стандартний цілий тип і навпаки.

16. Написати модуль із функціями перетворення зображень цілих чисел зі стандартних типів у рядкове:

а) у словесному вигляді;

б) у словесному вигляді з урахуванням відмінка й навпаки.

17.* Непорожній рядок містить цілі числа, відокремлені пропусками в довільній кількості. Якщо в рядку 3 числа, то слід визначити, чи задають вони довжини сторін трикутника, і надрукувати повідомлення "трикутник" або "не трикутник". За іншої кількості чисел треба повідомити: "помилкові дані".

18. Написати функцію обчислення за двома рядками

а) найбільшої довжини їхнього спільного підрядка;

б) їхнього найдовшого спільного підрядка (якщо таких кілька, то повертається ближчий до початку першого рядка, наприклад, для рядків "тік" та "кіт" це рядок "т", а для рядків "кіт" та "тік" – "к");

в) найбільшої довжини їхньої спільної підпослідовності символів (наприклад, для рядків "слова" та "справи" підпослідовності "св" і "са" мають довжину 2);

г) їхньої найдовшої спільної підпослідовності (якщо таких кілька, то повертається найбільш "притиснута" до початку першого рядка – для рядків "справи" та "слова" це "са", а не "св").

19. Нехай над рядками означено дії двох видів: вставити та вилучити символ. Мінімальна довжина послідовності дій, необхідних для перетворення одного рядка в інший, називається відстанню між ними. Наприклад, відстань між рядками "кава" та "чай" дорівнює 5 (вилучити букви "к", "в", "а" та вставити "ч" та "й"). Написати функцію обчислення відстані між двома рядками.

3. Нестандартне подання чисел

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

Для подання та обробки чисел необхідно означити спеціальні типи та підпрограми реалізації операцій над числами. Необхідні також підпрограми перетворення чисел із цих типів до звичного вигляду й назад, аналогічні процедурам запису та читання даних стандартних типів.Ціле число в будь-якій системі числення зображається послідовністю цифр. Зокрема, подання в стандартних типах – це послідовність двійкових цифр, відтворених бітами. Обробка чисел у їх стандартному поданні відтворює звичні алгоритми виконання арифметичних операцій (додавання "у стовпчик" тощо), але у двійковій системі числення.

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

1) Значення цифри десяткового числа подається елементом масиву типу integer. Пам'ять використовується дуже неекономно (розряд займає 2 або 4 байти), але арифметичні операції реалізуються через порозрядні операції над значеннями цифр, уже означені в Паскалі для типу integer.

2) Цифра числа (а не її значення-число) безпосередньо є значенням типу char і подається одним байтом. Покомпонентні операції над значеннями цифр треба відтворити у вигляді операцій над символами. Для зображення чисел зручно скористатися рядковим типом.

3) Значення цифри числа в P-ковій системі подається одним байтом як число від 0 до P-1, де P 256. За P=256 кожний біт відображає значення двійкової цифри 0 чи 1; таке подання найекономніше витрачає пам'ять, але вимагає певних зусиль для реалізації операцій.

4) Значення P-кової цифри, де P 16, подається чотирма бітами (півбайтом) так, що дві сусідні цифри займають байт.

Дійсні числа (точніше, раціональні з їх певної підмножини) можуть подаватися у вигляді з фіксованою чи з плаваючою крапкою. У першому випадку фіксуються розряди для зображення цифр цілої та дробової частини. У другому – розряди дробової частини та показника степеня (мантиси й порядку – див. підрозділ 11.2). Ще один розряд подає знак числа. Варіанти подання відрізняються основами систем числення та довжиною мантиси й порядку, а також одиницями пам'яті для розрядів.

Задачі

20.* Означити типи для зображення цілих згідно з варіантами 1-4 у поясненнях.

21. Означити типи для зображення дійсних чисел у вигляді з фіксованою та плаваючою крапкою.

22.* Написати підпрограми введення та виведення числа нестандартного цілого типу.

23. Написати підпрограму обчислення

а)* суми; б) різниці

двох цілих чисел у нестандартному цілому типі.

24. Написати підпрограму обчислення

а) добутку; б) частки від ділення; в) остачі від ділення

"нестандартного" цілого числа на число типу integer.

25.* Написати підпрограму обчислення

а) добутку; б) частки від ділення; в) остачі від ділення

двох "нестандартних" цілих чисел.

26. Вхідними даними програми є послідовність цілих сталих та знаків операцій, що задається метавиразом

{ }

Знаки операцій +, -, *, d, m позначають відповідно додавання, віднімання, множення, частку та остачу від ділення. Сталі мають до 20 десяткових цифр. Кожна стала та знак операції набирається на клавіатурі з нового рядка. Ознака кінця задається натисканням на "Ctrl-Z".

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

Створити та використати модуль, що задає обробку чисел у їхньому нестандартному поданні. Варіанти подання – це варіанти 1-4 з пояснень до параграфа 12.3.

Варіанти наборів знаків операцій:

а) +; б) +, -; в) +, -, *;

г) d, m; д) +, -, *, d, m.

Сталі задають числа

а) невід'ємні; б) невід'ємні та від'ємні (зі знаком '-' попереду).

27. Вхідними даними програми є послідовність дійсних сталих та знаків операцій, що задається метавиразом

{ }

Знаки операцій +, -, *, / позначають відповідно додавання, віднімання, множення та ділення. Вхідна стала – це пара цифрових послідовностей, можливо, зі знаками '-' попереду, що задається метавиразом

['-'] Ц { Ц } ' ' ['+'|'-'] Ц [ Ц ]

Метасимвол Ц позначає десяткові цифри. Перша послідовність цифр (довжиною до 20) задає дробову частину числа, друга – десятковий порядок (так, символи 123 -12 задають число 0.123 10-12). Кожна стала та знак операції набирається на клавіатурі з нового рядка. Ознака кінця задається натисканням на "Ctrl-Z".

Вихідними даними програми є послідовність вихідних дійсних сталих. Перша з них є результатом нормалізації першої вхідної сталої. Кожна наступна подає нормалізований результат застосування операції, заданої знаком, до чисел, що подаються попередньою вихідною сталою та наступною вхідною. Нормалізоване подання числа – це стала вигляду

[ '+' | '-' ] Ц1 '.' Ц { Ц } 'E' [ '+' | '-' ] Ц [ Ц ],

де метасимвол Ц1 позначає цифри від 1 до 9.

Створити та використати модуль, що задає обробку чисел у їхньому нестандартному поданні.

Варіанти наборів знаків:

а) +, -; б) *, /; в) +, -, *, /.28. Написати програму створення за p-ковим поданням натурального числа (послідовність p-кових цифр) q-кового, де p, q – числа з множини {2, 3, ... , 36}. Довжина вхідної послідовності не більше 50 цифр. Значення p та q відповідно

1) 2 та 8; 2) 8 та 2; 3) 2 та 16;

4) 16 та 2; 5) 8 та 16; 6) 16 та 8;

7) задається як вхідне та 10; 8) 10 та задається як вхідне; 9) задаються як вхідні.

29.* Натуральні k та m, де 1 k39. Елементи N-вимірного масиву розмірів M1  …  MN розміщаються в пам'яті комп'ютера послідовно так, що найшвидше змінюється їх останній індекс, найповільніше – перший. Написати функцію обчислення лінійного індексу елемента (його номера в порядку розташування в пам'яті) за заданими розмірами M1, … , MN та індексами елемента в N-вимірному масиві. Написати процедуру обчислення індексів елемента в багатовимірному масиві за його лінійним індексом та розмірами M1, … , MN. Значенням N є:

а) 2; б) 3; в) 4.

40. Зображення містить замкнений контур і подається матрицею з 50 рядків по 80 символів. Елементи контура зображаються символом chr(219), порожні клітини всередині та зовні контура – пропуском ' '. Якщо всередині контура є хоча б один елемент із значенням '1' (відмічений), то зображення "заливається", тобто всі елементи всередині контура відмічаються за правилом: елемент відмічається, якщо з чотирьох його сусідніх по вертикалі чи горизонталі елементів хоча б один відмічений. Написати процедуру заливання зображення.