Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Новые рефераты » Динамічне програмування, алгоритми на графах

Реферат Динамічне програмування, алгоритми на графах





Міністерство освіти Республіки Білорусь

Установа освіти

В«Гомельський державний університет ім. Ф. Скорини В»

Математичний факультет

Кафедра МПМ








Реферат

Динамічне програмування, алгоритми на графах


Виконавець:

Студентка Старовойтова А.Ю.

Науковий керівник:

Канд. фіз-мат. наук, доцент Лебедєва М.Т.










Гомель 2007


Зміст


Введення

1. Алгоритми, використовують рішення додаткових підзадач

2. Основні визначення теорії графів

3. Пошук шляху між парою вершин незваженого графа

4. Шляхи мінімальної довжини у зваженому графі

Висновок

Література


Введення

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

Теорія графів містить величезну кількість визначень, теорем і алгоритмів. І тому даний матеріал не може претендувати, і не претендує, на повноту охоплення матеріалу. Однак, на думку автора, пропоновані відомості є хорошим компромісом між обсягом матеріалу і його "коефіцієнтом корисної дії" в практичному програмуванні та вирішенні олімпіадних завдань. p> Іноді вирішення основного завдання доводиться формулювати в термінах кілька модифікованих підзадач. Саме такі проблеми розглядаються в даній роботі. b>
1. Алгоритми, використовують рішення додаткових підзадач

Задача 9 . Потрібно підрахувати кількість різних розбиттів числа N на натуральні доданки. Два розкладання вважаються різними, якщо одне не можна отримати з іншого шляхом перестановки доданків.


В 

Рішення. Для того щоб підрахувати кількість різних розбиттів числа N на довільні натуральні доданки, попередньо підрахуємо кількості разбиений на наступні групи доданків: 1) розбиття тільки на одиниці (Очевидно, що для будь-якого числа таке розбиття єдино), 2) розбиття на одиниці і двійки такі, що хоча б одна двійка в розбитті присутній і т.д. Останню групу представляє саме число N . Очевидно, що кожне розбиття числа N можна приписати тільки до однієї з розглянутих груп, залежно від значення j - максимального доданка в тому чи іншому розбитті. Позначимо кількість розбиттів в кожній з груп t ( N , j ). Тоді шукану кількість розбиттів дорівнює сумі разбиений по всіх можливих групам. Введення таких підзадач призводить до нескладного способу підрахунку числа розбиття. А саме, так як в будь-якому з разбиений j -ої групи присутній число j , то ми можемо вирахувати з N число j і скласти розбиття вже числа N - j на доданки, що не перевищують j . Тобто ми прийшли до наступного рекурентному співвідношенню:

Тепер очевидно, що якщо ми маємо можливість завести двовимірний масив розміром N ' N , і будемо заповнювати його в порядку зростання номерів рядків, то завдання буде легко вирішена. Однак легко помітити, що рішення частини підзадач ніяк не беруть участь у формуванні рішення. Наприклад, при обчисленні кількості розбиттів числа 10 на доданки будуть отримані, але не використані значення t (9, j ) для j = 2 .. 9 і т. д. Для того щоб не виробляти зайвих обчислень, застосуємо динамічне програмування "зверху вниз" (усі попередні завдання вирішувалися "знизу вгору"). Для цього завдання будемо вирішувати все ж рекурсивно, використовуючи формулу (*), але відповіді до вже вирішеним підзадач будемо запам'ятовувати в таблиці. Спочатку таблиця порожня (вірніше заповнимо елементи, значення яких за формулою (*) дорівнює 0 або 1, а інші значення, наприклад, числом -1). Коли в процесі обчислень підзадача зустрічається перший раз, її рішення заноситься в таблицю. У Надалі рішення цієї підзадачі береться з таблиці. Таким чином ми отримали прийом поліпшення рекурсивних алгоритмів, а "зайві" підзадачі тепер вирішуватися не будуть.

Наведемо програму для вирішення цього завдання.


var i, j, k, n: byte;

sum: longint;

table: array [1 .. 120,1 .. 120] of longint;

function t (n, k: byte): longint;

var i, s: byte;

begin

if table [n, k] <0 then

{інші елементи не перераховуємо}

begin

table [n, k]: = 0;

for i: = 1 to k do

inc (table [n, k], t (n-k, i))

end;

t: = table [n, k]

end;

begin

read (n);

fillchar (table, sizeof (table), 0);

for i: = 1 to n do

begin

table [i, i]: = 1;

<...


сторінка 1 з 8 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Алгоритми Деккера і Петерсона, їх застосування для вирішення проблеми крити ...
  • Реферат на тему: Види і властивості алгоритмів. Рішення завдання Майхілла (про стрілки)
  • Реферат на тему: Визначення числа підприємств, обсягу продукції, середньооблікового числа пр ...
  • Реферат на тему: Знаходження оптимального числа листів фанери и Вирізання потрібного числа з ...
  • Реферат на тему: Рішення задач із застосуванням теорії графів