НОУ ІНТУЇТ | лекція | Використання мови Free Pascal для обробки масивів

1. 5.5 Обчислення суми і твори елементів масиву Знаходження суми і твори елементів масиву аналогічні...
2. 5.7 Сортування елементів в масиві
3. 5.7.1 Сортування методом "бульбашки"
4. 5.7.2 Сортування вибором

5.5 Обчислення суми і твори елементів масиву

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

Дан масив X, що складається з n елементів. Знайти суму елементів цього масиву. Змінної S присвоюється значення, рівне нулю, потім послідовно підсумовуються елементи масиву X. Блок-схема алгоритму розрахунку суми наведена на Мал. 5.19 .

Мал.5.19.

Алгоритм знаходження суми елементів масиву

Відповідний алгоритму фрагмент програми буде мати вигляд:

s: = 0; for i: = 1 to n do s: = s + x [i]; writeln ( 's =', s: 7: 3);

Знайдемо твір елементів масиву X. Рішення завдання зводиться до того, що значення змінної Р, в яку попередньо була записана одиниця, послідовно множиться на значення i -го елемента масиву. Блок-схема алгоритму наведена на Мал. 5.20 .

Відповідний фрагмент програми буде мати вигляд:

p: = 1; for i: = 1 to n do p: = p * x [i]; writeln ( 'P =', P: 7: 3);
Мал. 5.20. Алгоритм знаходження твори елементів масиву

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

Розглянемо задачу пошуку максимального елемента (Max) і його номера (Nmax) в масиві X, що складається з n елементів.

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

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

Відповідний фрагмент програми має вигляд:

Max: = X [1]; Nmax: = 1; for i: = 2 to n do if X [i]> Max then begin Max: = X [i]; Nmax: = i; end; write ( 'Max =', Max: 1: 3, 'Nmax =', Nmax);

Алгоритм пошуку мінімального елемента в масиві буде відрізнятися від наведеного вище лише тим, що в умовному блоці і, відповідно, в конструкції if тексту програми знак зміниться з> на <.

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

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

і в порядку убування, якщо

Багато алгоритми сортування засновані на тому факті, що переставляти два елементи треба таким чином, щоб після перестановки вони були правильно розташовані один щодо одного. При сортуванні по зростанню після перестановки елемент з меншим індексом повинен бути не більше елемента з великим індексом2. Розглянемо деякі з алгоритмів.

5.7.1 Сортування методом "бульбашки"

Найбільш відомим методом сортування є сортування масивів бульбашковим методом. Її популярність пояснюється запам'ятовується названіем3 і простотою алгоритму. Сортіровкаметодом "бульбашки" заснована на виконанні в циклі операцій порівняння і при необхідності обміну сусідніх елементів. Розглянемо алгоритм бульбашкового сортування на прикладі сортування за зростанням більш докладно.

Порівняємо перший елемент масиву з другим, якщо перший виявиться більше другого, то поміняємо їх місцями. Потім порівняємо другий з третім, і якщо другий виявиться більше третього, то поміняємо і їх. Далі порівнюємо третій і четвертий, і якщо третій більшого четвертого, їх також міняємо місцями. Після трьох цих порівнянь найбільшим елементом стане елемент з номером 4. Якщо продовжити порівняння сусідніх елементів: порівняти четвертий з п'ятим, п'ятий з шостим і т. Д. До порівняння -го і n-го елементів, то в результаті цих дій найбільший елемент стане на останнє ( -е) місце.

Таблиця 5.8. Процес упорядкування елементів в масиві по зростанню Номер елемента 1 2 3 4 5 Вихідний масив 7 3 5 4 2 Перший перегляд 3 5 4 2 7 Другий перегляд 3 4 2 5 7 Третій перегляд 3 2 4 5 7 Четвертий перегляд 2 3 4 5 7
Мал. 5.22. Алгоритм впорядкування по зростанню методом "бульбашки"

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

В табл. 5.8 детально показаний процес упорядкування елементів в масиві.

Неважко помітити, що для перетворення масиву, що складається з елементів, необхідно переглянути його раз, кожного разу зменшуючи діапазон перегляду на один елемент. Блок-схема описаного алгоритму приведена на Мал. 5.22 . Для обміну двох елементів в масиві (блок 4) використовується буферна змінна , В якій тимчасово зберігається значення елемента, що підлягає заміні.

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

program upor_massiv; var i, j, n: byte; X: array [1 .. 100] of real; b: real; begin writeln ( 'введіть розмір масиву'); readln (n); for i: = 1 to n do begin write ( 'X [', i, '] ='); readln (X [i]); end; writeln ( 'масив X'); for i: = 1 to n do write (x [i]: 5: 2, ''); writeln; for j: = 1 to n-1 do for i: = 1 to nj do if X [i]> X [i +1] then {Якщо поточний елемент повинна перевищувати, то} begin {поміняти їх місцями.} b: = X [i]; {Зберегти значення поточного елемента.} X [i]: = X [i + 1]; {Замінити поточний елемент наступним.} X [i +1]: = b; {Замінити наступний елемент змінної b.} End; writeln ( 'упорядкований масив'); for i: = 1 to n do write (X [i]: 5: 2, ''); writeln; end.

на Мал. 5.23 наведені результати роботи цієї програми.

Для упорядкування елементів в масиві по спадаючій їх значень необхідно при порівнянні елементів масиву замінити знак> на <(див. Блок 3 на Мал. 5.22 ).

Розглянемо наступний алгоритм сортування.

5.7.2 Сортування вибором

Для сортування елементів масиву по зростанню (по спадаючій) можна скористатися алгоритмом сортування вибору максимального (мінімального) елемента. Алгоритм вибором наведено у вигляді блок-схеми на Мал. 5.24 .

Мал.5.24.

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

Знайдемо в масиві найбільший елемент (блоки 2-5) і поміняємо його місцями з останнім елементом (блок 6). Після цього максимальний елемент встане на своє місце. Тепер треба повторювати ці дії (блоки 2-6), зменшивши кількість переглядаються елементів на одиницю (блок 7) до тих пір, поки кількість розглянутих елементів не стане рівним одному (блок 8). У зв'язку з тим, що ми на кожному кроці зменшуємо кількість елементів на 1, то, щоб не втратити розмір масиву (N), необхідно на початку алгоритму переписати N в змінну K (блок 1) та зменшувати вже значення K.

При упорядкуванні масиву по спадаючій необхідно переміщати мінімальний елемент. Для цього в алгоритмі ( Мал. 5.24 ) В блоці 4 досить поміняти знак> на знак <.

Нижче наведено фрагмент програми впорядкування масиву по зростанню, використовуючи сортування вибором максимального елемента.

k: = n; repeat max: = x [1]; nom: = 1; for i: = 2 to k do if max <X [i] then begin max: = X [i]; nom: = i; end; b: = x [nom]; x [nom]: = x [k]; x [k]: = b; k: = k -1; until k = 1;

Наступним важливим алгоритмом обробки масивів є алгоритм видалення елемента з масиву.