Масиви: Заповнення і сортування
Знайомимося з масивами
nbsp nbsp nbsp nbsp nbsp Масиви, в загальному, є однією з найбільш складних тем в програмуванні для початківців. Насправді, головне - зрозуміти, а далі все піде як по маслу (ну, для кого як, звичайно ж!). Так що вчитуйтесь в наступний текст як можете.
nbsp nbsp nbsp nbsp nbsp Отже, масив - це набір однорідних даних (чисел, символів, слів), який має ім'я і послідовну нумерацію його елементів. Наприклад, список учнів - масив, учень 1 - такий-то, учень 5 - такий-то, учень 18 - такий-то; або алфавіт - буква 1 - "А", буква 5 - "Д", буква 15 - "Н", буква 7 - "Е". Як фізично представляється масив в комп'ютері, я розповідати не буду, а от як формально - розповім. Ось це і треба засвоїти.
nbsp nbsp nbsp nbsp nbsp Якщо нам потрібен масив, то ми повинні визначити його параметри - ім'я, розмірність і тип даних в ньому - оператором DIM в бейсике (DIM - від англ. "dimension"). Наприклад, нам потрібен масив COUNT, що складається з 20 цілих чисел. пишемо DIM COUNT (20) OF INTEGER. Або той же COUNT, але складається з 47 строкових змінних. Пишемо DIM COUNT $ (47) OF STRING - після імені масиву з рядками, як і після імені строкової змінної, ставиться символ "$". У Паскалі масив задається наступним чином - імя_массіва: Array [0..колічество_елементов] of тип - і пишеться в розділі оголошення пременися Var.
nbsp nbsp nbsp nbsp nbsp Перейдемо до конкретного прикладу. Припустимо, у нас є таблиця середніх температур на кожен день якогось року. Кожна температура кожного дня записується в змінних Day1, Day2, Day3. Day365. Треба знайти середню річну температуру. Можна записати так: Sred: = (Day1 + Day2 + Day 3 +. + Day365) / 365 ;, а можна занести всі дані в масив розмірністю 365, а потім, зрозумівши суму всіх температур, розділити її на 365. Так само легше? Ну ось. Єдиний мінус Паскаля - розмірність масиву задається ще до програми, її ніяк не змінити в перебігу самої програми, а в бейсике можна занести в змінну бажану розмірність масиву, а потім тут же завести масив цієї розмірності.
nbsp nbsp nbsp nbsp nbsp Індекс в масивах в різних мовах позначається по-різному. Так, в бейсике індекс змінної в масиві позначається круглими дужками "()", а в Паскалі - квадратними - "[]". Отже, що ми маємо по масивах:
- у масиву є ім'я, яке дає йому програміст;
- у масиву є тип який визначається ім'ям (тільки в бейсике) - тобто, якщо масив текстовий, то після його імені обов'язково ставиться символ "$";
- у масиву є розмірність, тобто, кількість елементів в ньому;
- у масиву є наскрізна послідовна індексація складових його елементів;
- у кожного елемента є значення (прізвище, буква, температура - в попередніх прикладах).
Оператор DIM для кожного конкретного масиву повинен задаватися тільки один раз в програмі до першого до нього звернення.
Насправді, нумерація елементів масиву починається з нуля, але нам звичніше і зручніше починати нумерацію з одиниці. Це, в общем-то ми не незаконно - можна почати нумерацію і з 5-го і з 10-го і хоч-с-якого елементу. В принципі, можна задати номер самого першого елемента в кожному масиві (тільки в бейсике) - оператором OPTION BASE n, де n буде номером першого елемента в кожному масиві.
Заповнення одновимірних масивів і виведення їх на екран
nbsp nbsp nbsp nbsp nbsp Подивимося на програму заповнення масиву та виведення його на екран:
nbsp nbsp nbsp nbsp nbsp Розберемося по порядку. Перший рядок запит про розмір нового масиву після очищення екрану. Потім створює новий масив MASS розмірністю в N елементів - тобто, скільки ми ввели. Потім, в циклі запитує у нас кожен елемент. Ми заповнили масив, і в пам'яті зберігаються всі введені елементи з іменами MASS (1), MASS (2), MASS (3). MASS (N). Після цього друкується порожній рядок, щоб поставити межу між набором масиву і виведенням його на екран. Потім в циклі кожен елемент масиву виводиться на екран в один рядок. У циклі введення масиву можна поставити оператор присвоювання MASS (I) = INT (RND (100)) наприклад - якщо вам не хочеться набирати все елементи - комп'ютер просто заповнить весь масив довільно.
nbsp nbsp nbsp nbsp nbsp Як я вже сказав, головне - зрозуміти. Якщо Ви зрозуміли, то сміливо йдіть далі.
найпростіші сортування
nbsp nbsp nbsp nbsp nbsp Однією з основних операцій над масивами є їх сортування, тобто, упорядкування елементів масиву по якомусь ознакою: найчастіше за зростанням або спаданням - для чисел, і за алфавітом - для символів і рядків.
nbsp nbsp nbsp nbsp nbsp Найрізноманітніших способів сортування існує безліч, але ми розглянемо тільки два з них - найпростіших, але, на жаль, не найефективніших.
Перший спосіб - це сортування вибором.
nbsp nbsp nbsp nbsp nbsp Припустимо, дано числовий масив розмірністю N, і нам треба впорядкувати його елементи по зростанню. Так ось, суть цього способу в наступному: Знаходимо максимальний елемент і ставимо його на своє місце - на останній, після чого зменшуємо розглянутий масив на 1, так як один елемент вже на своєму місці. Повторюємо цю справу ще раз, потім ще раз, і ще. І так - N-1 раз.
nbsp nbsp nbsp nbsp nbsp Розглянемо конкретний приклад. Нехай нам дано масив з п'яти елементів 8 4 9 6 7. Тепер пішли обробляти:- 8 4 7 6 9
- 6 4 7 8 (9)
- 6 4 7 (8) (9)
- 4 6 (7) (8) (9)
nbsp nbsp nbsp nbsp nbsp Другий спосіб сортування - це метод обміну або "бульбашки". Програма попарно порівнює елементи масиву, і, в разі, якщо вони розташовані не по зростанню, змінює їх місцями. Максимум (N-1) в квадраті перестановок - в "найгіршому" випадку - коли всі елементи розташовані по спадаючій.
nbsp nbsp nbsp nbsp nbsp Спробуйте реалізувати ці способи сортування.
двовимірні масиви
DIM S (4,3) \ Var S: Array [0..5,0..3] of Integer;
nbsp nbsp nbsp nbsp nbsp Далі - все так же, як і зі звичайними одновимірними масивами, тільки трохи складніше. Заповнювати їх теж легко.
Заповнення двовимірних масивів і виведення їх на екран
nbsp nbsp nbsp nbsp nbsp В обробці двовимірних масивів замість одного циклу, використовуються два - один в іншому.
Розглянемо приклад заповнення двовимірного масиву X (3,5) цілими довільними числами від 1 до 20, а потім виведення його на екран у вигляді таблиці.
nbsp nbsp nbsp nbsp nbsp Отже, з масивами ми начебто розібралися, давайте перейдемо до підпрограм.
підпрограми
А що ж це?
nbsp nbsp nbsp nbsp nbsp Іноді в певних місцях потрібно виконувати одну і ту ж послідовність якихось операторів, з різними вихідними даними. Для цього ми використовуємо підпрограми (від англ. "Subroutine").
nbsp nbsp nbsp nbsp nbsp Підпрограми зменшують обсяг тексту програми, істотно прискорюють процес її роботи, а також і полегшують роботу програмісту, якому не дуже-то хочеться набирати одну послідовність операторів кілька разів, які можуть збирати програму модульно, тобто, з закінчених шматочків - підпрограм. Це дозволяє створювати великі програми групі програмістів.
nbsp nbsp nbsp nbsp nbsp Розглянемо підпрограму обчислення такого виразу: Z = N! / (M! * (N-M)!). Змінні N і M, а також вираз (N-M) забезпечені знаком оклику, що означає факторіал (добуток всіх чисел до даного включно, якщо хто не знає). У вираженні нам три рази доведеться звернутися до підпрограми обчислення факторіала, виробляючи при цьому одні і ті ж дії з різними числами. У підпрограмі описується обчислення факторіала, а потім три рази в самій програмі виробляються різні операції з різними значеннями, отриманими в цій підпрограмі. Давайте подивимося:
nbsp nbsp nbsp nbsp nbsp Як завжди, розбираємо через підрядник. Початок стандартне - очищення екрану і запит вихідних даних. Потім починається найцікавіше. Йде звернення до підпрограми FACT, яка обчислює факторіал. Мінлива K є параметром підпрограми FACT. В основній програмі ми присвоюємо змінної K значення змінної N, для якої обчислюємо перший факторіал. Звернення до підпрограми здійснюється оператором GOSUB, після якого вказується ім'я підпрограми, до якої потрібно перейти (у нас це FACT). Підпрограма виконує всі дії в ній і знаходить факторіал, після чого оператор RETURN повертає інтерпритатор до основної програми.
Оператор RETURN передає управління в основну програму на оператор, наступний за зверненням до підпрограми GOSUB.
nbsp nbsp nbsp nbsp nbsp Результатом підпрограми стала змінна P, в якій зберігається значення факторіала. Запам'ятовуємо перше отримане значення (N-факторіал) в змінної X1. Це необхідно зробити, тому що підпрограма буде виконуватися ще два рази, і кожного разу змінна P буде змінюватися. Потім повторюємо дії для змінних M і (N-M), відповідно. Причому, в останньому випадку отримане значення факторіала запам'ятовувати вже не треба, тому що більше звернень до підпрограми не буде. Усе! Залишилося тільки вивести значення виразу на екран і завершити програму.
Звикайте виконувати самостійні шматки програм у вигляді підпрограм. Програмування з використанням підпрограм - це хороший стиль! Про гарному стилі ми з Вами ще поговоримо.
nbsp nbsp nbsp nbsp nbsp Скажу ще пару слів про підпрограма в російській QBasic'е. Я показав Вам найпростіший спосіб написання і використання підпрограм, Але якщо Ви відчуваєте в собі сили, то спробуйте самостійно розібратися з такими потужними інструментами бейсика з написання підпрограм, як DECLARE SUB і CALL SUB. Не пошкодуєте!
nbsp nbsp nbsp nbsp nbsp З масивами і подпрограммами, здається, розібралися. Йдемо далі! .