Тема: Методи розробки алгоритмів і програм.

Зрозуміло, що багато прикладних задач можна розв’язати різними способами. Вибір методу розв'язку визначається із:

1. постановки задачі;

2. наявними програмними ресурсами;

Вимогами по швидкодії, використанням ресурсів ЕОМ.

Останній пункт означає, що обраний варіант програмування задачі повинен реалізувати її за найменший час або якомога менше використовувати ресурси оперативної та зовнішньої пам'яті. Зрозуміло, що час роботи програми в часових одиницях не є критерієм ефективності, оскільки він ще суттєво залежить від архітектури ЕОМ, тому цей варіант оцінювання ефективності проводять за кількістю так званих важких операцій даної задачі.

Враховуючи багатоманіття способів розв'язку конкретної задачі, потрібно володіти основними методами побудови алгоритмів та способами оцінювання їх ефективності. Окрім розглянутої часової ефективності це може бути критерій стійкості розв'язку, повноти розв'язку, оптимальності.

Тема: Метод повного перебору.

Застосовується так званих задачах вибору оптимального варіанту. Полягає у наступному: перебираються всі можливі варіанти розв'язку і для кожного з них визначається деяка цільова функція, яка має набувати

Переваги: простота методу як в алгоритмічному варіанті, так і в програмній реалізації.

Недоліки: в більшості випадків надзвичайно великий об’єм обчислень, що суттєво збільшує час роботи програми.

Наприклад. Пошук мінімального (максимального) елемента у масиві. Для п-елементів є величина порядку о(п). Для даної задачі чи не єдиний алгоритм розв'язку.

Задача „Комівояжер”. Дано п-пунктів, між якими є шляхи сполучення. Відомі вартості всіх сполучень, потрібно побудувати такий маршрут, що сполучає всі пункти лише по одному разу, при якому витрати будуть мінімальними.

Згідно з МПП перебираються всі можливі варіанти маршруту, для кожного з яких встановлюється цільова функція. В якості розв'язку буде той варіант, де функція мінімальна.

При програмуванні даної задачі за цим методом використовується п вкладених циклів по всіх можливих пунктах.

for i1=1 to n do

Begin

f:=0;

for i2:=1 to n do

if i2<>i1 then

Begin

f:=f+a[i1,i2]

for i3:=1 to n do

if i3<>i2 then

Begin

... ... ... ...

if in<>in-1 then

f:=f+a[in-1,in]

end; ... end;

if f<min then min:=f;

end;

Даний фрагмент програми передбачає перебір всіх можливих значень величини f для різних варіантів маршрутів, змінна і має бути достатньо велике значення.

Цей варіант передбачає наявність всіх шляхів сполучень, тому у випадку відсутності частини шляхів сполучень потрібно передбачити вилучення тих варіантів, які не можливі за умовою.

Тема: Метод „розділяй і володарюй”.

Ідея методу полягає по розділені складної задачі на декілька окремих під задач, що має цілісну структуру. Такий поділ дозволяє отримати декілька простіших задач, кожну з яких можна окремо розв’язати. Остаточний розв'язок є об'єднанням всіх часткових розв’язків. Метод РІВ передбачає адитивний поділ. Кожна під задача має той самий характер, що і основна задача. Об'єднання часткових розв’язків виконується не комбінуванням а сумуванням.

<== попередня сторінка	\|	наступна сторінка ==>
Так оголошені вказівники на об’єкти класів є статичними змінними – це чотирибайтні числа-адреси у пам'яті.	\|	Якщо ж поділ дає різноманітні задачі, метод виділення під цілей.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.