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

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

Алгоритми, що розгалуджуються, залежно від виконання або невиконання в них деяких умов здійснюють ту або іншу послідовність обчислень. При розгалуженні відбувається одноразовий прохід по одній з гілок рішення задачі. Класичний приклад алгоритму, що розгалуджується - це алгоритм рішення квадратного рівняння ах2+вх+з=0 при будь-кому а, в, с. На додаток до попередніх блоків алгоритми, що розгалуджуються, містять блок "рішення" (умова). В даному прикладі A, B, C, D, x, x1, x2 - змінні.

Спочатку перевіряють можливість А=0, тоді рівняння ах2+вх+с=0 зводиться до виду вх+ с =0, звідки . Потім обчислюють дискримінант D, якщо він негативний, рівняння коренів не має, якщо позитивний, будуть два корені, якщо рівний 0, обидва корені будуть однакові. Алгоритм представлений на рис.1.2.

Рис.1.2

Розгалуження можуть бути повні і неповні:

Циклічні алгоритми мають частину обчислень, які виконуються неодноразово. У загальному вигляді цикли містять три види дій:

1) підготовчі до циклу;

2) дії, які повторюватимуться (їх називають тіло циклу);

3) умови виходу з циклу.

Згідно з новим Гостом цикл можна зображувати і так:

Циклічні алгоритми бувають декількох видів:

- цикли з лічильником застосовуються, коли заздалегідь відомо, скільки разів повторюватиметься послідовність дій;

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

1) Знайти суму N доданків, тобто вичислити .

Рішення: Ведемо S=Ш, тоді S₁=S+a₁;

S₂=S₁+a₂;

·

·

S_i=S_i–1+a_i;

·

·

S_n=S_n-1+a_n,

значенню суми на i -му кроці привласнюється значення суми на попередньому кроці плюс доданок чергового кроку аi:

Рис.1.3(а) Рис.1.3(б)

На рис.1.3(а) приклад циклу з лічильником. Тут заздалегідь відома кількість повторень N разів. Блоки 5-8 можна було б оформити і так (рис.1.3(б)):

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

Розглянемо алгоритм виділення розрядів з числа 1579, тобто вимагається послідовно отримати 9, 7, 5, 1.

Очевидно, 9 вийде, якщо 1579 розділити на 10 і виділити залишок; 7 вийде, якщо цілу частку попереднього кроку (157) розділити на 10 і виділити залишок; 5 вийде, якщо цілу частку попереднього кроку (15) розділити на 10 і виділити залишок; і, нарешті, 1 вийде, якщо цілу частку попереднього кроку (1) розділити на 10 і виділити залишок.

Коли ж вимагається закінчити обчислення? При останньому обчисленні в частку запишеться 0. Це і можна вважати ознакою закінчення рахунку.

Словесний опис рішення вимагається формалізувати. Позначимо у - черговий розряд, N - проміжна частка. Фрази "залишок", "ціле" замінюватимуть функції отримання відповідно залишку і цілої частини.

У = залишок (N/10).

N = ціле (N/10).

тут = не знак рівності, а знак привласнення.

Тепер розглянемо задачу, яка використовує вище розглянений алгоритм.

Вимагається перевірити кратність 5 сум цифр будь-якого числа Х. Алгоритм представлений на рис.1.4.

Рис.1.4

Поиск по сайту: