Повторення

Приклад

Aлгоритм

Повторення

Розгалуження

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

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

Дві стрілки, які відгалужуються від ромба, позначені словами «Так» і «Ні». Якщо записане всередині ромба умовне твердження є істинним, виконуються дії, на які вказує стрілка, позначена словом «Так». Якщо це твердження є хибним, виконуються дії, на які вказує стрілка, позначена словом «Ні».

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

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

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

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

Найбільший спільний дільник чисел а і b позначимо через НСД(а, b), а остачу від ділення а на b - через a mod b.

Алгоритм Евкліда ґрунтується на тому факті, що НСД(а, b) = НСД(b, a mod b), якщо b≠ 0, і НСД (а, b) = а, якщо b = 0.

НСД(12, 5) = НСД(5, 12 mod 5) = НСД(5, 2)=НСД(2, 5 mod 2) = НСД(2, 1) = = НСД(1, 2 mod 1) = НСД(1, 0) = 1

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

1. Прочитати значення а та b.

2. Поки , виконувати дії, описані у пунктах 3-5.

3. Обчислити величину с = a mod b.

4. Значення а замінити значенням b.

5. Значення b замінити значенням с

6. Написати значення а.

Структура повторення реалізується кроками 2-5. Виконання описаних на кроках 3-5 дій повторюватиметься доти, доки істинним є твердження . Істинність цього твердження перевіряється на кроці 2. Така перевірка здійснюється кожного разу перед тим, як виконуються кроки 3-5. Коли твердження стане хибним, кроки 3-5 будуть пропущені і після кроку 2 буде виконано одразу крок 6.

Алгоритм Евкліда

Тема: Структурне програмування.

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

Лінійна структура

Операції виконуються послідовно зверху донизу.

Лінійний алгоритм

Алгоритм, що вміщує тільки лінійні структури, називається лінійним алгоритмом. Це прості обчислювальні алгоритми.

Умовна структура (основна конструкція )

Виконання чи не виконання дії по умові.

Розгалуження здійснюється на дві гілки.

Умовна структура неосновний варіант

Виконання чи не виконання дії по умові.