mozok.click » Інформатика » Одновимірні масиви
Інформація про новину
  • Переглядів: 16443
  • Автор: admin
  • Дата: 18-09-2017, 10:46
18-09-2017, 10:46

Одновимірні масиви

Категорія: Інформатика

9.1. Основи роботи у середовищі Lazarus (повторення)

Пригадайте, що називають середовищем програмування; які основні функції воно повинно виконувати? Яке середовище програмування ви використовували у 5-7 класах; у 8 класі? Які недоліки, на вашу думку, мають ці середовища?

Загальні відомості про середовище Lazarus

Lazarus — це вільне інтегроване середовище візуального програмування мовою Free Pascal. У середовищі Lazarus реалізовані елементи об’єктно-орієнтованого програмування (ООП). Середовище функціонує під управлінням ОС Windows і Linux. Воно забезпечує розробку програм як у консольному, так і у візуальному режимах. Методика розробки програм у консольному режимі принципово не відрізняється від методики створення програм у середовищі Free Pascal. Тому далі основна увага буде приділятися візуальному режиму.

Початковий вигляд вікон середовища Lazarus зображено на рис. 1.

ООП — це методика розробки програм, в основі якої є поняття об'єкт, метод і клас. Основна ідея ООП полягає в об'єднанні даних, з якими працює програмний код, і процедур їх опрацювання в єдине ціле.



Головне вікно Lazarus (рис. 2) складається з трьох частин: головного меню (Файл, Правка та ін.), панелі інструментів (ліворуч під головним меню) і палітри компонентів на вкладках Standard, Additional та ін.

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

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

На палітрі компонентів розташована значна кількість компонентів, які користувач може розміщувати на формі в процесі створення інтерфейсу майбутньої програми. Ці компоненти згруповані за функціональним призначенням. За замовчуванням відкриваються компоненти групи Standart (див. рис. 2). Найчастіше з цієї групи застосовують такі компоненти:

Можна скористатися також компонентами групи Additional та ін. Для розкриття компонентів інших груп необхідно клацнути назву відповідної групи.

Компонент, перенесений на форму, є об'єктом. Кожний об'єкт має властивості і методи. Властивості визначають зовнішній вигляд об'єкта (ім'я, розміри, колір та ін.). Метод визначає поведінку об'єкта, наприклад, як він буде реагувати на клацання кнопки миші або зміну його розміру. Для налаштування властивостей об'єктів використовують Інспектор об'єктів. Значення деяких властивостей можуть змінюватися також програмно.

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

стрілкою розташовану на вкладці ліворуч.

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

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

Швейцарський інженер і дослідник світу програмування. Автор і один з розробників мови програмування Паскаль. Ніклаус Вірт є одним з найавторитетніших у світі вчених в області комп'ютерних наук, його книга «Алгоритми + структури даних = програми» вважається одним із класичних підручників зі структурного програмування.

Властивості поділяються на прості та складні. Прості властивості мають лише одне значення, а складні — декілька значень. Наприклад, властивість Caption (Заголовок) визначається рядком символів, а властивість Font (Шрифт) — це набір шрифтів, із яких можна вибрати один конкретний шрифт. Ліворуч від назви складних властивостей розташований трикутник. Якщо клацнути світлий трикутник (після цього він набуде темного кольору), то відкриється список його значень. Клацання на темному трикутнику приведе до згортання списку. Біля простих властивостей трикутника немає.

Для активації будь-якої властивості необхідно клацнути на ній кнопкою миші. Після активації властивості в кінці рядка може з’явитися кнопка з трьома точками і кнопка зі стрілкою вниз. Після клацання кнопки з трьома точками відкриється діалогове вікно для вибору відповідних значень. Наприклад, після активації властивості Color відкриється вікно Колір. Активація кнопки трикутника приведе до розкриття списку можливих значень цієї властивості.

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

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

Вікно редактора тексту (див. рис. 2) призначено для введення і редагування програмного коду. Фактично у редакторі тексту міститься структура (шаблон) майбутньої програми, що полегшує роботу програміста.

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

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

За замовчуванням на передньому плані міститься вікно редактора тексту, яке закриває форму. Активувати вікно можна за допомогою клавіші F12 або команди Вигляд ^ Перемкнути форму/модуль.

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

Програми у середовищі Lazarus розробляють у три етапи (рис. 3).

«Гарний токар працює у декілька разів краще, ніж середній, а гарний програміст коштує у 10000 разів більше, ніж звичайний».

Вілл Гей тс

Для створення інтерфейсу майбутньої програми у середовищі Lazarus використовують форму, а для введення і редагування програмного коду — вікно редактора. Після розміщення компонента на форму автоматично змінюється програмний код у вікні редактора тексту. Найчастіше використовують компоненти групи Standard, у якій містяться стандартні елементи інтерфейсу. Такими компонентами, зокрема, є: TButton (командна кнопка), TLabel (поле для розміщення однорядкових написів), TMemo (багаторядковий текстовий редактор) та ін.

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

