Приклад алгоритму із розгалудженням

Постановка задачі: знайти найменше з трьох заданих чисел a, b і c.

Вхідними даними є числа a, b і c, вихідними - найменше число з них.

Розв'язання:

На цій нескладній задачі проілюструємо відзнаку між механізмами розв'язання, використовуваними людиною та ЕОМ. Уявимо ситуацію, коли всі три числа записані на аркуші паперу і показані людині. Мозок людини є паралельною обчислювальною системою з величезною кількістю "процесорів", тому для нього не буде складно миттєво зафіксувати у зоровій пам'яті всі три числа, оцінити їх співвідношення і через долю секунди визначити найменше або найбільше число. Із значним спрощенням можна сказати, що алгоритм, за яким працює мозок при розв'язанні даної задачі, полягає в перевірці умови

((a < b) і (a < c)) або ((b < a) і (b < c)) або ((c < a) і (c < b)), (2.13)

причому всі складові цієї умови обробляються немов би водночас. Зрозуміло, що на відміну від людини, ЕОМ в кожен момент часу може оперувати із суворо обмеженою кількістю даних, тому подібний алгоритм для ЕОМ є непридатним. В той же час, якщо кількість чисел, серед яких треба знайти найменше, збільшити до ста або, навіть, тисячі, то виконавець-людина втратить спроможність «охопити» їх разом і також буде вимушений виконувати обробку послідовно, застосовуючи алгоритм «машинного» виду.

Наведений приклад показує, що алгоритм, розрахований на виконання послідовною ЕОМ, повинен орієнтуватись на послідовну обробку даних, здійснення руху до розв’язку крок за кроком.

Алгоритм розв’язання задачі в текстовому вигляді побудуємо наступним

чином:

- ввести a, b, c;

- якщо a < b:

· якщо a < c вивести a; o інакше вивести c;

- інакше:

· якщо b < c вивести b; o інакше вивести c.

- завершення алгоритму.

Після закінчення «першого раунду» – перевірки умови a < b – стає відомо, яке з цих двох чисел «претендує» називатись найменшим. Якщо таким є число a, то залишається порівняти його з числом c для здійснення кінцевого висновку. Аналогічне порівняння необхідно виконати, якщо меншим виявилось число b. Випадок, коли будь-яка пара чисел співпадає в даному алгоритмі не розглядається.

Зауважимо, що попарне порівняння чисел можна здійснювати у довільному порядку, наприклад, спочатку порівняти b і c, а потім, за результатами цього порівняння – b і a або c і a.

Схема алгоритму представлена на наступному рис. 2.10.

Рис. 2.10 – Схема алгоритму розв’язання задачі про найменше з трьох чисел

Дата добавления: 2014-11-08