Лекції >> Програмування, комп’ютери і кібернетика >> Робота з масивами даних

Розв’язування на ЕОМ багатьох задач пов’язане з обробкою великої кількості числових даних. Ці данні подаються, як правило, в вигляді різноманітних таблиць — масивів, множин.

У програмуванні під масивами розуміють певним чином організовану сукупність однотипних елементів, яка може розглядається як єдине ціле. Кожен масив має найменування, а кожен елемент має свій номер (індекс). Тому будь-які дані можна знайти у масиві,  знаючи лише ім’я масиву та індекси потрібних елементів.

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

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

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

Двовимірний масив — це масив, що містить елементи, в яких номер  складається з двох індексів. Перший індекс вказує номер рядка, а другий – номер стовпця, в якому знаходиться елемент. Двовимірний масив іноді ще називають матрицею. У програмуванні про двовимірний масив говорять як про структуру, що утворена з одновимірного масиву, у якому кожен елемент сам є одновимірним масивом. Двовимірний масив містить в со ність елементів одного і того ж типу. У такому масиві кожен елемент має номер, що складається з одного індексу. Такий масив ще називають вектором.

Двовимірний масив — це масив, що містить елементи, в яких номер  складається з двох індексів. Перший індекс вказує номер рядка, а другий – номер стовпця, в якому знаходиться елемент. Двовимірний масив іноді ще називають матрицею. У програмуванні про двовимірний масив говорять як про структуру, що утворена з одновимірного масиву, у якому кожен елемент сам є одновимірним масивом. Двовимірний масив містить в собі n х m елементів (n – кількість рядків, m – кількість стовпчиків).  Подібно до цього задаються тривимірні, чотиривимірні і т.д. масиви.

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

Пошук найбільшого елемента масиву.

Нехай до пам’яті ЕОМ введено деякий масив чисел, елементи якого мають імена А(1), А(2), ... , А(N). Серед елементів масиву знайдемо найбільше число та виведемо його на пристрій в мер рядка, а другий – номер стовпця, в якому знаходиться елемент. Двовимірний масив іноді ще називають матрицею. У програмуванні про двовимірний масив говорять як про структуру, що утворена з одновимірного масиву, у якому кожен елемент сам є одновимірним масивом. Двовимірний масив містить в собі n х m елементів (n – кількість рядків, m – кількість стовпчиків).  Подібно до цього задаються тривимірні, чотиривимірні і т.д. масиви.

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

Пошук найбільшого елемента масиву.

Нехай до пам’яті ЕОМ введено деякий масив чисел, елементи якого мають імена А(1), А(2), ... , А(N). Серед елементів масиву знайдемо найбільше число та виведемо його на пристрій виводу (екран).

Пропонується така послідовність дій для розв’язання даної задачі:

1. Оберемо змінну для шуканого числа, наприклад, Мах. Перед циклічним переглядом елементів масиву спочатку приймемо за шукане максимальне значення перший елемент масиву. Для цього змінній Мах присвоїмо значення першого елемента масиву - Мах := А(1).

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

Для цього організуємо цикл з параметром і, що змінюється від 2 до n. У тіло циклу вмістимо конструкцію розгалуження: якщо умова А(і)>Мах істинна, то Мах := А(і).

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

3. Вивести значення змінної Мах.

Подібні дії можна виконати і для того, щоб відшукати найменший елемент масиву.

Сортування елементів масиву.

Часто у задачах виникає потреба певним чином розташувати елементи масиву, впорядкувати їх - у порядку зростання або спадання. Така робота називається сортуванням масиву. З багатьох відомих алгоритмів розглянемо сортування вибором та обмінне сортування.

Алгоритм сортування вибором такий:

1. Встановити найменший елемент масиву та його номер.

2. Поміняти місцями знайдений найменший і перший елементи.