Програма у середовищі Lazarus є проектом. Проект об’єднує декілька файлів, із яких створюється єдиний файл, що виконується. У результаті компіляції з файлів проекту створюється єдиний файл, що виконується, з розширенням exe. Ім’я файла збігається з іменем проекту. Користувач розробляє програмний модуль, усі інші додаються до проекту автоматично. Заголовок модуля починається ключовим словом unit, за яким слідує ім’я модуля і крапка з комою. Розділ опису починається ключовим словом interface. Тут описуються компоненти програмного коду: типи, класи, процедури і функції. Розділ implementation (див. рис. 1) містить програмний код опрацювання даних, який розробляє користувач.

Запитання для перевірки знань

Які вікна має середовище Lazarus?

За допомогою яких команд виконується компіляція і запуск програми?

Для чого призначено вікно редактора тексту?

Для чого призначена панель інструментів головного вікна?

Як встановлюються події для об'єктів, розташованих на формі?

Для чого призначено вікно інспектора об'єктів?

Завдання для самостійного виконання

Запустіть середовище Lazarus. Відкрийте вікно форми. Змініть розміри і місце розташування вікна форми.

Розмістіть на формі компоненти: TLabel,

TEdit, TMemo, TListBox, TButton. Для кожного з них установіть необхідні властивості за власним бажанням.

На формі з іменем Моя робота розмістіть два компоненти TLabel, компонент TEdit

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

На формі з іменем Спільна робота розмістіть компоненти: TPopupMenu, TCheckBox, TMemo. Експериментальним шляхом спробуйте визначити їх функціональне призначення.


9.2. Поняття типів користувача і масиву

Пригадайте, які типи даних ви вивчали у 8 класі. Чому, на вашу думку, не можна в мовах програмування обмежитися лише простими типами даних?

У 8 класі ви вивчали базові типи даних середовища Lazarus. Нагадаємо, що базовими є прості (скалярні) типи. Існують п’ять стандартних простих типів: цілі, дійсні, символьні, булів-ські й тип дата-час. Простим типом є також перелічуваний тип, але він оголошується користувачем (приклади 1, 2). Складені типи будуються з простих за певними правилами. Серед складених (структурованих) найчастіше застосовуються масиви, формування яких засновано на використанні інших типів.

Незважаючи на те що середовище Lazarus має потужну структуру стандартних (вбудованих у мову) типів даних, воно надає також можливість створення нових типів, які називають користувацькими. Структура їх оголошення така: type <новий тип даних>=<визначення типу>; var <список змінних: новий тип даних>;

Масив — це структурований тип даних, елементи якого мають один тип, наприклад integer, char та ін.

Структура масиву може бути одновимірною (лінійною), двовимірною (табличною) та багатовимірною. Загальну структуру одновимірного масиву можна позначити так:

Місце елемента у масиві, тобто його порядковий номер, називають індексом. Індекс записують у квадратних дужках, наприклад запис x[i] означає і-й елемент масиву. Так, числа 105, 11, 173 , 35, 40 можна розглядати одновимірним масивом цілих чисел, у якому п’ять елементів. У прикладі 3 видно, що першим елементом масиву є монітор, другим — миша.

Перш ніж опрацьовувати масив, його потрібно оголосити. Оголошення можна зробити такими способами.

• У розділі змінних. Структура оголошення одновимірного масиву в цьому розділі така:

var <ім'я_змінної>: array [n1..n2] of <тип елементів масиву>;

Тут array — ключове слово, яке вказує, що змінна є масивом; у квадратних дужках визначається діапазон індексів: n1 — індекс першого елемента масиву; n2 — індекс останнього елемента масиву. Після слова of вказується тип елементів масиву (приклад 4).

Масив також може бути оголошений за такою структурою: var <ім'я змінної>: array [n1..n2] of <тип елементів>= (значення елементів);

Наприклад:

Для одночасного опрацювання декількох типів даних у багатьох мовах програмування, в тому числі у мові Free Pascal, застосовується спеціальний тип, який називають записом. Формат опису змінної типу запис такий:

У розділі типів. Структура оголошення масиву така:

Із наведеної структури видно, що після оголошення типу оголошується ім’я масиву.

Наприклад, type mas4=array [0..5] of real; var s: mas4;

У полі const. Оголошення масиву має таку структуру:

Наприклад, const mas5=array [1..4] of integer=(33, 54, 2, 32);

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

Наприклад, const n=7; var a: array [1..n] of integer;

Будь-якому елементу масиву можна присвоїти певне значення за допомогою оператора присвоювання. Наприклад, mas[4]:=5; — четвертому елементу одновимірного масиву mas присвоєно значення 5.

Запитання для перевірки знань

Наведіть визначення масиву.

Які існують структури масивів?

Назвіть способи оголошення масивів.

Як здійснюється звернення до елементів масиву?

Яким може бути тип індексу елемента масиву?

Наведіть загальну структуру одновимірного масиву.

