четверг, 24 января 2013 г.

Масиви

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

Масив - це великий простір чогось однорідного за типом.
(Зі словника іноземних слів, 1954 р.)
Масив у програмуванні - це тип структури даних, що має складені значення. (З Оксфордського словника англійської мови, 1995 р.)
Масив - це впорядкований скінченний набір елементів (даних) одного типу. Зазвичай працюють з масивами, які містять числа.
Масивом називається скінченна послідовність змінних одного типу, які мають однакове ім'я та різняться порядковим номером.

Індексом називається порядковий номер елемента масиву.

Отже, введено новий тип — масив. Усі типи, які досі були вам відомі, називаються простими. Масив є прикладом структурованого типу, тобто він, у свою чергу, складається з елементів іншого типу.

Як звернутися до елементів цього масиву? Для цього необхідно вказати індекс.

Наприклад,

T[2], T[5], T[i], T[i + j].

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

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

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


Оскільки у мові Pascal усе з чим ми працюємо потрібно оголошувати, то масиви також потрібно оголосити. Це можна зробити кількома способами:

у полі const

const <ім'я змінної>=array[1 .. <клькість елементів>] of <тип> = (1,2,3, ... <значення>);

у полі type

type <ім'я типу>=array[1 .. <кількість елементів>] of <тип>;
var <ім'я змінної> : <ім'я типу>; 

у полі var

var <ім'я змінної> : array[1 .. <кількість елементів>] of <тип>;

Приклад:

type Mas = array[1 .. 5] of integer;
var a : Mas;

