4. Моделювання предметних областей за допомогою масивів.

Задача 3. Змоделювати предметну область про студентів трьома текстовими масивами: масивом імен чи прізвищ А, масивом В з оцінками відповідних осіб і масивом С з адресами цих осіб. Упоря­дкувати масив А за алфавітом, переставляючи одночасно елементи в масивах В і С.

Розв’язування. Занесемо в масив А такі імена:

Наталка, Тарас, Юля, Роман, Галя, Андрій.

Задача зводиться до впорядкування елементів масиву А з дани­ми типу String за зростанням. Тут «більшим» є текст, який почина­ється з букви, що в алфавіті міститься дальше. Код буде той же, що і вище, але перші п’ять команд треба замінити на такі:

' Програма упорядкування масиву імен

Dim А(6) As String

Dim с As String

Dim і, j, n

A(1) = "Наташа": A(2) = "Тарас": A(3) = "Роман"

A(4) = "Галя": A(5) = "Юля": A(6) = "Андрій"

Після виконання програми отримаємо список імен за алфавітом:

Андрій Галя Наталка Роман Тарас Юля.

Масиви В і С називають асоційованими до масиву А, оскільки вони містять додаткові відомості про осіб, імена яких занесені в ма­сив А. Тому, щоб оцінки й адреси завжди асоціювалися (узгоджува­лися) із заданою особою, потрібно, міняючи місцями елементи в ма­сиві А, міняти так само місцями елементи в масивах В і С.

Завдання 1. Для масиву А створіть два асоційовані масиви В і С з будь-якими значеннями, що логічно відповідають змісту задачі. Доповніть код командами переставляння місцями значень у маси­вах В і С (команди такі ж, як і для масиву А). Виконайте код і пе­реконайтеся, що під час упорядкування імен правильно перестав­ляються значення в асоційованих масивах.

Завдання 2. Знайшовши спочатку в масиві А особу з іменем Галя і з’ясувавши її номер, виведіть на екран її оцінку та адресу.

5*. Пошук даних в упорядкованому масиві. Метод бісекції. Не­хай в масиві А є імена осіб, а асоційовані масиви В і С містять оцін­ки й адреси цих осіб.

Задача 4. Визначити оцінку й адресу конкретної особи, напри­клад, Галі.

Розв’язування. Нехай в масиві А є такі імена: Наталка, Ростик, Тарас, Роман, Галя, Андрій, Юля. Позначимо номер шуканого еле­мента в масиві А через г. Вважатимемо, що нумерація елементів по­чинається від одиниці. Оскільки ім’я Галя є п’ятим у масиві імен, то 2 = 5. Відповідь — значення В(5) і С(5).

Однак насправді формальний виконавець імен не бачить, тому він спочатку розглядає (вибирає) перший елемент масиву А і порів­нює його з еталоном, тобто перевіряє, чи А(1) = "Галя". Якщо А(1) = "Галя", то 2 = 1, і виконавець пошук закінчує, якщо ні, то він розглядає другий елемент масиву. Якщо А(2) = "Галя", то z = 2 і т.д. У нашому випадку вибирань і порівнянь буде 5, поки буде ви­значено, що 2 = 5. Відповідь: В(z) і С(z).

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

Для ефективного розв’язування задачі пошуку потрібного даного застосовують метод бісекції — послідовного ділення впорядкованого ма­сиву навпіл. Обчислювальна складність цього алгоритму — 0(log₂n).

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

Далі розглядатимемо задачу за умови, що масив А вже є впоря­дкований за зростанням і два асоційовані масиви змінені.

Упорядкований масив А містить п — 7 елементів (формальний виконавець їх не бачить):

Андрій Галя Наталка Роман Ростик Тарас Юля.

Алгоритм методу бісекції такий:

1. Вибрати середній елемент: А(4). Тут А(4) = "Роман".

2. Якщо А(4) = "Галя", то відповідь k = 4 і стоп (але це не так).

3. Якщо А(4) < "Галя", то далі шукати в правій частині масиву:

5 6 7

Ростик Тарас Юля,

4. Якщо А(4) > "Галя”, то далі шукати у лівій частині масиву:

1 2 3

Андрій Галя Наталка.

5. Вибрати середній елемент А(2).

6. Якщо А(2) = "Галя" (а це так), то відповідь k = 2 і стоп, інак­ше — пошук продовжити праворуч чи ліворуч.

Як бачимо, елемент "Галя" був знайдений за дві операції виби­рання елементів масиву А, а не за п’ять, як раніше.

Виконаємо формальний опис алгоритму бісекції. Нехай у змін­них n1 і n2 містяться номери першого й останнього елементів, тобто спочатку n1=1 і n2=n. Нехай змінна z міститиме шуканий номер. Спочатку покладемо z = 0. Розглянемо алгоритм.

1. m = (n1 + n2) \ 2 - це номер середнього елемента А(m).

2. Якщо А(m) = "Галя", то z = т і перейти до п. 6.

3. Якщо n1 = n2, то перейти до п. 6.

4. Якщо А(m) < "Галя", то n1 = m + 1 і перейти до п.1.

5. Якщо А(m) > "Галя", то n2 = m - 1 і перейти до п.1.

6. Вивести z.

Відповідь на поставлене в умові задачі 4 запитання дає команда <вивести B(z), C(z)>.

Третій пункт алгоритму дає змогу з’ясувати, чи є в масиві шу­каний елемент. Результатом роботи алгоритму буде або номер шука­ного елемента, або число 0, якщо такого елемента в масиві немає.

Завдання 1. Перевірте правильність алгоритму, застосувавши його для масиву з двох елементів ("Іра", ”Оля”), намагаючись від­шукати в ньому ім’я: а) Оля, б) Леся.

Завдання 2. Складіть код розв’язування задачі 4 самостійно.

Завдання 3. Покращіть алгоритм, щоб у ньому була менша кількість команд розгалуження.

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

Вправи

1. Упорядкуйте усно за зростанням таку послідовність чисел: 5, -7, 4, 6, 0, -2.

2. Упорядкуйте усно наведену вище послідовність чисел за спаданням.

3. Упорядкуйте в алфавітному (лексикографічному) порядку (за зрос­танням) такі імена: Іра, Оля, Леся, Галя, Люба.

4. Розв’яжіть задачу № 12 свого варіанта з розділу «Задачі».

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

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

7*. Складіть програму для методу бісекції.