НОУ ІНТУЇТ | лекція | Блок-схеми. Графічна реалізація алгоритмів

Заняття 4. Графічна реалізація циклічного алгоритму

У розгляді циклічного алгоритму слід виділити кілька понять.

Тіло циклу - це набір інструкцій, призначений для багаторазового виконання.

Ітерація - це одиничне виконання тіла циклу.

Мінлива циклу - це величина, що змінюється на кожній ітерації циклу.

Кожен цикл повинен містити наступні необхідні елементи:

1. початкове завдання змінної циклу,
2. перевірку умови,
3. виконання тіла циклу,
4. зміна змінної циклу.

Цикли бувають двох видів - з передумовою і з умовою поста. У циклі з передумовою спочатку перевіряється умова входу в цикл, а потім виконується тіло циклу, якщо умова вірна. Цикл з передумовою представлений на Мал. 2.9 . Цикл з передумовою також може бути заданий за допомогою лічильника. Це зручно в тих випадках, коли точно відомо кількість ітерацій. У загальному вигляді блок-схема, яка реалізує цикл з передумовою, представлена ​​нижче. Спочатку задається початкове значення змінної циклу, потім умова входу в цикл, тіло циклу і зміна змінної циклу. Вихід з циклу здійснюється в момент перевірки умови входу в цикл, коли воно не виконується, тобто умова помилкова. Цикл з передумовою може ні разу не виконатися, якщо при першій перевірці умови входу в цикл воно виявляється хибним.

Мал.2.9.

Циклічний алгоритм з передумовою в загальному вигляді

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

Мал.2.10.

Циклічний алгоритм з умовою поста в загальному вигляді

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

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

Наведемо найпростіші приклади, відповідні циклічного алгоритму.

Приклад 7. Вася дзвонить Петі, але у Петі може бути зайнята лінія. Скласти блок-схему дій Васі в цьому випадку.

Рішення. Коли телефонна лінія зайнята, то необхідно знову і знову набирати номер, поки Петя не закінчить попередню розмову, і телефонна лінія не виявиться знову вільною. Блок-схема представлена ​​на Мал. 2.11 .

Мал.2.11.

Блок-схема для прикладу 7

Тут тіло циклу складається з однієї дії "Набрати номер Петі", тому що саме ця дія слід повторювати, поки лінія буде зайнята. Під итерацией циклу розуміється чергова спроба додзвонитися до Петі. Як такої змінної циклу тут немає, тому що ситуація взята з життя. Вихід з циклу відбувається в той момент, коли умова "У Петі зайнято" стало невірним, тобто телефонна лінія вільна - дійсно, немає необхідності більше набирати номер Петі. В даному прикладі застосований цикл з умовою поста, тому що спочатку необхідно набрати номер Петі, адже інакше ми не можемо відповісти на питання - чи зайнята лінія у Петі.

Приклад 8. Учневі потрібно купити підручник. Скласти блок-схему, що описує дії учня в разі, якщо підручника немає в ряді магазинів.

Рішення. Дії учня в даному прикладі очевидні: коли він приходить в перший і будь-який інший магазини, то можливі два варіанти - підручник є в наявності або підручника немає в продажу. Якщо підручника немає в продажу, то учневі слід піти в інший книжковий магазин і запитати даний підручник, і т.д. поки підручник не буде куплений, тому що перед учнем стоїть кінцева мета - купити підручник. Ми будемо використовувати цикл з передумовою, тому що спочатку потрібно знайти магазин, який має в наявності даний підручник. Цикл буде виконуватися, поки умова "В даному магазині немає підручника" буде вірним, а вихід з циклу здійсниться, коли умова стане хибним, тобто коли учень прийде в магазин, в якому є даний підручник. Дійсно, в цьому випадку учень купить потрібний йому підручник і не буде більше шукати книжкові магазини. Результат блок-схеми представлений на Мал. 2.12 .

Мал.2.12.

Блок-схема для прикладу 8

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

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

Приклад 9. Дано числа . Відомо, що число змінюється від -10 до 10 з кроком 5, і не змінюється. обчислити суму і різниця чисел і для всіх значень і .

Рішення. На відміну від прикладів 3 і 6 тут число змінюється від -10 до 10 з кроком 5. Це означає, що число є змінною циклу. спочатку одно -10 - це початкове завдання змінної циклу. далі буде змінюватися з кроком 5, і т.д. поки не буде досягнуто значення 10 - це відповідає зміні змінної циклу. Ітерації треба повторювати, поки виконується умова " ". Отже, буде набувати наступних значень: -10, -5, 0, 5, 10. Число нічого очікувати бути змінної циклу, тому що і не змінюється за умовою задачі. Результат блок-схеми (з передумовою) представлений на Мал. 2.13 .

Мал.2.13.

Блок-схема для прикладу 9 (з передумовою)

Тіло циклу складається з декількох дій: обчислення суми, обчислення різниці і висновок отриманих даних на екран. Таким чином, у нас вийде кілька значень сум і різниць, тому що змінюється. Кількість сум і кількість різниць співпаде з кількістю різних значень , Тобто п'ять.

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

Наведемо блок-схему, яка використовує цикл з умовою поста, на Мал. 2.14 .

Мал.2.14.

Блок-схема для прикладу 9 (з умовою поста)

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

Мал.2.15.

Блок-схема з розгалуженням для прикладу 9: а) з передумовою, б) з умовою поста