Файл: ОП Конспект лекций - Паскаль.doc

Тема 14: Багатомірні масиви

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

A(3,4) =

Дана матриця має розмір 3 на 4, тобто вона складається з трьох рядків і чотирьох стовпців. Матриця позначається ім'ям, а кожен її елемент має два індекси, наприклад, А[i,j], де перший індекс “i” позначає номер рядка, а другий індекс “j” – номер стовпця. Опис матриці має вид.

type massiv = array[1..3] of array[1..4] of integer;

var a:massiv;

або

type massiv = array[1..3,1..4] of integer;

var a:massiv;

де в першому варіанті спочатку описується один тип індексу 1..3, потім указується складний базовий тип Array[1..4] Of Integer, що у свою чергу містить опис другого типу індексу і простого базового типу Integer. В другому випадку описується кожен тип індексу, потім указується простий базовий тип елементів масиву Integer.

Якщо в програмі потрібно виділити окремі рядки матриці, опис буде мати вид

type

massiv1= array[1..4] of integer;

massiv = array[1..3] of massiv1;

var

a : massiv; b : massiv1;

тут спочатку описується тип одного рядка Massiv1, а потім, через тип рядка Massiv1 описується тип усієї матриці Massiv; у розділі Var “A” є двовимірним масивом, а “B” – одномірним масивом.

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

type bukva = ( a, b, c, d, e, f, g, h, );

type doska = array[bukva, 1…8] of figural;

Введення елементів матриці виконується за допомогою процедури Read, що розташовують усередині циклу, наприклад,

writeln(`Введення елементів матриці:`);

for i := 1 to n do

for j :=1 to m do

read(a[ i, j ]);

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

writeln(`Виведення елементів матриці:`);

for i :=1 to n do

begin

for j :=1 to m do

write(a[ i, j ]);

writeln;{ця процедура потрібна для порядкового виведення матриці}

end;

Приклад. Дано матрицю дійсних чисел А.

А(3,5)=

Одержати матрицю В, значення якої дорівнюють подвоєним значенням матриці А.

const n=3;{кількість рядків}

m=5;{кількість стовпців}

type massiv = array[1..n,1..n] of real;

var

a,b : massiv;{масиви типу massiv}

i : integer; {індекс рядка}

j : ineger; {індекс стовпця}

begin

writeln(`введіть значення матриці А :`);

for i := 1 to n do

for j := 1 to m do

read(a[i,j]);