3. Виконати пункти 1 і 2 над залишком масиву (масивом без першого елемента). Пункт 3 повторювати доти, доки кількість елементів у залишку масиву не скоротиться до одного.

На прикладі масиву з п'ятьох елементів проілюструємо зміну їх порядку у міру повторення пункту 3:

40 50 10 20 30

10 50 40 20 30

10 20 40 50 30

10 20 30 50 40

10 20 30 40 50

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

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

Розглянемо як змінюється значення масиву з п'ятьох елементів (30, 20, 10, 50, 40) на кожному кроці сортування:

Вихідне значення: 40 50 10 20 30.

Після 1-го кроку : 40 10 20 30 50.

Після 2-го кроку : 10 20 30 40 50.

Навчальна алгоритмічна мова.

У НАМ елементи масивів даних задаються як елементи таблиць. Таблиці спочатку описуються: вказується їх тип, ім’я та розмірність.

В Е-практикумі для описання типу використовуються службові слова вещтаб, целтаб.  Тип литтаб відсутній (не можна задавати таблиці, що складаються з рядків). Після службового слова записують ім’я таблиці, за яким у квадратних дужках вказують розмірність: номер першого елемента, символ двокрапка, номер останнього елемента.

Наприклад:

          вещтаб А [ 1 : 10 ] – одновимірний масив (10 елементів);

          целтаб В [ 3:7, 1:10 ] - двовимірний масив (50 елементів).

Доступ до окремого елемента масиву здійснюється шляхом індексування. Наприклад,

          А [ 1 ],  B [ 3, 1 ] – перші елементи описаних масивів.

Basic.

На мові Basic для опису масивів використовують оператор DIM, в якому вказують імя масиву, тип та в круглих дужках розмірність – макси­маль­ні значення індексів. Наприклад:

DIM А (20) – одновимірний масив дійсних чисел з 21 елементом;

DIM В% (4,10) – двовимірний масив цілих чисел з 55 елементами.

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

А(1) – другий елемент масиву А;

В (4, 10) – останній елемент масиву В.

Якщо ж наперед відомо, що кількість елементів масиву не буде перевищувати 10 (індекси від 0 до 9), то такий масив можна спеціаль­но не описувати.

Якщо при виконанні програми на певному етапі деякий масив стає зайвим або не вистачає оперативної пам’яті для роботи програми, то можна звільнити зарезервовану під масив пам’ять за допомогою оператора ERASE, вказавши ім’я масиву. Наприклад:

ERASE А       - вилучити масив А;

ERASE А, В%   - вилучити масиви А і В.

На етапі налагодження програми з масивами даних зручно використовувати оператори DATA, READ, Restore.

Pascal.

Для описання масивів використовується зарезервоване слово array.

Наприклад, опишемо одномірний масив А, який може містити 10 елементів – дійсних чисел, та двомірний масив В, який може містити 5х10 елементів – цілих чисел:

   Type

         dataA      = array [ 1 .. 10 ]  of real ;

         masiv      = array [ 3 .. 7, 1 .. 10 ] of integer ;

   Var

         A : dataА ;

         В  : masiv ;

Доступ до окремого елемента масиву здійснюється шляхом індексування. Наприклад, А [ 1 ],  B [ 3, 1 ] – перші елементи описаних масивів.

Якщо деякі масиви ідентичні за структурою та типом елементів, то над такими масивами як над послідовностями можна виконувати операції відношення “дорівнює”, “не дорівнює” та операцію присвоєння (змінній-масиву можна присвоїти існуючий масив раніше введених елементів), тобто ці операції можна виконувати над масивами в цілому. 

Арифметичні операції, введення та виведення елементів масиву не можна виконувати над послідовностями, а отже не можна їх виконувати і над масивами в цілому – вказані операції можна виконати тільки над окремими елементами.

 Приклад 1.  Знайти середнє арифметичне лінійної таблиці, що містить десять елементів

 початок

 

 

N

 

 

