Сторінка
1
Масив – це великий простір чогось однорідного за типом.
Зі словника іноземних слів, 1954 р.
Масив у програмуванні – це тип структури даних, що має складені значення.
З Оксфордського словника
англійської мови, 1995 р.
1. Одновимірні масиви В розділі 7 ми познайомилися зі структурами, в які об'єднуються дані, пов'язані своїм змістом. Структури – це змінні, складені з кількох змінних-полів, взагалі, різнотипних. Кожне поле повинно мати своє власне ім'я. Коли полів небагато, підібрати їм імена неважко. А якщо треба об'єднати кілька сотень або тисяч значень? Як правило, якщо значень багато, то всі або майже всі вони мають той самий тип. Отже, нам потрібні структури, в яких змінні однотипні й відрізняються не іменами, а номерами. Наведемо приклад, де виникають такі дані. У прикладі 5.1 (п.5.5) спочатку читалося число – точка, в якій треба було обчислити значення полінома. Потім читалися його коефіцієнти. Але більш природно спочатку прочитати поліном, а потім одну або більше точок для обчислень. В цьому разі весь поліном доведеться запам'ятати. І якщо його степінь може сягати 101, то потрібно 102 змінні. Означати їх та описувати їх обробку – не найкращий спосіб убити час. Краще означити масив – змінну, складену із 102 змінних, які ідентифікуються ім'ям масиву та номерами від 0 до 101. Можна й від 1 до 102 – це справа смаку. Уточнимо нарешті, що ж таке масив. Масив – це змінна, утворена послідовністю змінних, причому:
- усі вони (компоненти, або елементи масиву) мають той самий тип;
- кожний компонент має свій номер у послідовності (індекс) і відрізняється ним від інших елементів (ідентифікується);
- множина індексів (індексова множина) скінченна й зафіксована в означенні масиву та в процесі виконання програми не змінюється;
- можливість обробки компонента, або його доступність, не залежить від його місця в послідовності (елементи рівнодоступні).
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-й рядок біноміальних коефіцієнтів.
Завантажити реферат