Як оголошується одновимірний масив у розділі оголошення змінних?

За якою структурою оголошуються масиви в розділі типів?

Наведіть приклад оголошення одновимірного масиву в розділі const.

Завдання для самостійного виконання

Оголосіть у розділі змінних масив рядкового типу з елементами: файл, біт, папка, дані.

Оголосіть у розділі типів масив чисел: 2, 6,

2.1, 40, 7.

Оголосіть у полі const масив: процесор, пам'ять, плата, символ.

І Визначте значення елементів a[1] і a[3] в результаті оголошення масиву:

9.3. Введення і виведення значень елементів масиву

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

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

У візуальних додатках середовища Lazarus для формування масивів, уведення значень його елементів із клавіатури, а також виведення елементів найчастіше застосовуються багаторядкові текстові поля TMemo і TListBox, а також функції InputBox( ) і ShowMessage( ). Можуть застосовуватися також і однорядкові текстові поля TEdit і TLabel. Розглянемо створення, введення і виведення елементів одновимірних масивів на конкретних прикладах.

• Використання компонента TMemo для введення і компонента TListBox для виведення значень елементів однови-мірного масиву.

Програміст пише у середньому 10-12 рядків програмного коду, які потрапляють у кінцевий продукт.

Приклад 1. Розмістимо на формі компоненти: TMemo, TListBox і TEdit. Надамо відповідним властивостям цих компонентів значень згідно з рис. 1. Уведемо з клавіатури 10 назв найбільших річок України: Дніпро, Десна, Дністер, Сіверський Донець, Псел, Західний Буг, Горинь, Прут, Прип'ять, Сейм. Для цього активуємо об’єкт Метої, в інспекторі об’єктів виділимо властивість Lines і клацнемо в цьому рядку кнопку з трьома крапками. Відкриється вікно редактора рядків, у яке введемо назви десяти перелічених річок. Після натискання кнопки ОК відкриється вікно форми (рис. 1).

Встановимо також значення ssVertical (вертикальна смуга прокручування) для властивості

Рис. 2. Код для введення і виведення масиву з використанням компонентів TMemo і TListBox

ScrollBars об’єкта Метої. Активуємо об’єкт Editl, виберемо для нього подію onclick і введемо код, зображений на рис. 2.

Після успішної компіляції програми виконуємо її. Результат виконання зображено на рис. 3. За допомогою смуг прокручування можна переглянути всі назви річок.

Формування масиву випадковими числами і виведення їх у текстові поля TListBox і TMemo.

Приклад 2. Генеруються 12 випадкових чисел з діапазону від 0 до 6. Із цих чисел формується масив, значення елементів якого виводяться в поле об’єкта ListBoxI, а в поле об’єкта Метої виводяться всі елементи цього масиву, крім елементів, значення яких дорівнюють 6. Код, що реалізує це завдання, зображено на рис. 4. На формі розміщено об’єкти Метої, ListBoxI, Labell, Label2 і Buttonl.

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

на початку програми встановлено оператор Randomize. Без цього оператора кожного разу будуть генеруватися однакові числа.

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

Зверніть увагу на те, що в поле об’єкта Метої виведені всі елементи масиву, крім елементів зі значенням 6.

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

Рис. 4. Код створення і виведення масиву випадкових чисел

Рис. 5. Результати виведення масиву випадкових чисел

Формування масиву на основі обчислених значень і виведення їх у декілька колонок текстового поля TListBox.

