підзадачі головного завдання).
Метод спадного проектування передбачає послідовне розкладання загальної функції обробки даних на прості функціональні елементи («зверху - вниз»). У результаті будується ієрархічна схема, що відображає склад і взаімоподчіненность окремих функцій.
Створення програми з використанням технології низхідній (зверху - вниз) розробки з покрокової деталізацією. Ця технологія є невід'ємною частиною створення добре структурованих програм. Вона починаємо з записи псевдокоду вершини.
Вершина - це єдина пропозиція (оператор), що виражає загальне призначення програми. Таким чином, вершина відображає всю програму в цілому.
Вершина рідко відображає достатню кількість деталей, на підставі яких можна написати програму на мові програмування.
Тому потрібен процес деталізації.
Для цього вершину ділять на ряд дрібніших завдань і записують їх у тому порядку, в якому вони повинні виконуватися.
Багато програм можуть бути логічно розділені на три етапи:
- етап завдання початкових значень, в якому задаються початкові значення змінних програми;
- етап обробки даних, в якому вводяться дані і встановлюються значення відповідних змінних програми;
- завершальний етап, в якому обчислюються і друкуються остаточні результати.
Програміст завершує процес низхідній розробки з покрокової деталізацією, коли алгоритм на псевдокоде настільки деталізований, щоб його псевдокод можна було б перетворити в програму мовою програмування.
Реалізована програма виявиться в цьому випадку простий і наочною.
Спадний проектування може здійснюватися такими способами:
- За алгоритмом програми створюється текст головного модуля, що містить у вигляді коментарів основни6е етапи рішення завдання. Бажано, щоб кожен рядок коментаря представляла собою виклик підпрограми, вирішальною підзадачу головного завдання.
- Основні етапи замінюються рядком коду, що представляє собою виклик функції, відповідної етапу розв'язання задачі. Вибирається ім'я функції, тип значення і визначається список параметрів.
- По кожній новоствореної функції записується визначення. Тіло функції містить коментарі. Процедура повторюється до тих пір, поки коментарів не будуть замінені кодом мовою обраною мовою програмування.
Динамічне програмування
Динамічне програмування в теорії управління і теорії обчислювальних систем - спосіб вирішення складних завдань шляхом розбиття їх на простіші підзадачі. Він застосуємо до завдань з оптимальною підструктури, виглядаючим як набір перекриваються подзадач, складність яких трохи менше початкової. У цьому випадку час обчислень, у порівнянні з «наївними» методами, можна значно скоротити.
Ключова ідея в динамічному програмуванні досить проста. Як правило, щоб вирішити поставлене завдання, потрібно вирішити окремі частини задачі (підзадачі), після чого об'єднати рішення підзадач в одне спільне рішення. Часто багато хто з цих підзадач однакові. Підхід динамічного програмування полягає в тому, щоб вирішити кожну підзадачу тільки один раз, скоротивши тим самим кі...