S := 0

 

 

i, 1, N, 1

 

 

A ( i )

 

 

S := S + A ( i )

 

 

 

 

SN := S / N

 

 

S

 

кінець                      

мал. 16

І етап. Дана лінійна таблиця – одновимірний масив певної розмірності. Спочатку потрібно вказати розмірність N масиву, а потім ввести елементи масиву. Значення елементів масиву вводяться у циклі (Basic, Pascal) або записуються у розділі рез (НАМ). Середнє арифметичне для масиву – це частка суми всіх його елементів та їх кількості. Щоб обчислити суму елементів масиву необхідно використати цикл та виконати дії, аналогічні прикладу на стор. 55. Тому операції з введення елементів масиву та сумування об’єднаємо в тілі одного циклу (Basic, Pascal).

ІІ етап. Складемо блок-схему (мал. 16).

алг Аn (цел n, вещтаб A [1:10], вещ Sn)

   арг n, An = 10, 0,1,2,3,4,6,7,8,9,10

   рез Sn

нач вещ S, цел i

      S :=0

      нц  для i от 1 до n шаг 1

            S := S + A [ i ]

      кц

      Sn := S / n 

кон

НАМ-програма 8

ІІІ етап. Запишемо програму.

 

10 REM Сер. арифметичне

20 Input “Кількість елементів” ; N

30 DIM A (N)

40 S = 0

50 FOR i =1 TO N

60 INPUT A ( i )

70 S=S + A ( i )

80 NEXT

90 SN = S / N

100 PRINT “Сер. Ар. = ” ; SN

110 END

Basic-програма 8

 

Program An ;

   Var

      S, Sn    : Real ;

      i, N    : Integer ;

      A       : Array [ 1..10 ] of Real ;

Begin

   ReadLn (N) ; S := 0 ; 

   For i := 1 to N do

       Begin

           Read ( A [ i ] ) ;

           S := S + A [ i ]

       End ;

   Sn := S / N ;  

   WriteLn ( ‘ Сер. ар. = ’ , Sn :10 : 6 )

End.

 

 

Pascal-програма 8

IV етап. N=10, таблиця {0,1,2,3,4,6,7,8,9,10}. Середнє арифметичне- 5. n

 Приклад 2.  Для двовимірного масиву цілих чисел знайти мінімальний елемент та його індекси.

 початок

 

 

 N, M, B

 

Min := B (1,1)

 

 

i, 1, N, 1

 

 

j, 1, M, 1

 

 

Min > B(i, j)

 

Min := B (i, j)

X := i

Y := j

 

 

 

 

S

 

кінець                      

мал. 17

І етап. Введення розмірності масиву, елементів масиву здійснимо аналогічно до попереднього прикладу, тому описувати окремо послідовність таких дій не будемо, а відповідні записи внесемо до блоку введення. Пошук мінімального елементу масиву аналогічний пошуку максимального елемента, розглянутому вище (стор. 61).

Зауважимо лише, що у задачі дано двовимірний масив, тому спочатку перший елемент масиву приймаємо за мінімальний (Min:=B(1,1)), а потім для перегляду елементів масиву використовуємо два цикли: цикл з параметром j, що вкладений у цикл з параметром і. Це дозволяє для кожного значення і проглянути всі значення j. За параметром j забезпечується зміна другого індексу (номер стовпчика), а за параметром і – першого індексу (номер рядка).

ІІ етап. Блок-схема (мал. 17).

алг Min2 (целтаб B [1:2,1:3], цел min, x, y, N, M)

   арг N, M, B = 2, 3, 0, -5, 1, 4, 2, 1

   рез min, x, y

нач  цел i, j

   min := B [1,1]

   x :=1

   y :=1

   нц  для i от 1 до N шаг 1

   .     нц для j от 1 до M шаг 1

   .     .  если Min > B [ i, j ] 

   .     .  то    Min := B [ i, j ]

   .     .            x := i ;

   .     .            y := j

   .     .  все

   .     кц

   кц

   Min := Min

   x := x

   y := y

