Мета уроку: Дати поняття про основні ідеї технології структурного програмування, про сутність методу покрокової деталізації та послідовного уточнення алгоритму.
Теоретичний матеріал
Під час побудови алгоритму часто виникає необхідність пояснити виконавцю деякі складні дії, виконання яких не входить у систему команд виконавця. Наприклад, перший раз даючи дитині завдання пришити ґудзик до сорочки, їй треба пояснити, як слід добирати нитки для шиття, як протягнути нитку в голку, як тримати голку та ґудзик під час роботи, яка різниця між пришиванням ґудзика до тоненької сорочки та товстої куртки (в другому випадку беруть ґудзик на «ніжці»). У подальшому такі пояснення будуть зайві, оскільки алгоритм «пришивання ґудзика» стає вже командою в системі команд виконавця «дитина».
Отже, кожна дія людини (якщо вона її може виконати) може вважатися командою її «системи команд», хоча колись, на етапі навчання, учитель або хтось інший ретельно пояснював, яку послідовність дій треба виконати, щоб досягти поставленої мети.
Отже, кожну задачу можна вважати окремою командою виконавцю, якщо його навчено виконувати поставлене завдання, коли ж виконавець не знає, як розв’язувати запропоновану задачу, необхідно розкласти її на такі підзадачі, які є легкими для виконання, тобто входять до системи команд виконавця. Таким чином отримують алгоритм, що складається з простих команд, зрозумілих виконавцю, або остаточно переконуються, що дана задача непосильна для певного виконавця, оскільки в його системі команд не існує команд, необхідних для вирішення цієї задачі. Наприклад, як би ми не деталізували дошколярику алгоритм побудови багатоповерхової будівлі, таке завдання, все ж таки, залишиться для дитини непосильним.
Примітка: на даному етапі уроку можна дати учням завдання придумати задачу, яка б була непосильною для вибраного виконавця (виконавцем може бути людина, комп’ютер, якийсь пристрій тощо). Наприклад, спробуйте створити алгоритм виконання ремонту кімнати, розрахований на виконавця «екскаватор».
Запропонований підхід до конструювання алгоритмів називається методом покрокової деталізації зверху донизу. При такому підході кожну операцію можна подати у вигляді лише одного з трьох типів базових структур алгоритмів—лінійної (у літературі часто ця структура називається слідування),розгалуження та повторення (циклу). Ступінь деталізації алгоритму при цьому сильно залежить від того, на якого виконавця орієнтовано виконання даного алгоритму. Подумайте, наприклад, як розробляється конструкція сучасного теплоходу, автомобілю або літаку. Адже складну конструкторську задачу неможливо розв’язати без поступового заглиблення в деталі.
Метод покрокової деталізації конструювання алгоритмів не враховує конкретні особливості поставленої задачі та вибір певного виконавця. Проте набір команд із системи команд вибраного виконавця суттєво впливає на ступінь деталізації алгоритму та на його структуру.
Розглянемо, наприклад, простий алгоритм «переходу через вулицю». Взагалі для кожної дитини можна вважати це командою, що входить до її «системи команд». Але кожний пам’ятає, як у дитинстві батьки та вихователі неодноразово повторювали: якщо там, де необхідно перейти вулицю, є підземний перехід, то скористайся ним, якщо немає—відшукай місце, де є світлофор, і перейди вулицю, користуючись правилами; якщо немає ані підземного переходу, ані світлофора... (далі діти самостійно продовжать цей алгоритм). Однак, навіть у такому алгоритмі є необхідність дещо деталізувати. Наприклад, що значить «перейди вулицю, користуючись правилами при наявності світлофора»? А якщо алгоритм складається для зовсім маленької дитини, то що таке світлофор і як його шукати? А якщо виконавець—взагалі прибулець з інших світів? Що таке «зелене», «червоне», «жовте»? Що таке підземний перехід? Перелік запитань можна продовжувати. Алгоритми, що складаються для розв’язування окремих підзадач основної задачі, називаються допоміжними. Вони створюються при поділі складної задачі на прості або при необхідності багаторазового використання того ж самого набору дій в одному або різних алгоритмах.
Допоміжний алгоритм повинен мати тільки один вхід та один вихід, причому того, хто користується ним, зовсім не цікавить, як реалізований цей алгоритм. Головне, щоб усі команди, які входять до складу допоміжного алгоритму, входили до системи команд обраного виконавця. Зверніть увагу й на те, що в реальному житті допоміжні алгоритми можуть виконувати навіть інші виконавці. Наприклад, якщо батьки вдома вирішили зробити ремонт, то зовсім не обов’язково, що вони власноруч повинні зробити шпалери та клей. Алгоритми виробництва матеріалів існують, і їх хтось виконує, а ми тільки користуємося результатами такої роботи.
Таким чином, можна вважати допоміжний алгоритм своєрідним «чорним ящиком», на вхід якого подаються деякі вхідні дані, а на виході ми отримуємо очікуваний результат. Головне — чітко домовитись про правила оформлення вхідних даних та результату. Невиконання домовленостей може призвести до збою у виконанні допоміжного алгоритму або до отримання неочікуваного результату. Описаний метод послідовної деталізації лежить в основі технології структурного програмування і широко застосовується у таких мовах програмування, як Паскаль, С, C++ та інших мовах високого рівня. При описуванні програми для комп’ютера мовами високого рівня допоміжні алгоритми реалізовуються у вигляді підпрограм. Правила опису, звернення до них та повернення в точку виклику визначаються конкретною мовою програмування. Для зручності часто використовувані підпрограми можна об’єднувати в бібліотечні модулі і за необхідності підключати їх в свої програми.
Домашнє завдання
• Вивчити означення, що були прочитані на лекції;
• Придумати та записати алгоритм, в якому залежно від вибору певноговиконавця необхідний різний ступінь деталізації;
• Продумати приклади алгоритмів, для яких будь-який ступінь деталізації все одно не дозволить виконати їх заданим виконавцем.