13:29 § 11. Алгоритми підвищеної складності | |
§ 11. Алгоритми підвищеної складностіВище розглядалися найпростіші структури алгоритмів з повторенням і з розгалуженням. На практиці застосовуються більш складні структури цих типів алгоритмів. Нижче описані циклічні алгоритми з розгалуженням і алгоритми з вкладеними циклами,Циклічні алгоритми з розгалуженням У попередніх розділах розглядалися алгоритми з фіксованою, заздалегідь відомою кількістю циклів. Наприклад, алгоритм отримання таблиці множення на 3 містить 10 циклів. На практиці часто використовуються алгоритми, у яких кількість циклів заздалегідь невідома. Вона залежить від поточної ситуації, що склалася у процесі виконання алгоритму. Наприклад, невідомо, скільки разів потрібно кинути кубик з цифрами від 1 до 6, щоб отримати суму чисел більше 45. Невідомо також, скільки разів необхідно виконати віднімання від більшого числа меншого, щоб різниця чисел стала меншою меншого числа. Наприклад, якщо задані числа 34 і 9, то процес зменшення буде відбуватися так: 1-й цикл: 34 - 9 = 25; 2-й цикл: 25 - 9 = 16; 3-й цикл: 16 - 9 = 7, кінець. Циклічні алгоритми із заздалегідь невідомою кількістю циклів поділяються на два види: з передумовою і з післяумовою. Цикли з передумовою У алгоритмах з передумовою спочатку перевіряється певна умова. Доти, доки вона має істинне значення, цикл виконується. Як тільки умова отримає значення хибне, виконання циклу закінчується. На рисунку 3.76 подано схему, що пояснює сутність циклічного алгоритму з передумовою. З рисунка видно, що операції тіла циклу можуть взагалі бути не виконані жодного разу, якщо результат перевірки умови мае значення хибне. Для створення ефекту анімації об'єкта Ьоз'4-walking-b імпортуємо його образи b і с. Програма, що моделює його переміщення, подана на рисунку 3.78. Після запуску програми об'єкт починає рухатися, як тільки буде натиснута кнопка миші. Рух об'єкта припиняється, якщо кнопку миші відпустити. Отже, команди тіла циклу виконуються лише за умови натиснення кнопки миші. У циклічних алгоритмах з післяумовою спочатку виконуються оператори тіла циклу, а потім перевіряється умова. Якщо умова має значення хибне, оператори тіла циклу виконуються ще раз, інакше їх виконання припиняється. У таких алгоритмах тіло циклу виконується принаймні один раз. Сутність алгоритмів з післяумовою пояснюється графічної схемою, поданою на рисунку 3.79. Приклад. У розкладі потягів по станції Київ підрахувати кількість потягів, що прямують до м. Львів. Позначимо Розклад - загальний список потягів по станції Київ (що містить: Рівне, Харків, Львів, Миколаїв, Львів, Херсон, Львів), а - поточний номер рядка у розкладі потягів, р - зміст поточного рядка розкладу, с - кількість потягів до Львова. Програму подано на рисунку 3.81. Алгоритми з вкладеними циклами - це такі алгоритми, в яких інструкції одного циклу містяться є інструкціях іншого циклу. Розглянемо сутність алгоритмів цього типу на прикладі. Записано три рядки чисел, у кожному з яких знаходиться по п'ять чисел: Необхідно знайти загальну їх суму. Алгоритми знаходження суми чисел можуть бути різними. Найчастіше застосовується метод "послідовного накопичення" суми. Його сутність полягає в тому, що береться число першого рядка першого стовпця, до нього додасться число другого стовпця цього ж рядка. До отриманої суми додасться число третього стовпця, потім четвертого і п'ятого. Далі у такій же послідовності до отриманої суми додаються числа другого, потім третього рядків. Для поданого прикладу цей процес можна записати так: 1+3=4; 4+5=9; 9+7=16; 16+9=25; 25+4=29; 29+6=35 і т. д. Позначимо поточне значення суми змінної s; поточне значення числа, що додається - змінною a; b - значення числа першого стовпця поточного рядка. З урахуванням описаного вище алгоритм знаходження суми чисел можна записати так. 1. Початок. 2. Поточне значення суми дорівнює 0 (s:=0). 3. Зробити поточним перший рядок. 4. Зробити поточним перший стовпець. 5. Вибрати число (а) з поточного рядка поточного стовпця. 6. Додати до поточної суми поточне число (s."=s + а). 7. Збільшити на одиницю номер поточного стовпця. 8. Збільшити на одиницю номер поточного рядка. 9. Повторити пункти 4 - 9 три рази. 10. Кінець. Програма реалізації поданого алгоритму подана на рисунку 3.82. У програмі враховано те, що кожне наступне число рядка Приклад. На рисунку 3.83 подано орнамент. Його аналіз показує, що зображено 6 рівносторонніх трикутників різних кольорів. Кожний з них зсунутий один відносно другого на половину його сторони. Програма малювання орнаменту наведена на рисунку 3.83. Виконуємо 1. Два цілих числа уводяться з клавіатури. Розробити програму для отримання таблиці множення більшого числа. 2. Випадкові числа генеруються в діапазоні від 2 до 7 і додаються один до одного. Розробити програму визначення кількості випадкових чисел, сума яких стане більше 49. 3. У пам'яті банкомату зберігається список купюр 20 і 50 грн. На рисунку 3.85 наведена програма обчислення загальної суми грошей і кількості кожних купюр. "* У програмі використані такі змінні: k - загальна кількість купюр у банкоматі (довжина списку), а - поточний номер купюри у списку, х - кількість купюр 20 грн, у - кількість купюр 50 грн, s - загальна сума грошей у банкоматі, Банкомат - список купюр у банкоматі. Проаналізуйте й виконайте програму. Доведіть, що вона функціонує правильно. Змініть список Банкомату і перевірте правильність програми. Перед останнім етапом експедиції, який мае тривати 10 днів, запас води складав 200 літрів. З кожним наступним днем потреба у воді зростає на 10% відносно витрати води за попередній день. За перший день витрата води склала х літрів (значення х уводиться з клавіатури). Експедиція триває доти, поки є вода. За яких умов експедиція може завершити шлях без зовнішньої допомоги? Якщо не вистачить води, то на скільки днів? 5. На рисунку 3.86 подано програму, яка моделює табло з демонстрацією 6-ти найбільших річок світу (Ніл, Амазонка, Янцзи, Міссісіпі, Єнісей, Іртиш). На табло послідовно висвітлюються перераховані річки світу. Виконайте програму і переконайтеся, що вона функціонує правильно. Внесіть доповнення у список річок і перевірте роботу програму. Перевіряємо себе 1. Які алгоритми називають циклічними з передумовою? 2. За допомогою якої команди Скретч реалізується цикл з передумовою? 3. Які алгоритми називають циклічними з післяумовою? 4. За допомогою якої команди Скретч реалізується цикл з післяумовою? 5. Які алгоритми називають з вкладеними циклами? 6. Накресліть графічну схему циклічного алгоритму з передумовою, 7. Накресліть графічну схему циклічного алгоритму з післяумовою. 8. Наведіть приклад циклічного алгоритму з передумовою. 9. Наведіть приклад циклічного алгоритму з післяумовою. 10. Наведіть приклад алгоритму з вкладеними циклами. Решебник ответы 7 класс по украинскому языку Новые учебники 7 класс 2015 алгебре | |
