Паскаль: масиви

ПАСКАЛЬ: МАСИВИ Масив — це великий простір чогось однорідного за типом.

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

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

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

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

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

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

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

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

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

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

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

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

Подивимося на масив із точки зору математики. Нехай компоненти масиву мають тип T, а індекси — тип I. Значенням змінної-масиву є послідовність значень типу T, занумерованих значеннями типу I, тобто функція типу IxF0AE 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.

З точки зору математики, для масивів означена операція індексування []. За масивом типу IxF0AE 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 елементів, де nxF0A3 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,.

де nxF0A3 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 «є «12 345 ». Ціла довжина рядка повертається з виклику функції length із аргументом-рядком: length («123 ») = 3.

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

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

s:= «12 345 «.

чотири її компоненти з індексами 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 зі «сміття «перетворяться на значення-рядок. Присвоювання іншим елементам рядка не змінює довжини його значення.

У типах рядків означено операції порівняння =, <>, <, …. За означенням, рядки рівні, якщо мають ту саму довжину, і в її межах відповідні символи однакові. У противному разі вони не рівні. Упорядкування рядків залежить від системи програмування.

У мові Турбо Паскаль, якщо length (s1).

У системі програмування Турбо Паскаль означено також багато корисних підпрограм обробки рядків. Розглянемо лише чотири з них.

Функція з заголовком.

function copy (s: string; ind, cnt: byte): string.

задає повернення підрядка рядка s, що починається з s[ind] і має довжину cnt. Наприклад, copy («abcd », 2, 2)= «bc » .

Функція з заголовком.

function pos (subs, s: string): byte.

задає повернення номера того елемента в рядку s, починаючи з якого subs входить у s як підрядок (якщо не входить, то повертається 0). Наприклад, pos («bc », «abcd »)=2, pos («aa », «abcd »)=0.

Процедура з заголовком.

procedure val (s: string, var v; var ErrCode: integer).

задає перетворення зображення числа в рядку s у числовий тип і присвоювання його змінній v. Якщо перетворення дійсно можливе, то значенням ErrCode буде 0. У противному разі її значенням буде позиція з символом у рядку, починаючи з якого перетворення неможливе. Тип аргументу, відповідного параметрові v, повинен мати тип, відповідний змісту рядка s. Так само зміст рядка повинен задавати число, представне в типі цього аргументу. Наприклад, за s= «1.3 «або s= «1E2 «другий аргумент повинен бути дійсного типу, а не цілого. Аналогічно за його типу integer у рядка не повинно бути значень, що подають числа, більші 32 767 або менші -32 768.

Процедура з заголовком.

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.

®.

U.

TH.

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, де PxF0A3 256. За P=256 кожний біт відображає значення двійкової цифри 0 чи 1; таке подання найекономніше витрачає пам «ять, але вимагає певних зусиль для реалізації операцій.

4) Значення P-кової цифри, де PxF0A3 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.123xF0D7 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, де 1xF0A3 k.

4. Матриці та багатовимірні масиви Розглянемо прямокутну таблицю з mxF0B4 n однотипиних елементів як послідовність із m рядків, у кожному з яких n елементів. Послідовності певної довжини подаються в мовах програмування масивами. Отже, виникає поняття «масив, елементами якого є масиви », або двовимірний масив. Якщо елементи прямокутної таблиці самі є послідовностями або таблиці утворюють послідовність певної довжини, то виникає поняття тривимірного масиву тощо.

Означення багатовимірних масивів та зображення їх елементів у мові Паскаль опишемо за допомогою простого прикладу. Позиція в грі «хрестики-нулики на полі 3xF0B4 3 «подається квадратною таблицею з символів «x », «0 «або «» (пропуск). Пронумеруємо клітинки поля, як у шахах — літерами «a », «b », «c «по горизонталі та числами 1, 2, 3 по вертикалі. Тоді рядки таблиці можна подати масивами типу.

type Row = array [ «a ». «c «] of char;

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

type Table = array [ 1. 3 ] of Row;

Партія, тобто послідовність позицій, має довжину не більше 9, і може подаватися масивом таблиць:

type Game = array [ 1. 9 ] of Table;

Масиви типу Table мають два виміри: номер рядка та номер символу в ньому; масиви типу Game — три: номери таблиці, рядка та символу. Вимір 1.9 у типі Game називається зовнішнім, вимір «a ». «c », що нумерує символи в рядках, — внутрішнім.

Тип Game можна задати еквівалентним виразом, не означаючи імен типів Row і Table, а саме:

type Game = array [ 1. 9 ] of.

array [ 1. 3 ] of.

array [ «a ». «c «] of char;

Нехай A — змінна типу Game. Вираз вигляду A[ i ], де 1xF0A3 i xF0A3 9, задає змінну типу Table, або типу.

array [ 1. 3 ] of array [ «a ». «c «] of char;

вираз вигляду A[i][j], де 1xF0A3 jxF0A3 3, — змінну типу Row, або типу.

array[ «a ». «c «] of char;

вираз вигляду A[i][j][k], де «a «xF0A3 k xF0A3 «c » , — змінну типу char.

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

type Game1 = array [ 1. 9, 1. 3, «a ». «c «] of char.

еквівалентне означенню типу Game, а вираз A[i, j, k] - виразові A[i][j][k].

Елементи багатовимірних масивів розташовуються в пам «яті послідовно, найшвидше в них змінюється внутрішній індекс, найповільніше — зовнішній. Зокрема, двовимірні масиви (матриці) розташовуються за рядками. Так, послідовні числа масиву типу.

array [ 1 .2, «a ». «b «] of real.

мають набори індексів [1, «a «, [1, «b «, [2, «a «, [2, «b «, а послідовні символи в масиві типу Game — [1, 1, «a «, [1, 1, «b «, [1, 1, «c «, [1, 2, «a «, …, [1, 3, «c «, [2, 1, «a «, …, [9, 3, «c «].

Задачі.

30. Написати процедуру побудови за дійсними числами a1, …, an квадратної матриці.

а) 1 1 … 1 б) a1 a2 … an-1 an.

a1 a2 … an a2 a3 … an a1.

… …

a1n-1 a2n-1 … ann-1 an a1 … an-2 an-1.

31.* У матриці розмірами M xF0B4 N обміняти місцями а) два рядки, б) два стовпці,.

задані номерами.

32.* Транспонувати квадратну матрицю без використання додаткової матриці.

33.* Квадратну матрицю повернути за годинниковою стрілкою на а) 90xF0B0; б) 180xF0B0 .

Додаткову матрицю не використовувати.

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

35. За матрицею з дійсними елементами побудувати нову «згладжену «матрицю, значенням кожного елемента якої є середнє арифметичне значень відповідного елемента та його сусідів у початковій матриці.

36.* Написати процедуру обчислення добутку двох матриць.

37. Написати процедуру обчислення степеня квадратної матриці на основі «індійського алгоритму «(див. підр. 9.4).

38. За квадратною матрицею розміру N одержати послідовність чисел b1, b2, …, bN*N обходом матриці.

а) «змійкою »: б) за спіраллю:

39. Елементи N-вимірного масиву розмірів M1 xF0B4 … xF0B4 MN розміщаються в пам «яті комп «ютера послідовно так, що найшвидше змінюється їх останній індекс, найповільніше — перший. Написати функцію обчислення лінійного індексу елемента (його номера в порядку розташування в пам «яті) за заданими розмірами M1, …, MN та індексами елемента в N-вимірному масиві. Написати процедуру обчислення індексів елемента в багатовимірному масиві за його лінійним індексом та розмірами M1, …, MN. Значенням N є:

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

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