Приклад 3. Створимо масив, значеннями елементів якого є висота вільного падіння тіла після кожної із дванадцяти секунд (висоту обчислюють за формулою

Для

того щоб значення елементів масиву виводилися колонками, властивості Columns об’єкта

Рис. 6. Код створення і виведення масиву значень висоти вільного падіння тіла

ListBoxI надамо значення 2. Код реалізації цього завдання наведено на рис. 6.

На формі розміщено об’єкти ListBoxI, Labell, Buttonl. їхнім властивостям надано значень, щоб зовнішній вигляд компонента був орієнтовно таким, як зображено на рис. 7.

Приклад 4. Варіант коду формування масиву Після успішної компіляції програми і її цілих чисел у процесі його оголошення і виве- виконання отримаємо результат, зображений дення в поле об’єкта Метої подано на рис. 8. на рис. 9.

Рис. 8. Код формування масиву в процесі його оголошення і виведення в поле об'єкта Метої

Рис. 9. Масив цілих чисел, виведений у поле об'єкта Метої

Уведення елементів масиву за допомогою функції InputBoxQ і виведення за допомогою функції ShowMessageO.

Приклад 5. На рис. 10 зображено код із використанням функції InputBoxO для циклічного введення елементів масиву рядкового типу і функції ShowMessageO для виведення елементів цього масиву.

У процесі введення даних із клавіатури зручно застосовувати функцію InputBoxO, яка має таку структуру: InputBox (заголовок, підказка, рядок за замовчуванням), де: заголовок — це заголовок вікна (1) (рис. 11), яке висвітлюється на формі під час виконання функції; підказка — підказка для користувача (2) (рис. 11); рядок за замовчуванням — рядок для введення значення елемента масиву (3) (рис. 11). Якщо клацнути кнопку ОК, то елементу буде присвоєно введене значення (на рис. 12 це слово

алгоритм). Якщо натиснути кнопку Cancel, то функція повертає значення рядка за замовчуванням.

Під час виконання функції InputBoxO виводиться вікно (див. рис. 11), програма призупиняє виконання, у рядок слід увести значення певного елемента масиву, клацнути кнопку ОК і ввести значення наступного елемента. Після завершення введення всіх елементів виконання програми продовжується.

Функція ShowMessageO виводить на форму вікно із заданим текстом.

У вікно, зображене на рис. 12, виведено перший елемент масиву. Після кожного клацання кнопки ОК виводиться черговий елемент до завершення виведення всіх елементів.

Рис. 10. Код уведення й виведення масиву за допомогою функцій InputBoxO і ShowMessageO відповідно

Рис. 12. Вікно функції ShowMessageO для виведення значень елементів масиву

• Уведення й виведення елементів масиву в консольних програмах.

Уведення значень елементів масиву в консольних програмах здійснюється за допомогою клавіатури. Для цього використовують оператори readln або read і оператори циклу. Спочатку вводиться значення першого елемента, потім — другого, третього і т. д. Виведення значень елементів масиву виконується за допомогою операторів write і writeln.

Приклад 6. На рис. 13 наведено код, за допомогою якого елементи одновимірного масиву (дійсні числа) вводяться за допомогою клавіатури, а потім виводяться на екран. Масив складається із 6 чисел.

Якщо з клавіатури будуть уведені числа: 12, 13.2, 3, 40.5, 5, 6.7, то на екран буде виведено результат виконання програми (рис. 14).

Рис. 13. Код уведення одновимірного масиву за допомогою клавіатури

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

Запитання для перевірки знань

Які компоненти застосовують для введення і виведення масивів?

За допомогою яких операторів уводять елементи масиву в консольних додатках?

За допомогою яких операторів виводять елементи масиву в консольних додатках?

Які функції застосовують для введення і виведення даних у масив?

Поясніть використання функції ShowMessage(). Поясніть порядок використання функції InputBox().

Як можуть формуватися масиви?

Поясніть методику використання компонента TMemo для введення даних.

Поясніть методику використання компонента TListBox для виведення даних.

Завдання для самостійного виконання

Розробіть консольну програму для введення і виведення масиву, що містить слова: змінна, масив, дані, параметри, рекурсія.

Розробіть консольну програму формування масиву 10 цілих випадкових чисел з діапазону від 0 до 100.

Розробіть код для введення і виведення за допомогою компонента TMemo масиву, що містить 5 дійсних чисел.

Розробіть код із використанням компонента TListBox для формування і виведення масиву 10 випадкових чисел з діапазону від 0 до 20.

Розробіть код із використанням функцій InputBox(), ShowMessage() і компонента TListBox для введення і виведення масиву цілих чисел.


9.4. Класичні алгоритми опрацювання числових одновимірних масивів

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

9.4.1. Знаходження суми і кількості заданих елементів масиву

Назвіть компоненти і функції, які можна використовувати для введення даних у масив і виведення даних із нього. Яким із них ви надаєте перевагу і чому? Які, на ваш погляд, операції можна виконувати над значеннями елементів масиву?

Числові масиви — це масиви, значеннями елементів яких є цілі або дійсні числа.

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

Нехай дано одновимірний масив цілих або дійсних чисел а[1], а[2], ..., а[л]. Обчислити суму значень елементів цього масиву можна методом послідовного накопичення. Сутність цього методу полягає в тому, що до початку додавання початкове значення суми вважається таким, що дорівнює нулю, тобто s=0. Потім до цього значення додається значення першого елемента масиву: s=s+a[1]. До отриманої суми додається значення другого елемента масиву: s=s+a[2] і так далі до останнього елемента (приклад 1).

Розглянемо алгоритм знаходження суми значень елементів масиву, що задовольняють певну умову.

Рис. 1. Блок-схема алгоритму обчислення суми елементів одновимірного масиву з виведенням поточних значень суми

Блок-схему алгоритму обчислення подано на рис. 1.

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

із використанням компонента TEdit зображено на рис. 2. Для об’єкта Editl обрано подію onclick.

Після успішної компіляції і виконання програми отримаємо результат, зображений рис. 3.

Рис. 2. Код обчислення суми значень елементів масиву

• Знаходження кількості елементів, що дорівнюють значенню заданого.

Нехай у масиві a[1], a[2], a[3], ..., a[n] потрібно визначити кількість елементів, значення яких дорівнюють с. Сутність алгоритму полягає у послідовному порівнянні всіх елементів масиву, починаючи з першого елемента, із заданим значенням. Якщо значення елемента масиву дорівнює заданому, то показник кількості збільшується на одиницю.

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

Як бачимо, змінній m, у якій підраховується кількість елементів, спочатку присвоюється значення нуль. Потім порівнюється значення елемента a[1] зі значенням с. Якщо їхні значення збігаються, то значення змінної m збільшується на одиницю, інакше її значення не змінюється. На наступному кроці порівнюється значення елемента a[2] зі значенням с і виконуються дії, аналогічні тим, що виконувалися на попередньому кроці. Потім порівнюється значення елемента a[3] і так далі до a[n]. Блок-схему алгоритму подано на рис. 4.

Рис. 4. Блок-схема алгоритму знаходження кількості елементів, що дорівнюють значенню заданого

Приклад 3. На рис. 5 зображено код, за допомогою якого створюється масив із 40 цілих випадкових чисел з діапазону від 0 до 6. Значення кожного елемента масиву виводиться в поле об’єкта Метої й одразу порівнюється з цифрою 4. Якщо значення елемента дорівнює 4, то значення змінної т збільшується на одиницю. Після виконання

40 циклів значення змінної т виводиться у поле об’єкта Labell. Для цього об’єкта обрано подію On Click.

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

Рис. 5. Код обчислення кількості цифр 4, що містяться у масиві

Рис. 6. Результат обчислення кількості цифр у масиві

Рис. 7. Блок-схема алгоритму

створення нового масиву

Запитання для перевірки знань

Назвіть класичні алгоритми опрацювання одновимірних масивів.

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

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

Завдання для самостійного виконання

Дано масив чисел: 71, 2, 7, 12, 4, 5, 17, 10. Розробіть програму обчислення суми чисел масиву, більших за 8.

Дано масив чисел: 66, 3, 12, 7, 9, 22, 44, 15. Розробіть програму обчислення кількості чисел, менших від 22.

На рис. 7 наведено блок-схему алгоритму створення нового масиву s із елементів заданого масиву а. Розробіть програму реалізації цього алгоритму.

9.4.2. Пошук даних у масиві

У повсякденному житті часто доводиться здійснювати пошук необхідного об'єкта серед багатьох із них. Чи можна такі процеси подати у вигляді загального алгоритму?

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

• Лінійний пошук даних.

Л інійний пошук базується на прямому переборі елементів масиву.

Нехай дано масив a[1], a[2], ..., a[n] і значення с (ключ). Потрібно визначити, чи є у цьому масиві елемент, значення якого збігається зі значенням с.

Сутність лінійного пошуку така. Спочатку с порівнюється з a[1]. Якщо вони збігаються, робиться висновок, що елемент знайдено на першій позиції масиву, і на цьому пошук завершується. Інакше с порівнюється з a[2] і робиться аналогічний висновок, потім — з a[3] і так далі до a[n].

Блок-схему алгоритму подано на рис. 1.

Рис. 1. Блок-схема алгоритму лінійного пошуку в одновимірному масиві, де і — лічильник кількості переглянутих елементів; n — загальна кількість елементів у масиві

, Приклад 1. Визначити, чи є у масиві з 10 випадкових цілих чисел з діапазону від 0 до 6 число 5. Тобто достатньо знайти номер першої позиції, на якій розміщено такий елемент. Програмний код подано на рис. 2. У програмі використано об’єкти: ListBoxI — для виведення елементів масиву, Labell — для виведення

повідомлення про наявність ключа, Label2 — для виведення повідомлення про номер позиції, на якій розташовано ключ. Якщо ключа немає, виводиться нульова позиція. Для об’єкта Labell обрано подію onclick.

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

Рис. 2. Код реалізаціїлінійного пошуку заданого значення у масиві

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

• Двійковий пошук даних.

Д війковий пошук можна застосовувати лише до впорядкованих масивів.

Нехай дано масив a[1], a[2], ..., a[n], елементи якого впорядковані за зростанням їхніх значень. Потрібно визначити, чи є в цьому масиві елемент, значення якого збігається зі значенням с.

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

Позначимо поточне значення лівої межі масиву змінною І, а значення правої межі — змінною p (початкові значення змінних: І = 1 і p = n). Спочатку в цьому масиві обирають елемент, розташований у середині масиву, — a[i]. Значення індексу середнього елемента можна визначити за формулою i=[(l+p)/2] (квадратними дужками позначена ціла частина числа). Значення середнього елемента порівнюють із ключовим значенням с. Якщо c=a[i], елемент знайдено. Якщо c < a[i], то далі для пошуку обирають частину масиву, розташовану ліворуч від a[i], у протилежному випадку — частину масиву, розташовану праворуч від a[i]. Для обраної частини процес повторюють (приклад 2).

Блок-схему алгоритму подано на рис. 4.

Приклад 2. Нехай дано масив цілих чисел: 2, 5, 8, 9, 13, 15, 20, 21 і ключове значення с = 15. У масиві міститься 8 елементів. Номер середнього елемента дорівнює 4, тому що [(1+8)/2]=4. Оскільки а[4]<15, далі пошук будемо проводити в частині масиву, що складається з елементів: 13, 15, 20, 21. У цьому масиві номером середнього елемента є число [(5+8)/2]=6. Значення шостого елемента дорівнює 15 і збігається зі значенням с. На цьому виконання алгоритму завершується.

Рис. 4. Блок-схема алгоритму двійкового пошуку в масиві

Ада Августа Лавлейс розробила перші програми для аналітичної машини Беббіджа, заклавши тим самим теоретичні основи програмування. Саме вона вперше ввела поняття циклу операції. У наші дні Ада Лавлейс по праву називають першим програмістом у світі.

Як бачимо, у блоці 3 змінній l надається початковий номер лівої межі масиву (він дорівнює 1), а змінній p — початковий номер правої межі (він дорівнює n). У блоці 4 обчислюється середній індекс розглядуваної ділянки масиву і його значення присвоюється змінній і.

У блоці 5 ключове значення c порівнюється зі значенням елемента, розташованого посередині поточної ділянки. Якщо ці значення збігаються, ключ знайдено, виводиться індекс і елемента масиву із ключовим значенням с (блок 10) і робота алгоритму завершується (блок 12). Але якщо згадані значення різні, керування передається блоку 6, де перевіряється, чи більше значення c за значення середнього елемента a[i]. Якщо c > a[i], шуканий елемент розташований праворуч від a[i] і значення правої межі не змінюється, а значенням лівої межі стає величина i+1 (блок 7). Якщо ж c < a[i], то пошук ключового значення треба вести ліворуч від a[i]. У цьому випадку значення лівої межі не змінюється, а значенням правої межі стає величина i-1 (блок 8).

Алгоритм припиняє роботу у двох випадках: коли виконується умова c=a[i] і коли значення лівої межі перевищує значення правої (блок 9). Настання другого випадку означає, що всі необхідні перевірки виконані, а ключового значення в заданому масиві не знайдено.

М етод двійкового пошуку значно швидший за метод лінійного пошуку. Проте, як уже згадувалося, двійковий пошук можна застосовувати лише до впорядкованих масивів.

Приклад 3. На рис. 5 подано код програми, що реалізує алгоритм двійкового пошуку.

Результаті виконання коду зображено на рис. 6.

Рис. 5. Код реалізації двійкового пошуку даних у масиві

Рис. 6. Результат виконання коду двійкового пошуку даних

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

Розглянемо сутність алгоритму пошуку мінімального елемента в масиві (пошук максимального елемента принципово не відрізняється від пошуку мінімального). Спочатку мінімальним вважається елемент, розташований на першій позиції. Його значення порівнюється зі значенням другого елемента. Якщо значення другого елемента менше від першого, то далі меншим вважається другий елемент. Потім значення меншого елемента порівнюється зі значенням третього елемента і так далі до останнього елемента. У результаті буде знайдено найменший елемент. Отже, алгоритм пошуку мінімального (максимального) елемента є циклічним алгоритмом (приклади 5, 6).

Приклад 5. Розглянемо покро-кове виконання алгоритму пошуку мінімального елемента в масиві 37, 15, 41, 7, 21. min:=37;

1- й цикл: 15<37? Так — min:=15

2- й цикл: 41<15? Ні

3- й цикл: 7<15? Так — min:=7

4- й цикл: 21 <7? Ні.

Результат: min=7

Приклад 6. На рис. 7 наведено код пошуку мінімального і максимального елементів у одно-вимірному масиві.

Результат виконання коду зображено на рис. 8.

Рис. 7. Код пошуку мінімального і максимального елементів масиву

Рис. 8. Результат пошуку мінімального і максимального чисел

Запитання для перевірки знань

Які існують найпростіші методи пошуку даних у масивах?

У чому полягає перевага двійкового пошуку над лінійним?

Поясніть сутність двійкового методу пошуку даних у масиві.

Накресліть блок-схеми: алгоритму лінійного пошуку даних; двійкового пошуку даних.

Завдання для самостійного виконання

Опишіть динамику процесу пошуку числа 17 у масиві: 53, 21, 7, 40, 17, 4, 35.

У довільному порядку вводяться назви 5 обласних центрів України. Розробіть алгоритм і програму визначення: чи є в цьому переліку місто Суми.

Опишіть динаміку процесу пошуку мінімального і максимального чисел у масиві: 77, 65,

7, 21, 13, 40, 88, 51, 57.

Генерується 10 цілих випадкових чисел у діапазоні від 0 до 15. Розробіть алгоритм і програму пошуку мінімального і максимального з цих чисел. Масив випадкових чисел виведіть у поле об'єкта ListBoxl. Розробіть програму визначення третьої за довжиною річки України.

9.5. Упорядкування елементів масиву

Поясніть сутність лінійного і двійкового алгоритмів пошуку даних у масиві. У чому їх переваги й недоліки? Сформулюйте сутність алгоритму пошуку максимального елемента. За якими правилами, на вашу думку, можна впорядкувати за зростанням 4 цілі числа?

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

• Упорядкування масиву методом вибору.

Нехай дано масив a[1], a[2], ..., a[n], який необхідно впорядкувати за зростанням його елементів. Сутність методу вибору така. Відшукують елемент із максимальним значенням і міняють його місцем з останнім елементом масиву. Після цього останній елемент із подальшого розгляду виключають, а для перших (n-1) елементів процедуру повторюють. Тобто аналізується масив a[1], a[2], ..., a[n-1], у якому також відшукують максимальний елемент. Цей елемент міняють місцями з елементом a[n-1]. Подібні дії виконують у масиві a[1], a[2], ..., a[n-2], потім — у масиві a[1], a[2], ..., a[n-3] тощо. Отже, на кожному циклі алгоритму значення правої межі масиву зменшується на одиницю. Цей індекс будемо зберігати у змінній р. У табл. 1 наведено динаміку процесу впорядкування масиву 15, 12, 17, 8, 14, 6.

Загальне значення слова «сортування» — це розподіл елементів на групи за деякою ознакою, наприклад розподіл яблук по сортах за їх якістю, листів — за поштовими індексами, банок із фарбами — за кольором тощо. Проте у програмуванні під сортуванням розуміють упорядкування елементів (за деякою характеристикою), наприклад шикування учнів за зростом на уроці фізкультури, розташуван-н я слів у словнику в алфавітному порядку, упорядкування точок площини за зростанням координати х тощо.

Таблиця 1. УПОРЯДКУВАННЯ МАСИВУ МЕТОДОМ ВИБОРУ

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

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

Блок-схему алгоритму подано на рис. 2.

Рис. 2. Блок-схема алгоритму впорядкування масиву методом вибору

Початкове значення правої межі масиву (значення змінної р) дорівнює значенню змінної n. Змінна m містить індекс поточного елемента з максимальним значенням, а змінна і містить індекс елемента, що переглядається у даний момент. Оскільки перший елемент завжди спочатку вважається найбільшим, то у блоці 4 змінна m набуває значення 1, а змінна і — значення 2.

У блоці 5 перевіряється: чи більше значення поточного елемента a[i] за значення поточного найбільшого елемента a[m]. Якщо a[i]>a[m], то індекс поточного максимального елемента у блоці 6 набуває нового значення. Індекс поточного елемента масиву збільшується на одиницю у блоці 7. Якщо цей індекс менший або дорівнює правій межі (блок 8), то пошук максимального елемента триває далі. Якщо ж i > p, то це означає, що всю невпорядковану ділянку масиву переглянуто і в блоці 9 елемент із максимальним значенням міняють місцями з останнім. У блоці 10 значення правої межі ділянки, що переглядається, зменшується на одиницю. Ознакою завершення процесу виконання алгоритму є той факт, що індекс правої межі дорівнює одиниці (блок 11).

Метод сортування вибором є

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

Приклад 1. Програмний код реалізації алгоритму впорядкування масиву методом вибору подано на рис. 3. У цьому коді масив

формується із 10 випадкових чисел у діапазоні від 0 до ЗО. На рис. 4 зображено один із можливих результатів виконання програмного коду.

Рис. 3. Програмний код упорядкування масиву методом вибору

• Упорядкування масиву методом обміну.

Сутність упорядкування масиву за зростанням значень його елементів методом обміну така. Масив a[1], a[2], ..., a[n] переглядається зліва направо. Спочатку порівнюються елементи a[1] і a[2], потім — a[2] і a[3], a[3] і a[4], a[4] і a[5] і так далі до елементів a[n-1] і a[n]. Кожного разу, коли попередній елемент більший за наступний, значення елементів міняються місцями. Зрозуміло, що після повного завершення першого перегляду всього масиву на останній позиції буде міститися елемент із максимальним значенням. Після цього елемент a[n] з подальшого розгляду виключається, переглядається масив a[1], a[2], ..., a[n-1] і з його елементами виконуються аналогічні дії, в результаті чого на позицію n - 1 буде переміщено другий за величиною елемент.

Процедура повторюється для масиву a[1], a[2], ..., a[n - 2], потім — для масиву a[1], a[2], ..., a[n - 3] і т. д. З описаного випливає, що сортування масиву завершується після повного впорядкування всіх елементів масиву. Ознакою того, що масив упорядкований, є те, що після завершення його перегляду жодної перестановки елементів не було.

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

У 1959 році Дональд Шелл запропонував удосконалення алгоритму прямих вставок. Його ідея — порівнювати елементи, розташовані на певній відстані один від одного, і покроково зменшувати цю відстань.

Приклад 2. Дано масив 41, 52, 58, 70, 66, який потрібно впорядкувати за зростанням значень елементів. У цьому масиві 3 перші елементи впорядковано. Для того щоб масив

був повністю впорядкований, потрібно поміняти місцями четвертий і п’ятий елементи. Для цього виконуються дії, наведені у табл. 2.

Таблиця 2. ПРОЦЕС УПОРЯДКУВАННЯ МАСИВУ

Коментар: під час першого виконання зовнішнього циклу відбулась перестановка елементів маси- І ву, після його завершення змінна у набула значення false. Тому починається другий зовнішній цикл, І а змінна у набуває значення true

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

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

Із табл. 2 видно, що після першого зовнішнього циклу масив є впорядкованим. Але змінна у має значення false, тому виконується другий зовнішній цикл. Після його завершення жодної перестановки елементів не було, тому процес упорядкування завершується. Звернемо особливу увагу на те, що на початку будь-якого зовнішнього циклу ця змінна набуває значення true. Після того як у внутрішньому циклі відбувається хоча б одна перестановка елементів, змінна у набуває значення false і до кінця цього циклу не змінюється.

На основі аналізу процесу впорядкування наведеного вище масиву розробимо алгоритм упорядкування методом обміну. В алгоритмі використано такі позначення: p — індекс правої межі поточної ділянки масиву; у — ознака наявності перестановки: на початку кожного зовнішнього циклу вона набуває значення true. Якщо після завершення зовнішнього циклу змінна у має значення true, це означає, що перестановок під час останнього перегляду не було, якщо y=false, то відбулася принаймні одна перестановка; і — індекс поточного елемента масиву; z — змінна, призначена для тимчасового зберігання значення елемента масиву під час перестановки елементів.

Приклад 3. Програму, що реалізує алгоритм сортування методом обміну, подано на рис. 5. У цьому коді масив формується з десяти

випадкових чисел з діапазону від 0 до 50. На рис. 6 зображено один із можливих результатів виконання програмного коду.

Рис. 5. Програмний код упорядкування масиву методом обміну

• Упорядкування масиву методом вставки.

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

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

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

Запитання для перевірки знань

Які переваги й недоліки мають методи впорядкування масиву вибором і обміном?

Як здійснюється перестановка двох елементів масиву?

Який вигляд матиме масив 21, 40, 5, 13, 18 після завершення першого зовнішнього циклу впорядкування масиву методом вибору?

Розробіть програму впорядкування назв районів свого міста (області) за алфавітом. Поясніть сутність алгоритму впорядкування масиву методом вибору.

Поясніть сутність алгоритму впорядкування масиву методом обміну.

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

Завдання для самостійного виконання

Відомі прізвища і зріст 8 учнів вашого класу.

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

Знайдіть в Інтернеті назви 7 найбільших за площею областей України. Розробіть алгоритм

і програму впорядкування назв областей у порядку зменшення їхніх площ. Використайте метод вибору.

Опишіть у вигляді таблиці впорядкування масиву чисел 33, 60, 7, 12, 80, 41 у порядку їх зменшення. Використайте метод вибору; метод вставки.

Варіант

Завдання

Початкові дані

1

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

N = 6

4.7; 3.8; 3.3; 3.6; 3.1; 3.9; c = 3.5

2

Відомі результати змагань чемпіонату світу з жіночого біатлону. Розробіть алгоритм і програму визначення того, чи входить команда України у 6 кращих команд і, якщо є, яке місце вона посідає.

Норвегія, Німеччина, Україна, Росія, Франція, Швеція

Хід роботи

Під час роботи з комп’ютером дотримуйтесь правил безпеки.

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

Проаналізуйте умову задачі, побудуйте інформаційну модель.

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

Перевірте роботу програми із різними початковими даними.

Виконайте програму із зазначеними в таблиці початковими даними. Проаналізуйте отриманий результат.

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

Практична робота № 18

Тема. Класичні алгоритми для роботи з масивами та їх реалізація у вигляді програм. Завдання: розробити алгоритм і програму для реалізації одного із завдань, наведених у таблиці.

Обладнання: комп'ютер із встановленою програмою — середовищем програмування. Таблиця. ЗАВДАННЯ ДЛЯ ВИКОНАННЯ ПРАКТИЧНОЇ РОБОТИ № 18

Варіант

Завдання

Початкові дані

1

Дано масив з N цілих додатних чисел. Розробіть алгоритм і програму визначення, наскільки максимальне число більше за мінімальне.

N = 7;

105, 34, 160, 31, 28, 60, 70

2

Знайдіть в Інтернеті прізвища космонавтів України. Розробіть алгоритм і програму впорядкування їхніх прізвищ в алфавітному порядку.

 

Хід роботи

Під час роботи з комп’ютером дотримуйтесь правил безпеки.

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

Проаналізуйте умову задачі, побудуйте інформаційну модель.

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

Перевірте роботу програми із різними початковими даними, дібраними самостійно.

Виконайте програму із зазначеними в таблиці початковими даними. Проаналізуйте отриманий результат.

Зробіть висновок: які методи сортування і пошуку доцільно використовувати в цій роботі.

 

Це матеріал з підручника Інформатика 9 клас Руденко (поглиблений рівень)

 






^