кон

НАМ-програма 9

ІІІ етап. Запишемо програму.

10 REM Мінімальне

15 INPUT N, M

20 DIM B(N,M)

40 FOR I=1 TO N

50 FOR J=1 TO M

60 INPUT B(I, J)

70 NEXT J

80 NEXT I

90 MIN=B(1,1): X=1: Y=1

100 FOR I=1 TO N

110 FOR J=1 TO M

120 IF MIN > B (I, J) THEN MIN=B(I, J) : X=I : Y=J

130 NEXT J

140 NEXT I

150 PRINT “ Міn= ” ; MIN

160 PRINT ”індекси”; X , Y

160 END

 

 

Program Minimum;

   Const

      N = 2 ; M = 3 ;

   Var

      Min, I, J, X, Y         : integer ;

      B       : array [ 1..N, 1..M ] of integer ;

Begin

   For I := 1 to N do

       For J := 1 to M do

           Read ( B [ I, J ] ) ; 

   Min := B [1,1] ;  X:=1 ; Y:=1 ;

   For I := 1 to N do

       For J := 1 to M do

           If Min > B [ I, J ] Then

               Begin

                 Min := B [ I, J ] ; X:=i ; Y:=J

               End ;       

   WriteLn(‘Міn’, Min :10, ‘X=’, X :3, ‘Y=’, Y :3 )

End.

Basic-програма 9

 

Pascal-програма 9

IV етап. N=2, M=3, масив . Мін. елемент В (2,1)= –5. n

Схожі матеріали
05.10.2012 Введення та виведення даних, розробки та опису лінійних програм.
20.12.2011 Pascal - лабораторні роботи - для студентів III-го курсу (лекції Ляшенко Б.М.)
12.12.2010 Робота з підпрограмами
12.12.2010 Робота з рядковими та символьними величинами.
12.12.2010 Робота з циклічними програмами
12.12.2010 Робота з масивами даних.
12.12.2010 Розробка та описання програм з розгалуженнями
12.12.2010 Початки програмування
12.12.2010 Етапи розв’язання задач з використанням ЕОМ
12.12.2010 Поняття про алгоритм

Тести даної категорії
12.12.2010 ПОЧАТКИ АЛГОРИТМІЗАЦІЇ. ВСТУП ДО ПРОГРАМУВАННЯ

Останні створені тести
28.03.2016 Ахметов Р. Ф. Основи наукових досліджень. Тести. 500 питань
16.11.2015 Олімпійські ігри Стародавньої Греції. Відродження олімпійських ігор. Олімпійський рух сучасності.
28.10.2015 British Writers. Тест для студентів 4 курсу ННІ педагогіки
27.10.2015 The Passive Voice. Тест для студентів 2 курсу ННІ педагогіки
27.10.2015 Articles. Тест для студентів 1 курсу неспеціальних факультетів
27.10.2015 The Active Voice. Тест для студентів 2 курсу ННІ педагогіки
08.10.2014 INTEL
22.10.2012 Цивільний захист
28.09.2012 Питання для поточного контролю
26.09.2012 Мовнокомунікативна компетентність. Орфографічна складова
Рекомендовані лекції
23.09.2014 Котлова Л.О. Психологія конфлікту : курс лекцій
12.12.2010 Обробка графічної інформації
12.12.2010 Введення та виведення даних з використанням текстових файлів
12.12.2010 Циклічні програми
27.09.2012 Літературознавство як наука
12.12.2010 ЕОМ як виконавець алгоритму. Мови програмування
22.02.2016 ОС та СП. Тема 2. Процеси та потоки. Слайди
10.01.2015 Publisher створення візитки
12.12.2010 Порядковий тип даних
28.09.2014 Лекції з курсу "Основи психокорекції"