Реферат на тему:
Метод покрокової деталізації в програмуванні
Принцип спадного проектування алгоритмів і програм (метод проектування зверху вниз)
Для створення "хороших" програм необхідно дотримуватися певних правил програмування. У зв'язку з цим становить інтерес розглянути новий підхід до розробки програм, що отримала досить широке поширення в останні роки - структурне програмування.
Ідеї структурного програмування були висловлені Е. Дейкстри ще в 1965 р. Пізніше їм було викладено основні положення структурного програмування в роботі "Нотатки з структурному програмуванню". З тих пір термін "структурне програмування" широко використовується, але в різних значеннях і без строгого визначення.
Структурне програмування - метод програмування, використання якого знижує ймовірність помилок у процесі складання програм, підвищує їх надійність, ефективність, спрощує розуміння, забезпечує створення програм, структура яких ясна і нерозривно пов'язана зі структурою вирішуваних завдань.
Метою структурного програмування є спроба спростити процес написання правильних програм і забезпечити можливість читання програми від початку до кінця, слідуючи логіці.
Програми, написані з використанням традиційних методів, зазвичай мають хаотичну структуру, тому і читання, і розуміння їх утруднено. Структуровані програми можна читати як звичайний текст зверху вниз без перерви, так як вони мають послідовну організацію, тобто застосування методу структурного програмування покращує ясність і читабельність програм.
Інакше його ще називають методом покрокової деталізації.
Низхідний проектування програми, коли спочатку програма розглядається, як сукупність дій, кожна з яких потім деталізується і представляється як послідовність більш простих і конкретних дій і т.д. Аж до окремих операторів мови; такий підхід дозволяє реалізувати наявність двох видів підпрограм в мові - процедур і функцій.
Спочатку продумується загальна структура алгоритму без детального опрацювання окремих його частин. Блоки потребують подальшої деталізації, позначаються пунктирною лінією. Далі опрацьовуються окремі блоки, не деталізовані на попередньому кроці.
Таким чином, на кожному кроці розробки уточнюється реалізація фрагмента алгоритму (або програми), тобто вирішується простіше завдання. Повністю закінчивши деталізацію всіх блоків, отримуємо рішення задачі в цілому.
Якщо на кожному кроці деталізації використовувати принципи структурного програмування, то виходить хороша структурована програма в цілому.
Процес проектування зверху вниз блок-схеми алгоритму показаний на нижче наведеному прикладі.
Приклад. Обчислити значення функції y = f (x) для x, що змінюється від x 0 до xn з кроком h:
, Де
x 0 = -5; xn = 10; h = 1; a = -1; b = 3.5.
Технологія низхідного проектування з покрокової деталізацією є невід'ємною частиною створення добре структурованих програм. Розробка алгоритму методом покрокової деталізації полягає в наступному:
Будь-який алгоритм можна представити у вигляді одного приписи - у вигляді постановки завдання. Але якщо виконавець не навчений виконувати заданий припис, то виникає необхідність представити даний припис у вигляді деякої сукупності більш простих приписів. Якщо виконавець не може виконати і деякі з них, то такі приписи знову представляються у вигляді сукупності ще більш простих приписів. Об'єднуючи так отримані приписи в єдину сукупність виконуваних у певному порядку приписів отримують виконання вихідного завдання в цілому.
Переваги методу покрокової деталізації:
1. Зберігається концептуальна цілісність програми: від складного до простого.
2. Проектування програми, кодування, перевірку і документування можна робити паралельно.
3. У кожний момент часу (навіть на початку розробки) є працюючий варіант програми.
4. Фрази природної мови, будучи закоментувати, служать хорошим путівником по програмі.
У процесі створення програми особливу увагу потрібно приділяти розробці алгоритмів. Такий підхід допоможе уникнути помилок, допущених при проектуванні програмного продукту. Наявність подібних помилок зажадає багато часу на виправлення, повернення на попередні етапи розробки з метою їх доопрацювання.
При розробці алгоритмів зазвичай використовують метод покрокової деталізації (поетапно):
1. На першому етапі описуються рішення поставленої перед програмою завдання, виділяються підзадачі.
2. У наступних етапах описується рішення кожної підзадачі, виділяючи при цьому нові підзадачі. Так відбувається до тих пір, поки рішення підзадач не буде очевидним. Рекомендовано рішення кожної задачі описувати за допомогою 1 - 2 конструкцій не більше, щоб більш чітко уявляти структуру програми.
Наприклад: Потрібно розробити програму, яка з певною точністю eps знаходить значення аргументу x по заданому значенню функції y при відомому значенні n
Де: n> 1, x> 0
При n> 1 функція є монотонно зростаючою, значення аргументу x можна визначити за допомогою методу половинного ділення. У чому полягає це метод?
1. Знаходимо відрізок [x1, x2], який задовольняє умові: f (x1) <= y <= f (x2).
2. Ділимо отриманий відрізок навпіл: xt = (x1 + x2) / 2 і определеяются в якій половині відрізка знаходиться x. Для цього порівнюємо два значення: f (x1) і y.
3. Отриманий відрізок знову ділимо навпіл, процес повторюється до тих пір, поки різниця x1 і x2 не стане менше заданого значення eps.
При розробці алгоритму даної програми використовуємо метод покрокової деталізації.
1 етап. Загальна структура програми:
Програма:
Ввести y, n, eps
Визначити x
Вивести x, y
Кінець.
2 етап. Деталізуємо операцію визначення x:
Визначити x
Визначити x1 таке, що f (x1) <= y
Визначити x2 таке, що f (x2)> = y
Визначити x на інтервалі [x1, x2]
Все.
3 етап. Деталізуємо операцію визначення x1. Значення x1 підбираємо таким чином, щоб виконувалася умова f (x1) <= y. Відомо, що x> 0, отже, беремо будь-яке значення x, наприклад x1 = 1 і будемо його пследовательно зменшувати, допустимо в 2 рази. Таким чином визначимо значення x1, задовольняє даній умові:
Визначити x1:
x1: = 1
цикл - поки f (x1)> y
x1: = x1 / 2
Всі - цикл
Всі
4 етап. Деталізуємо операцію визначення x2. Значення x2 визначаємо аналогічно x1, але початкове значення будемо послідовно збільшувати в 2 рази.
Визначити x2:
x2: = 1
цикл - поки f (x2) <y
x2: = x2 * 2
Всі - цикл
Все.
5 етап. Деталізуємо операцію визначення x. Визначення x виконується послідовним скороченням відрізка [x1, x2].
Визначити x:
цикл - поки x2-x1> eps
скоротити відрізок [x1, x2]
всі - цикл
Все.
6 етап. Деталізуємо операцію скорочення відрізка [x1, x2]. Інтервал визначення x скорочуємо діленням навпіл і відкидаємо половину, яка не задовольняє умові f (x1) <= y <= f (x2):
Скоротити інтервал визначення x:
xt = (x1 + x2) / 2
якщо f (xt)> y
то x2: = xt
інакше x1: = xt
все - якщо
Все.
Таким чином, за 6 етапів розроблено наступний алгоритм:
Програма:
Ввести y, n, eps
x1: = 1
цикл - поки f (x1)> y
x1: = x1 / 2
всі - цикл
x2: = 1
цикл - поки f (x2) <y
x2: = x2 * 2
всі - цикл
цикл - поки x2-x1> eps
xt: = (x1 + x2) / 2
якщо f (xt)> y
то x2: = xt
інакше x1: = xt
все - якщо
всі - цикл
Вивести xt, y
Кінець.
Таким чином, на кожному етапі вирішується просте завдання, що полегшує розробку алгоритму. Для вирішення даної проблеми було використано псевдокод, але можна використовувати і блок - схеми алгоритмів
Плюси і мінуси методик програмування
Після того, як ми розібралися в суті обох методик, давайте розглянемо, які зручності ми отримуємо від їх використання, і з якими проблемами стикаємося.
Жоден практикуючий програміст, звичайно, не буде жорстко дотримуватися однієї з показаних методик. У цій роботі ми завжди використовуємо і ті, і інші прийоми.
Інші проблеми структурного програмування
Текст програми повинен бути удобочитаем і зрозумілий людині. Існує декілька хитрощів, які допомагають зробити код читабельним:
o Писати треба просто. Починаючі програмісти частенько перетяжеляют код, використовуючи "красиві" хитромудрі конструкції. Однак, цим вони отримують одразу дві головні болі: по-перше, такий код складніше читати, а по-друге, в мудровані ділянки легко внести помилку. Звичайно, в будь-якому питанні потрібно дотримуватися золотої середини. Алгоритм бульбашкової сортування, скажімо, запам'ятати легше всього, але на практиці краще використовувати більш ефективні методи.
o Використовувати синтаксичні угоди. Перш за все, до них відноситься система синтаксичних відступів. Кожен наступний вкладений блок відсувається щодо попереднього на декілька позицій (зазвичай 2-3). У текстовому редакторі середовища цей відступ зручно вказати як ширину поля табуляції.
o Ще більш неправі ті, хто прагне "упакувати" максимум інформації в один рядок. Інша угода відноситься до імен змінних і називається "угорської нотацією".
o Ви поліпшите читабельність, якщо будете дотримуватися взаємною порядку операторів, описаного у вихідній версії мови. Скажімо, вважається, що в Паскалі блок опису констант const має стояти перед блоком опису типів type. Середовище програмування, швидше за все не вважатиме помилкою, якщо ви поміняєте ці розділи місцями, але з міркувань читабельності краще цього не робити.
o Створювати "говорять" ідентифікатори. Якщо ви використовуєте тільки Однолітерні змінні "a", "x", "n", як у найпростіших версіях Бейсіка, або ідентифікатори-абревіатури "nklm", "prs", як писали на старому Fortranе, чекайте неприємностей. Вам доведеться принаймні тягнути через весь проект довгі таблиці, що пояснюють призначення параметрів. Name завжди краще х, а OldValue - зрозуміліше a.
o Не лінуватися вставляти коментарі. Особливо складні алгоритми, оригінальні прийоми потрібно коментувати як можна докладніше, інакше, повернувшись через пару місяців до свого старого тексту, ви будете кілька годин заново проходити той самий шлях. Зручно давати коментар-специфікацію до підпрограми відразу після або відразу до її заголовка.
o Нарешті, по можливості робити підпрограми невеликими, оптимально - не більше однієї друкованої сторінки.
Необхідно знижувати трудомісткість тестування і налагодження програми (Вартість розробки - на 80% складається з вартості тестування та налагодження. Тому, на жаль, саме на них і починають заощаджувати багато нинішніх розробники). Тут існує тільки один шлях: акуратніше складати код і ретельніше планувати тестування. У серйозних компаніях формують окремий відділ бета-тестування, який займається виловлювання помилок - як інтерфейсних, так і внутрішніх.
Проблема верифікації - автоматичного доведення правильності роботи програми. Якщо програма відпрацювала правильно на десяти тестах, це, в принципі, не означає, що на одинадцятому вона не "впаде". Але ж не можна перевірити всі можливі комбінації параметрів, тому доводиться десь зупинитися. З теоретичної точки зору, питання про верифікацію надзвичайно складний. На практиці зазвичай обмежуються обраним для даної задачі набором тестів.
Спрощення модифікації програми. Будь-яка корисна програма зараз вимагає постійного оновлення, розширення функцій, випуску нових версій: на цьому й живуть серйозні софтверні корпорації. Краще всього, якщо створюючи першу версію, ви вже будете думати про наступну. Легкості змін служать і окремі прийоми програмування: використання об'єктів (а зараз компонентів), модульна структура, використання динамічно підключаються, заготовок під майбутні функції й т.д.
Ефективність програми. Оптимально програма займає мінімум пам'яті і виконується за мінімум часу. Останнім часом частенько ефективність програм підміняється "необхідними системними вимогами" - користувача змушують постійно нарощувати потужність обладнання. Але якщо у конкурента вимоги до системи виявляться нижче, а процеси стануть виконуватися швидше, користувач неодмінно відвернеться від вашої програми.
Метод покрокової деталізації в програмуванні
Принцип спадного проектування алгоритмів і програм (метод проектування зверху вниз)
Для створення "хороших" програм необхідно дотримуватися певних правил програмування. У зв'язку з цим становить інтерес розглянути новий підхід до розробки програм, що отримала досить широке поширення в останні роки - структурне програмування.
Ідеї структурного програмування були висловлені Е. Дейкстри ще в 1965 р. Пізніше їм було викладено основні положення структурного програмування в роботі "Нотатки з структурному програмуванню". З тих пір термін "структурне програмування" широко використовується, але в різних значеннях і без строгого визначення.
Структурне програмування - метод програмування, використання якого знижує ймовірність помилок у процесі складання програм, підвищує їх надійність, ефективність, спрощує розуміння, забезпечує створення програм, структура яких ясна і нерозривно пов'язана зі структурою вирішуваних завдань.
Метою структурного програмування є спроба спростити процес написання правильних програм і забезпечити можливість читання програми від початку до кінця, слідуючи логіці.
Програми, написані з використанням традиційних методів, зазвичай мають хаотичну структуру, тому і читання, і розуміння їх утруднено. Структуровані програми можна читати як звичайний текст зверху вниз без перерви, так як вони мають послідовну організацію, тобто застосування методу структурного програмування покращує ясність і читабельність програм.
Інакше його ще називають методом покрокової деталізації.
Низхідний проектування програми, коли спочатку програма розглядається, як сукупність дій, кожна з яких потім деталізується і представляється як послідовність більш простих і конкретних дій і т.д. Аж до окремих операторів мови; такий підхід дозволяє реалізувати наявність двох видів підпрограм в мові - процедур і функцій.
Спочатку продумується загальна структура алгоритму без детального опрацювання окремих його частин. Блоки потребують подальшої деталізації, позначаються пунктирною лінією. Далі опрацьовуються окремі блоки, не деталізовані на попередньому кроці.
Таким чином, на кожному кроці розробки уточнюється реалізація фрагмента алгоритму (або програми), тобто вирішується простіше завдання. Повністю закінчивши деталізацію всіх блоків, отримуємо рішення задачі в цілому.
Якщо на кожному кроці деталізації використовувати принципи структурного програмування, то виходить хороша структурована програма в цілому.
Процес проектування зверху вниз блок-схеми алгоритму показаний на нижче наведеному прикладі.
Приклад. Обчислити значення функції y = f (x) для x, що змінюється від x 0 до xn з кроком h:
x 0 = -5; xn = 10; h = 1; a = -1; b = 3.5.
Технологія низхідного проектування з покрокової деталізацією є невід'ємною частиною створення добре структурованих програм. Розробка алгоритму методом покрокової деталізації полягає в наступному:
Будь-який алгоритм можна представити у вигляді одного приписи - у вигляді постановки завдання. Але якщо виконавець не навчений виконувати заданий припис, то виникає необхідність представити даний припис у вигляді деякої сукупності більш простих приписів. Якщо виконавець не може виконати і деякі з них, то такі приписи знову представляються у вигляді сукупності ще більш простих приписів. Об'єднуючи так отримані приписи в єдину сукупність виконуваних у певному порядку приписів отримують виконання вихідного завдання в цілому.
Переваги методу покрокової деталізації:
1. Зберігається концептуальна цілісність програми: від складного до простого.
2. Проектування програми, кодування, перевірку і документування можна робити паралельно.
3. У кожний момент часу (навіть на початку розробки) є працюючий варіант програми.
4. Фрази природної мови, будучи закоментувати, служать хорошим путівником по програмі.
У процесі створення програми особливу увагу потрібно приділяти розробці алгоритмів. Такий підхід допоможе уникнути помилок, допущених при проектуванні програмного продукту. Наявність подібних помилок зажадає багато часу на виправлення, повернення на попередні етапи розробки з метою їх доопрацювання.
При розробці алгоритмів зазвичай використовують метод покрокової деталізації (поетапно):
1. На першому етапі описуються рішення поставленої перед програмою завдання, виділяються підзадачі.
2. У наступних етапах описується рішення кожної підзадачі, виділяючи при цьому нові підзадачі. Так відбувається до тих пір, поки рішення підзадач не буде очевидним. Рекомендовано рішення кожної задачі описувати за допомогою 1 - 2 конструкцій не більше, щоб більш чітко уявляти структуру програми.
Наприклад: Потрібно розробити програму, яка з певною точністю eps знаходить значення аргументу x по заданому значенню функції y при відомому значенні n
Де: n> 1, x> 0
При n> 1 функція є монотонно зростаючою, значення аргументу x можна визначити за допомогою методу половинного ділення. У чому полягає це метод?
1. Знаходимо відрізок [x1, x2], який задовольняє умові: f (x1) <= y <= f (x2).
2. Ділимо отриманий відрізок навпіл: xt = (x1 + x2) / 2 і определеяются в якій половині відрізка знаходиться x. Для цього порівнюємо два значення: f (x1) і y.
3. Отриманий відрізок знову ділимо навпіл, процес повторюється до тих пір, поки різниця x1 і x2 не стане менше заданого значення eps.
При розробці алгоритму даної програми використовуємо метод покрокової деталізації.
1 етап. Загальна структура програми:
Програма:
Ввести y, n, eps
Визначити x
Вивести x, y
Кінець.
2 етап. Деталізуємо операцію визначення x:
Визначити x
Визначити x1 таке, що f (x1) <= y
Визначити x2 таке, що f (x2)> = y
Визначити x на інтервалі [x1, x2]
Все.
3 етап. Деталізуємо операцію визначення x1. Значення x1 підбираємо таким чином, щоб виконувалася умова f (x1) <= y. Відомо, що x> 0, отже, беремо будь-яке значення x, наприклад x1 = 1 і будемо його пследовательно зменшувати, допустимо в 2 рази. Таким чином визначимо значення x1, задовольняє даній умові:
Визначити x1:
x1: = 1
цикл - поки f (x1)> y
x1: = x1 / 2
Всі - цикл
Всі
4 етап. Деталізуємо операцію визначення x2. Значення x2 визначаємо аналогічно x1, але початкове значення будемо послідовно збільшувати в 2 рази.
Визначити x2:
x2: = 1
цикл - поки f (x2) <y
x2: = x2 * 2
Всі - цикл
Все.
5 етап. Деталізуємо операцію визначення x. Визначення x виконується послідовним скороченням відрізка [x1, x2].
Визначити x:
цикл - поки x2-x1> eps
скоротити відрізок [x1, x2]
всі - цикл
Все.
6 етап. Деталізуємо операцію скорочення відрізка [x1, x2]. Інтервал визначення x скорочуємо діленням навпіл і відкидаємо половину, яка не задовольняє умові f (x1) <= y <= f (x2):
Скоротити інтервал визначення x:
xt = (x1 + x2) / 2
якщо f (xt)> y
то x2: = xt
інакше x1: = xt
все - якщо
Все.
Таким чином, за 6 етапів розроблено наступний алгоритм:
Програма:
Ввести y, n, eps
x1: = 1
цикл - поки f (x1)> y
x1: = x1 / 2
всі - цикл
x2: = 1
цикл - поки f (x2) <y
x2: = x2 * 2
всі - цикл
цикл - поки x2-x1> eps
xt: = (x1 + x2) / 2
якщо f (xt)> y
то x2: = xt
інакше x1: = xt
все - якщо
всі - цикл
Вивести xt, y
Кінець.
Таким чином, на кожному етапі вирішується просте завдання, що полегшує розробку алгоритму. Для вирішення даної проблеми було використано псевдокод, але можна використовувати і блок - схеми алгоритмів
Плюси і мінуси методик програмування
Після того, як ми розібралися в суті обох методик, давайте розглянемо, які зручності ми отримуємо від їх використання, і з якими проблемами стикаємося.
| Програмування знизу вгору | Програмування зверху вниз |
| Переваги | |
| Можна об'єднати одночасно кілька підпрограм або модулів, так як часто одна підпрограма більш високого рівня в проекті замінює відразу декілька драйверів. | Серйозні помилки з великою ймовірністю відшукуються вже на ранніх стадіях проекту. |
| Підпрограми, що розробляються на ранній стадії роботи над проектом, часто виявляються надзвичайно корисними і в інших випадках. Зазвичай такі низькорівневі підпрограми об'єднують у власні бібліотеки. | На будь-якому етапі ми можемо працювати всього з однієї підпрограмою, а це дозволяє легше налагоджувати і змінювати код. |
| Залежність від машинних ресурсів у цілому виходить менше, так як тільки на пізніх етапах проекту ми працюємо з великим об'ємом коду. | Простіше дотримуватися єдиних правил при створенні різних версій програми. При цьому створювати корисні приватні підверсії також виявляється зручно. |
| Тестування виявляється більш систематичним. | |
| Недоліки | |
| Вже реалізовані, налагоджені й протестовані модулі іноді доводиться відкидати, якщо в викликають частинах програми виявилися непереборні помилки, і необхідно переробляти цілий блок. | Якщо виявляється, що модуль низького рівня неможливо реалізувати, як замислювалося, іноді доводиться переробляти весь проект. |
| При налагодженні поглинається більше машинних ресурсів | |
Інші проблеми структурного програмування
Текст програми повинен бути удобочитаем і зрозумілий людині. Існує декілька хитрощів, які допомагають зробити код читабельним:
o Писати треба просто. Починаючі програмісти частенько перетяжеляют код, використовуючи "красиві" хитромудрі конструкції. Однак, цим вони отримують одразу дві головні болі: по-перше, такий код складніше читати, а по-друге, в мудровані ділянки легко внести помилку. Звичайно, в будь-якому питанні потрібно дотримуватися золотої середини. Алгоритм бульбашкової сортування, скажімо, запам'ятати легше всього, але на практиці краще використовувати більш ефективні методи.
o Використовувати синтаксичні угоди. Перш за все, до них відноситься система синтаксичних відступів. Кожен наступний вкладений блок відсувається щодо попереднього на декілька позицій (зазвичай 2-3). У текстовому редакторі середовища цей відступ зручно вказати як ширину поля табуляції.
o Ще більш неправі ті, хто прагне "упакувати" максимум інформації в один рядок. Інша угода відноситься до імен змінних і називається "угорської нотацією".
o Ви поліпшите читабельність, якщо будете дотримуватися взаємною порядку операторів, описаного у вихідній версії мови. Скажімо, вважається, що в Паскалі блок опису констант const має стояти перед блоком опису типів type. Середовище програмування, швидше за все не вважатиме помилкою, якщо ви поміняєте ці розділи місцями, але з міркувань читабельності краще цього не робити.
o Створювати "говорять" ідентифікатори. Якщо ви використовуєте тільки Однолітерні змінні "a", "x", "n", як у найпростіших версіях Бейсіка, або ідентифікатори-абревіатури "nklm", "prs", як писали на старому Fortranе, чекайте неприємностей. Вам доведеться принаймні тягнути через весь проект довгі таблиці, що пояснюють призначення параметрів. Name завжди краще х, а OldValue - зрозуміліше a.
o Не лінуватися вставляти коментарі. Особливо складні алгоритми, оригінальні прийоми потрібно коментувати як можна докладніше, інакше, повернувшись через пару місяців до свого старого тексту, ви будете кілька годин заново проходити той самий шлях. Зручно давати коментар-специфікацію до підпрограми відразу після або відразу до її заголовка.
o Нарешті, по можливості робити підпрограми невеликими, оптимально - не більше однієї друкованої сторінки.
Необхідно знижувати трудомісткість тестування і налагодження програми (Вартість розробки - на 80% складається з вартості тестування та налагодження. Тому, на жаль, саме на них і починають заощаджувати багато нинішніх розробники). Тут існує тільки один шлях: акуратніше складати код і ретельніше планувати тестування. У серйозних компаніях формують окремий відділ бета-тестування, який займається виловлювання помилок - як інтерфейсних, так і внутрішніх.
Проблема верифікації - автоматичного доведення правильності роботи програми. Якщо програма відпрацювала правильно на десяти тестах, це, в принципі, не означає, що на одинадцятому вона не "впаде". Але ж не можна перевірити всі можливі комбінації параметрів, тому доводиться десь зупинитися. З теоретичної точки зору, питання про верифікацію надзвичайно складний. На практиці зазвичай обмежуються обраним для даної задачі набором тестів.
Спрощення модифікації програми. Будь-яка корисна програма зараз вимагає постійного оновлення, розширення функцій, випуску нових версій: на цьому й живуть серйозні софтверні корпорації. Краще всього, якщо створюючи першу версію, ви вже будете думати про наступну. Легкості змін служать і окремі прийоми програмування: використання об'єктів (а зараз компонентів), модульна структура, використання динамічно підключаються, заготовок під майбутні функції й т.д.
Ефективність програми. Оптимально програма займає мінімум пам'яті і виконується за мінімум часу. Останнім часом частенько ефективність програм підміняється "необхідними системними вимогами" - користувача змушують постійно нарощувати потужність обладнання. Але якщо у конкурента вимоги до системи виявляться нижче, а процеси стануть виконуватися швидше, користувач неодмінно відвернеться від вашої програми.