Реферат по темі:
Метод покрокової деталізації в програмуванні
Принцип спадного проектування алгоритмів і програм (метод проектування зверху вниз)
Для створення "хороших" програм необхідно дотримуватися певних правил програмування. В зв'язку з цим представляє інтерес розглянути новий підхід до розробки програм, що отримала досить широке поширення в останні роки - структурне програмування.
Ідеї структурного програмування були висловлені Е. Дейкстри ще в 1965 р. Пізніше їм були викладені основні положення структурного програмування в роботі "Нотатки по структурному програмуванню ". З тих пір термін "структурний програмування" широко використовується, але в різних сенсах і без строгого визначення.
Структурне програмування - метод програмування, використання якого знижує ймовірність помилок в процесі складання програм, підвищує їх надійність, ефективність, спрощує розуміння, забезпечує створення програм, структура яких ясна і нерозривно пов'язана зі структурою розв'язуваних завдань.
Метою структурного програмування є спроба спростити процес написання правильних програм і забезпечити можливість читання програми від початку до кінця, слідуючи логіці.
Програми, написані з використанням традиційних методів, зазвичай мають хаотичну структуру, тому і читання, і розуміння їх утруднено. Структуровані програми можна читати як звичайний текст зверху вниз без перерви, так як вони мають послідовну організацію, тобто застосування методу структурного програмування покращує ясність і читабельність програм.
Інакше його ще називають методом покрокової деталізації.
Спадний проектування програми, коли спочатку програма розглядається, як сукупність дій, кожне з яких потім деталізується і представляється як послідовність більш простих і конкретних дій і т.д. Аж до окремих операторів мови; такий підхід дозволяє реалізувати наявність двох видів підпрограм у мові - процедур і функцій.
Спочатку продумується загальна структура алгоритму без детального опрацювання окремих його частин. Блоки потребують подальшої деталізації, позначаються пунктирною лінією. Далі опрацьовуються окремі блоки, не деталізовані на попередньому кроці.
Таким чином, на кожному кроці розробки уточнюється реалізація фрагмента алгоритму (або програми), тобто вирішується більш просте завдання. Повністю закінчивши деталізацію всіх блоків, отримуємо рішення задачі в цілому.
Якщо на кожному кроці деталізації використовувати принципи структурного програмування, то виходить хороша структурована програма в цілому.
Процес проектування зверху вниз блок-схеми алгоритму показаний на наведеному нижче прикладі.
Приклад. Обчислити значення функції y = f (x) для x, що змінюється від x 0 до xn з кроком h:
, де
x 0 = -5; x n = 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)
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)
x2: = x2 * 2
все - цикл
цикл - поки x2-x1> eps
xt: = (x1 + x2)/2
якщо f (xt)> y
то x2: = xt
інакше x1: = xt
все - якщо
все - цикл...
