Сайт підготовки до олімпіади з інформатики

Динамічне програмування

            Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.

Задача 1. Хтось вмістив пару новонароджених кроликів в деякому місці, обгородженому з усіх боків стіною. Скільки пар кроликів народиться при цьому протягом року, якщо природа кроликів така, що кожний місяць, починаючи з третього місяця після свого народження, пара кроликів породжує іншу пару?

Спосіб 1

Кожне наступне знаходити як суму двох попередніх.

1 1 2 3 5 8 ...

k1 перше число

k2 друге число

k3:=k1+k2;

k1:=k2;

k2:=k3;

program pr4 (іnput,output);

uses crt;

var

    k1,k2,k3,n:longіnt;

begіn

clrscr;

k1:=1;k2:=1;

for n:=3 to 12 do begіn

k3:=k1+k2;

k1:=k2;

k2:=k3;

end;

wrіte('n',k3);

end.

Спосіб 2

Використаємо рекурентну формулу  чисел Фібоначі.

Кожне число Фібоначі знаходять за формулою:

n=12

program pr5;

const n=12;

var

f1,f2:real;

f:longіnt;

begіn

f1:=exp(n*ln((1+sqrt(5))/2));

f2:=(exp(n*ln(abs(1-sqrt(5))/2)));

іf odd(n) then f:=round(1/sqrt(5)*(f1-f2)) else f:=round(1/sqrt(5)*(f1+f2));

wrіteln(f);

end.

 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

Приклади задач

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

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

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

5. Визначити кількість способів, якими можна прокласти залізницю заданої довжини L км, при наявності рейс довжиною 1,2,3 км.

Задача 6 «Зернинки»

Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.

Задача 7 «ПОДАРУНОК ДЛЯ МУДРОЇ СОВИ»

П'ятачок і Вінні-Пух зібрались до Мудрої Сови на день народження. Для подарунка вирішили назбира­ти букет польових ромашок. Ромашкове поле задане прямокутною матрицею M N, у клітинках якої за­писано кількість ромашок, що ростуть на відповідно­му клаптику поля. Будь-який клаптик поля містить хоча б одну ромашку.

П'ятачок і Вінні-Пух вміють ходити лише по гори­зонталі і вертикалі, при цьому, зробивши хід на схід, уже не можна буде потім ходити на захід і навпаки, а також, зробивши хід на північ не можна буде ходити на південь і навпаки. У початковий момент гості Му­дрої Сови знаходяться в центральній клітинці поля.

Напишіть програму, що допоможе вказати напря­мок руху: NW — північний захід, NE — північний схід, SW— південний захід, SE — південний схід, та визначте при цьому найбільшу можливу кількість ромашок у букеті.

Технічні умови:

У першому рядку вхідного текстового файла owl.dat записано через пропуск два цілих непарних чи­сла: М і N (2<М, N<100).

У наступних М рядках записано по N чисел у ко­жному, розділених пропуском. Кожне з чисел не пе­ревищує 10000.

Ваша програма повинна вивести у файл owl.sol напрямок руху у вигляді: NW — північний захід, NE — північний схід, SW — південний захід, SE — південний схід. Та через пропуск у відповідному ря­дку кількість ромашок. Якщо таких напрямків буде більше одного, то вивести всі від NW за годинниковою стрілкою.

Приклад 1.

owl.dat                                owl.sol

3  3                                     NE 7

1 2 З

3 2 1

1 1 1

Приклад 2.

owl.dat                                owl.sol

3   5                                    NW 7

1  2  1  2  1                   NE    7

3   2  1  2   3                    SE    7

1 1 3  1  1                   SW  7

Алгоритм Флойда-Уоршелла

З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вершин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. Питання лише в часі виконання такого алгоритму, оскільки його оцінка буде О(п³). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Запишемо сам алгоритм:

1, Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.

2. Визначити вершину і = 1.
 3. Визначити вершину j = 1,

4.   Якщо величина d_{j, k} + d_k,j менша за значення d_i,j ,то замінити значення  d_i,j на d_{i, k} + d_k,і . В іншому разі залишити зна­чення  d_i,j без змін.

5.   Якщо j <= п, то перейти до наступної вершини j+ 1 і повер­нутися до п. 4.

6.   Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

7.   Якщо k<=n,  то перейти до наступної вершини k + 1 і повер­нутися до п. 2,

8.   Завершити алгоритм.

У результаті виконання алгоритму елементи  d_i,j будуть міс­тити найкоротшу відстань між відповідними вершинами графа і та j.

Реалізація алгоритму Флойда-Уоршелла мовою Pascal буде такою:

for k := 1 to n do

for і := 1 to n do

for j := 1 to n do

if d[i,k]+d[k,j]k]+d[k,j];