Масиви бувають одновимірними (у вигляді послідовності чисел), двовимірними (у вигляді таблиць чисел розміром m x n) і багатовимірними (3-,4-вимірні і т.д. 3-вімірні - це об'ємний простір з комірками, а 4-вимірні і більше - це фантастично-абстрактні поняття). 

Масив називається одновимірним, якщо для задання місцеположення елемента в масиві необхідно вказати значення лише одного індексу.
Масив називається двовимірним, якщо для задання місцеположення елемента в масиві необхідно вказати значення двох індексів.
Запам'ятайте, що у двовимірних масивах перший індекс завжди вказує на номер рядка, а другий - на номер стовпчика в цьому рядку!
Розмірність масивів у Pascal необмежена, вона визначається лише об'ємом пам'яті вашого комп'ютера.
Резонним буде запитання: а як же розташовуються масиви в пам'яті комп'ютера? Пояснення для одновимірних масивів дуже просте – всі вони розташовані в пам'яті підряд. Двовимірні масиви розташовуються дещо інакше - спочатку елементи пер­шого рядка, потім другого і т. д. Розташування масивів більшої розмірності пояснюється аналогічно.
Залишилося з'ясувати, як пояснити програмі, що ви працюватимете з елементами, які утворюють масив значень.Загальний вигляд опису масивів:
<ім'я змінної>: array [<межі зміни індексів>] of <тип>.
Наприклад,
varA: array[1..10] of real;B: array[1..100,1..100] of byte;C: array[1..100] of array[1..100] of byte.
Цікаво, що другий і третій приклади описують однакові ма­сиви. Справді, адже будь-яку таблицю можна розглядати як послідовність рядків, де кожний рядок у свою чергу є також послідовністю. Звернення до елементів останнього масиву буде мати такий вигляд: C[i][j].
Зауваження.
По-перше, межі індексів завжди вказуються через два символи «.».
По-друге, при розподілі пам'яті в опи­совій частині програми під масив буде зарезервовано стільки місця, скільки передбачає вказана кількість елементів масиву. Тому при виконанні програми ви можете використовувати кількість елементів не більшу, ніж описана в розділі змінних.
По-третє, межі зміни індексів повинні бути сталими величи­нами, а не змінними, інакше невідомо буде, скільки місця не­обхідно відвести в пам'яті під такий масив.

Розглянемо таку задачу.
Нехай дано таблицю здійснення рейсів N автобусами протягом M днів. Рейси, що відбулися, позначаються в таблиці цифрою 1, а ті, що з деяких причин не відбулися, - цифрою 0. Треба скласти програму, яка підраховує кількість рейсів, що не відбулися.
Приклад програми
program voyage;
var R :array[1..30,1..100] of byte;

і, j, n, m, count : integer;
begin
write ('Задайте кількість автобусів: ');
repeatreadIn(n) until (n > 0) and (n <= 30);
write ('Задайте кількість днів: ');
repeatreadln (m) until (m > 0) and (m <= 100);
writeln ('Задайте інформацію про здійснення рейсів: ');
for i := 1 to n do for j := 1 to m do beginwrite (i, ' автобус, ', j, ' день: ');
repeatreadln(R[i,j]) until (R[i, j] = 0) or (R[i, j] = 1) end;count := 0;
for і := 1 to n do
for j := 1 to m do
if R[i. j] = 0 then count := inc (count);
writeln ('Кількість нездійснених рейсів: ', count:5);
repeat
until
Key
Pressed
end.
У цій програмі використано нову стандартну процедуру мови Pascal inc (count). Ії призначення - заміна значення пара­метра на 1. Можливий ще такий варіант використання цієї процедури: inc (n, step). У цьому разі збільшення параметра п відбуватиметься з кроком step. У Pascal існує альтернативна процедура Dec, яка зменшує значення вказаного параметра.

Якщо ви спробували виконати цю програму на комп'ютері, то, напевно, під час виправлення можливих помилок вам що­разу доводилося знову і знову задавати початкові дані. Можли­вості мови Pascal дають змогу уникнути такої незручності.

Повернемося до початку знайомства з Pascal, де вводилося поняття про розділ констант const. У цьому розділі ідентифіка­торами позначаються сталі величини. Надалі в програмі замість цих сталих величин вказуватимемо лише відповідні їм ідентифікатори. Зручність полягає в тому, що якщо знадобить­ся поміняти значення якоїсь константи, то достатньо це зроби­ти тільки в розділі const, не чіпаючи всієї програми.

Наприклад, можна розміри масиву задати таким чином:
const SizeLine = 100;
SizeColumn = 100;
var A: array [1..SizeLine, 1..SizeColumn] of real;
.............................................
repeatread (n, m) until (n > 0) and (n <= SizeLine) and (m > 0) and (m <= SizeColumn);


Зверніть увагу на те, що в розділі констант стоїть символ «=», а не символ «:=».Використовуючи в програмі константи, необхідно врахувати таку особливість: їх значення не можна змінювати під час виконання програми. Тобто ідентифікаторам, що визначають

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

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

constA:array[1..3, 1..4] of real= ((1.5, 1.2, 2.1,-4.42), (2.4,5.7,-1, 45.4), (-1.1,7, 45,-10));

3 останнього прикладу видно, що в розділі констант можна задавати ще й тип. Такі константи називаютьсятипізованими. Значення масивам задаються таким чином: в одновимірних масивах вони записуються через кому, у двовимірних – значення елементів рядків беруться у круглі дужки, для тривимірних – аналогічним чином. Відмінність типізованих констант від простих, для яких тип не вказується, полягає в тому, що їх значен­ня можна змінювати під час виконання програми.

Якщо ж вас не цікавлять конкретні дані, які будуть надані елементам масиву під час виконання програми, то скористайтеся можливостями стандартної процедури Pascal Randomize та функції Random (n), що генерують випадкові числа. Параметр n (типу Word) у процедурі Random визначає праву межу інтервалу, в якому будуть визначатися випадкові числа (ліва межа завжди 0). Функція Random може задаватися і без параметра. У цьому разі вона генеруватиме те дійсне число в діапазоні [0; 1). А для того щоб випадкові числа в програмі з кожним її наступним запуском не повторювалися (хоча вони і випадкові, але послідовність цих чисел постійна), то скористайтеся процедурою Randomize, яка встановить початок відрахунку випадкових чисел залежно від поточного стану системного годинника вашого комп'ютера.

Фрагмент програми, що використовує випадкові числа, може виглядати так:

randomize;
for і := 1 to n doa[i] := random (100);


Одновимірні масиви 
  Введення масиву з клавіатури
     for i:=1 to n do readln(a[i]);    тут (і надалі) і - параметр, n - кількість елементів у 
                                                       масиві, а -  одновимірний масив
  Друк масиву на екран 
     for i:=1 to n do writeln(a[i]);
   Перебір всіх елементів
     for i:=1 to n do
        begin
       if a[i]=0 then s:=s+1;    - кількість елементів, які відповідають умові (у даному разі 
                                       ті, що рівні  нулю). Кількість буде записана до змінної s 
      if a[i]=0 then k:=i;        - порядковий номер елементу, який відповідає умові (=0)
        end;
  Пошук мінімального/максимального елеманту 
Припускаємо, що це перший і переглядаємо масив. Якщо зустрінемо більший (чи менший) за нього елемент, то цей елемент стає максимальним (мінімальним). Розглянемо пошук максимального:
max:=a[1]; 
for i:=1 to n do
   if a[i]>max then max:=a[i];
  Сортування за зростанням/спаданням 
Переглянемо масив n разів. Кожного разу розглядаємо всі елементи від 1 до n-1. Якщо елемент більший (сортування за зростанням) за нступний за ним, то міняємо їх місцями.
fo j:=1 to n do        {переглядаємо масив n разів}
for i:=1 to n-1 do    {переглядаємо кожного разу елементи від 1 до n-1 (бо можемо                          
                      поміняти міцями  a[n-1] і a[n] - а у програмі буде a[i] та a[i+1] при i=n-1)}
    if a[i]>a[i+1] then
       begin
            b:=a[i];       {зберігаємо значення a[i] в іншу змінну, тип якої такий як і   
                                               елементів масиву}
            a[i]:=a[i+1];  {власне міняємо місцями елементи - записуємо менше значення на 
                                              місце    більшого}
            a[i+1]:=b;       {"витягуємо" з пам'яті значення a[i], більше, і записуємо на нове   
                                                               місце}
       end; 
Такий метод сортування називається бульбашковим (або "Метод бульбашки"). Різні особи по-різному трактують цю назву, тому я взагалі не буду трактувати її. Сприймайте цей метод так, як його обізвали.
Двовимірні масиви (n x m)
  Введення масиву з клавіатури 
for i:=1 to n do       {перебір n рядків}
  for j:=1 to m do     {перебір m стовпців}
    readln(a[i,j]);         {власне ввід кожного елементу}
  Вивід масиву на екран 
Щоб вивести двовимірний масив на екран у вигляді таблиці роблять наступне: 
for:=1 to n do     {перебір рядків}
  begin
     for j:=1 to m do write(a[i,j],' ');      {вивід кожного рядка}
     writeln;                                       {перехід на новий рядок}
  end; 

Приклад програми.
Утворити і вивести масив у з елементами у(к), к=1,12. Перший додатний елемент поміняти місцями з максимальним
program Masuvu;
uses crt;
var y,g:array [1..12] of real; max,h:real;
k,n,m:integer;
begin 
clrscr; 
max:=-1000000; 
n:=0; 
for k:=1 to 12 do 
begin 
y[k]:=sin(k*k)*cos(k*k*k)-sin(k)+5.2; 
if y[k]>max then 
begin 
max:=y[k]; 
m:=k; 
end; 
if y[k]>0 then 
begin 
n:=n+1; 
g[n]:=y[k]; 
h:=g[1]; 
end; 
if y[k]=g[1] then 
begin 
y[k]:=max; 
y[m]:=h; 
end; 
writeln (k,' element ',y[k]:5:2); 

if n>0 then writeln ('pershuj dodatnij element',g[1]:5:2)else writeln('nema dodatnih elementiv'); 
writeln ('maksumalnuj element - ', m,' -',max:5:2); 
readln; 
end. 
end.

Комментариев нет:

Отправить комментарий