Сортування трьох чисел

Раніше Ви познайомилися з основними засобами мови програмування Visual Basic, що застосовуються для реалізації на комп'ютері нелінійних алгоритмів, тобто таких алгоритмів, що містять розгалуження і повторення. Нагадаємо, що до цих засобів відносяться оператори безумовного й умовного переходів GoTo і If... Then... Else, а також оператори циклу For... Next і Do... Loop. Особливо допитливі з Вас могли познайомитися і з оператором вибору альтернативи Select Case.

Цими засобами (операторами умовного переходу і циклу) ми часто користувалися при рішенні задач двох попередніх глав. Але у всіх цих задачах нам не доводилося зіштовхуватися з перевіркою складних умов — умовні вирази в зазначених операторах були дуже простими.

Зараз ми розглянемо питання про те, як програмувати складні (з погляду логіки) умови виконання тієї чи іншої дії. Іншими словами, ми розглянемо складні умовні алгоритми. У чому полягає їхня складність?

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

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

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

Приклад 3.1. Нехай у нас 3 яблука і ваги без гир з важелем, за допомогою яких можна порівнювати вагу двох яблук.

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

Нехай a, b, с — змінні, значення яких — вага кожного яблука. І нехай Max, Mid і Min — це змінні, значеннями яких повинні стати вага найбільшого, середнього і найменшого яблука.

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

Розглянемо перестановки (Перестановкою чисел al,..., an називається довільна послідовність, складена з цих чисел: (N1,..., Nn). Число перестановок чисел — це добуток усіх натуральних чисел від 1 до п. Такий добуток у математиці називається факторіалом числа п. Докладніше про факторіал числа як про функцію цього числа буде йти мова розд. 3.2.) трьох чисел: (а, b, с), (а, с, b), (b, а, с), (b, с, а), (с, a, b), (с, b, а). По черзі будемо брати кожну з них і перевіряти, чи не справджуються для неї дві нерівності: N1 > = N2 > = N3. Як тільки ці дві нерівності будуть виконані, алгоритм завершить свою роботу і ми одержимо результат: Max = N1, Mid = N2, Min = N3.

Цей алгоритм записується за допомогою наступного коду:

Код 3.1

У цій програмі використовуються багаторазово вкладені один в одного (на зразок російських матрьошок) умовні оператори If... Then... Else... End If. Зверніть увагу на те, що 2 самі внутрішні перевірки (с >= b And b >= а) є зайвими. Адже якщо всі попередні умови не виконуються, то дана умова буде виконана автоматично. З цієї причини 2 рядки програмного коду без усякого збитку можна просто видалити з програми. Для зручності читання таких програм використовується запис драбинкою — внутрішні умовні оператори записуються трохи правіше зовнішніх, як Ви бачите в коді 3.1.

Використовуючи ключове слово ElseIf (У мові Visual Basic можна трішки скоротити запис програми, що містить вкладені перевірки. Для цього використовується ключове слово ElseIf. З його допомогою можна об'єднати два рядки, що починаються зі слів Else і If, в один, а також забрати один рядок End If.), можна трохи скоротити програму (код 3.2).

Код 3.2

Оцінимо число порівнянь, які необхідно виконати для того, щоб знайти максимальне і мінімальне значення з трьох. Очевидно, що в кращому випадку потрібно перевірити 2 нерівності, а в гіршому випадку — 10 нерівностей!

Чи можна вважати розглянуту програму задовільною? Очевидно, що ні. Хоча використаний у ній декларативний алгоритм простий і зрозумілий, його робота малоефективна: занадто багато перевірок потрібно зробити для того, щоб порівняти між собою всього три числа! А для п'яти чисел знадобилося б уже k= 476 перевірок: k = 4 *(1* 2 * 3 * 4 * 5- 1).

Процедурний алгоритм розв'язання цієї задачі виглядає логічнішим.

Знову звернемося до обрахування яблук. Варто зробити так: спочатку порівняти два яблука. Важче (перше) відкласти, а легше (друге) порівняти з третім. Якщо третє виявиться легше від другого, то третє — найлегше, а перше — найважче. Якщо друге легше третього, то найлегше — друге. А для обрахування найважчого яблука треба зробити ще одне порівняння — першого з третім. У кращому випадку нам буде потрібно два порівняння, а в гіршому — всього три! Код 3.3 демонструє даний алгоритм.

Код 3.3

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

Код 3.4

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

Але зовсім відмовлятися від декларативного стилю програмування ми Вам не радимо. Його врятує ідея рекурсії, про яку ми поговоримо у наступному розділі.

Hові поняття:

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

Питання для роздумів

1. Яке найменше і найбільше число порівнянь буде виконано декларативною програмою сортування чотирьох чисел (аналогічній програмі коду 3.1 чи 3.2)? А декларативною програмою сортування восьми чисел? (Відповідь: 3 і 69 порівнянь для 4 чисел; 7 і 261233 порівнянь для 8 чисел.)
2. Яке число порівнянь буде виконано процедурною програмою сортування чотирьох чисел (аналогічній програмі коду 3.3 чи 3.4)? А сортування восьми чисел? (Відповідь: 4 порівняння для 4 чисел і 10 порівнянь для 8 чисел.)

Вправи