{обчислення значень матриці В:`);

for i := 1 to n do

for j :=1 to m do

b[i,j]:=a[i,j]*2;

writeln(‘виведення значень матриці В :’);

for i:=1 to n do

begin

for j:=1 to m do

write (b[ i, j ]:3:1,’ ’:2 );

writeln;

end;

end.

Питання для контролю.

1.Багатомірний масив і його опис.

2.Позначення елементів матриці.

3.Якими можуть бути типи індексів матриці?

4.Організація введення елементів матриці.

5.Організація виведення елементів матриці.

Тема 15: Пошук і сортування елементів масиву. Класи алгоритмів сортування

Сортування методом вибору найменшого елемента

Пошук мінімального (максимального) елемента в масиві

Задача пошуку полягає у пошуку в масиві елемента (чи декількох елементів) із заданими значеннями. Наприклад, пошук максимального чи мінімального значення елемента.

Алгоритм пошуку розглянемо на прикладі. Нехай заданий масив різних елементів:

x_{1 ,} x₂ , x₃ … x_n ;

Необхідно знайти мінімальне значення елементів масиву і номер мінімального елемента.

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

Приклад програми:

{Пошук миним. елемента в масиві і його номер}

const n=10;

type massiv=array[1..n] of real;

var

x : massiv; i, nom : integer; min : real;

begin

writeln(‘введіть’,n,’елементів масиву:’);

for i := 1 to n do read(x[ i ]);

min := x[1]; nom :=1;

for i := 2 to n do

begin

if min > x[ i ] then

begin

min := x[ i ]; nom :=i

end

end;

writeln(‘мінімальне значення’,min:2:3);

writeln(‘це’,nom’элемент масиву.’)

end.

Сортування методом вибору найменшого елемента

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

Наприклад.

Вихідний масив

Упорядкований за

зростанням масив

Розглянемо три найбільш прості методи сортування.

Сортування методом вибору найменшого елемента полягає в наступному. Знайдемо в масиві елемент із найменшим значенням і поміняємо його місцями з першим елементом. Потім розглянемо масив, що залишився, без першого елемента, починаючи з 2-го, і повторимо ті ж дії. Так продовжуємо доти, поки не залишиться один, останній елемент. Він буде найбільшим. У результаті одержимо масив упорядкований по зростанню значень елементів. Приклад програми:

const

n=10;

type massiv=array[1..n] of real;

var

a : massiv; i, j, k : integer; x : real;

begin

writeln(‘введіть’,n,’елементів масиву:’)ж

for i :=1 to n do read(a[ i ]);

writeln(‘упорядкований по зростанню масив:’);

for i :=1 to n do

begin

k :=i; x := a[ i ];

for j :=i+1 to n do

if a[ j ] < x then

begin

x :=a[j];

k :=j;

end;

a[ k ] :=a[ i ];

a[ i ] :=x;

write(x:6:2);

end;

end.

Сортування методом обміну (метод “пухирця”)

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

Значення елементів масиву необхідно упорядкувати по зростанню.

Розглянемо його від кінця до початку (порядок розгляду не має значення). Порівняємо 4-й і 5-й елементи. Вони розташовані не в порядку зростання, поміняємо їх місцями. Положення елементів буде наступним:

Тепер порівняємо 3-й і4-й елементи. Вони розташовані в порядку зростання і їх залишимо на місці. Порівнюємо 2-й і 3-й елементи і змінюємо їх місцями:

І, нарешті, порівнюємо і змінюємо місцями 1-й і 2-й елемент

2₁ 7₂ 20₃ 3₄ 15₅

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

Приклад програми:

const

n=10;

type massiv=array[1..n] of integer;

var

a : massiv; i, j, x : integer;

begin

writeln('Введіть 10 значень елементів масиву:');

for i := 1 to n do read (a[i]);

writeln(‘упорядкований по зростанню масив:’);

for i := 2 to n do

begin

for j := n downto i do

if a[j-1] > a[j] then

begin

x := a[j-1];

a[j-1] := a[j];

a[j] := x;

end;

for := 1 to n do

write(a[i],’’);

end;

end.

Сортування методом уставок

Полягає в наступному. Нехай у заданій послідовності А[1], А[2], ..., А[n] перші елементи уже відсортовані. У цій частині послідовності будемо шукати місце для і-го елемента, порівнюючи його один по одному зі всіма елементами, що знаходяться ліворуч, поки не виявиться, що деякий А[j] елемент<=A[і]. Зрушимо праву частину послідовності A[j+1], A[j+2], ..., A[j-1] на один елемент у право, звільнивши місце A[j=1] для елемента A[і], куди його і поставимо.

У випадку, якщо виявиться, що елемент A[і] менше всіх елементів, що стоять ліворуч, і місце йому не знайдено, перегляд закінчимо по досягненню першого елемента і всю послідовність зрушимо на один елемент вправо, а елемент A[і] поставимо на перше місце.

Проробивши подібні дії від 2-го елемента до n-го, одержимо упорядковану по зростанню значень елементів послідовність.

Приклад програми:

const

n=10;

type massiv=array[1..n] of integer;

var

a : massiv;

i, j, x : integer;

begin

writeln('введіть вектор з ',n,' цілих чисел:');

for і := 1 to n do

read(a[i]);

writeln(‘упорядкований по зростанню вектор:’);

for i := 2 to n do

begin

x := a[i];

j := i-1;

while (x<a[j]) and (j>0) do

begin

a[j+1] := a[j];

j := j-1;

end;

a[j+1] :=x;

for i:= 1 to n do

write(a[i],’’);

end.

Питання для контролю.

1. Задача пошуку елемента в масиві і задача сортування елементів у масиві.

2. Алгоритм пошуку мінімального елемента в масиві і визначення його номера.

3. Алгоритм сортування методом вибору найменшого елемента.

4. Алгоритм сортування методом уставок. Приклад програми.

Тема 16: Динамічна пам'ять. Адреси і покажчики

Динамічна пам'ять

Всі змінні, оголошені в програмі, розміщуються в однієї безперервної області оперативної пам'яті, яка називається сегментом даних. Довжина сегменту даних визначається архітектурою мікропроцесорів 80x86 і складає 65536 байт, що може викликати відому скруту при обробці великих масивів даних. З іншого боку, об'єм пам'яті ПК (зазвичай не менше 640 Кбайт) достатній для успішного вирішення завдань з великою розмірністю даних. Виходом з положення може служити використання так званої динамічної пам'яті.

Динамічна пам'ять - це оперативна пам'ять ПК, що надається програмі при її роботі, за вирахуванням сегменту даних (64 Кбайт), стека (звичайні 16 Кбайт) і власне тіла програми. Розмір динамічної пам'яті можна варіювати в широких межах (див. пріл.1). За умовчанням цей розмір визначається всією доступней пам'яттю ПК і, як правило, складає не менше 200...300 Кбайт.

Динамічна пам'ять - це фактично єдина можливість обробки масивів даних великої розмірності. Багато практичних завдань важко або неможливо вирішити без використання динамічній пам'яті. Така необхідність виникає, наприклад, при розробці систем автоматизованого проектування (САПР): розмірність математичних моделей, використовуваних в САПР, може значно відрізнятися в різних проектах; статичний (тобто на етапі розробки САПР) розподіл пам'яті в цьому випадку, як правило, неможливо. Нарешті, динамічна пам'ять широко використовується для тимчасового запам'ятовування даних при роботі з графічними і звуковими засобами ПК.

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

Адреси і покажчики

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

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

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

У ПК адреси задаються сукупністю два шестнадцатіразрядних слів, які називаються сегментом і зсувом. Сегмент - це ділянка пам'яті, що має довжину 65536 байт (64 Кбайт) і що починається з фізичної адреси, кратної 16 (тобто Про, 16, 32, 48 і так далі). Зсув вказує, скільки байт від початку сегменту необхідно пропустити, щоб звернутися до потрібної адреси.

Адресний простір ПК складає 1 Мбайт (йдеться про так званій стандартній пам'яті ПК; на сучасних комп'ютерах з процесорами 80386 і вище адресний простір складає 4 Гбайт, проте в Турбо Паськале немає засобів, що підтримують роботу з додатковою пам'яттю; при використанні середовища Borland Pascal with Objects 7.0 така можливість є). Для адресації в межах 1 Мбайта потрібне 20 двійкових розрядів, які виходять з двох шестнадцатіразрядних слів (сегменту і зсуву) таким чином (рис. 16.1): вміст сегменту зміщується вліво на 4 розряди, праві розряди, що звільнилися, заповнюються нулями, результат складається з вмістом зсуву.