|
Динамічне програмування
Аналогічний приклад можна навести і на більш складніший числовий ряд чисел Фібоначі.
Задача 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 «Зернинки»
Мишка збирає зернинки на шаховій дошці. Може рухатись вниз та вліво. Зібрати найбільше зернинок.
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
|
2
|
1
|
0
|
8
|
4
|
1
|
4
|
9
|
6
|
1
|
|
2
|
3
|
3
|
12
|
16
|
17
|
20
|
30
|
36
|
|
2
|
|
6
|
2
|
5
|
7
|
3
|
2
|
10
|
1
|
3
|
2
|
|
8
|
10
|
15
|
22
|
25
|
27
|
37
|
37
|
40
|
|
3
|
|
2
|
8
|
6
|
6
|
6
|
6
|
8
|
5
|
8
|
3
|
|
10
|
17
|
24
|
30
|
35
|
41
|
49
|
55
|
62
|
|
4
|
|
5
|
9
|
5
|
9
|
6
|
6
|
4
|
6
|
9
|
4
|
|
15
|
26
|
31
|
41
|
47
|
53
|
57
|
63
|
72
|
|
5
|
|
7
|
4
|
6
|
7
|
3
|
5
|
8
|
4
|
1
|
5
|
|
21
|
30
|
38
|
48
|
51
|
58
|
66
|
71
|
73
|
|
6
|
|
2
|
5
|
4
|
9
|
4
|
5
|
5
|
4
|
10
|
6
|
|
24
|
35
|
41
|
56
|
60
|
66
|
72
|
75
|
85
|
|
7
|
|
4
|
3
|
8
|
1
|
0
|
6
|
6
|
9
|
4
|
7
|
|
28
|
39
|
49
|
58
|
61
|
71
|
77
|
87
|
91
|
|
8
|
|
4
|
3
|
7
|
8
|
8
|
9
|
5
|
9
|
1
|
8
|
|
32
|
42
|
57
|
65
|
74
|
83
|
89
|
98
|
99
|
|
9
|
|
2
|
5
|
2
|
2
|
2
|
1
|
6
|
7
|
6
|
9
|
|
34
|
47
|
59
|
68
|
76
|
84
|
95
|
105
|
110
|
|
10
|
|
10
|
1
|
6
|
2
|
10
|
7
|
4
|
5
|
3
|
10
|
|
44
|
48
|
65
|
69
|
86
|
93
|
99
|
110
|
113
|
Задача 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
Алгоритм Флойда-Уоршелла
З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вершин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. Питання лише в часі виконання такого алгоритму, оскільки його оцінка буде О(п3). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.
Запишемо сам алгоритм:
1, Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.
2. Визначити вершину і = 1.
3. Визначити вершину j = 1,
4. Якщо величина dj, k + dk,j менша за значення di,j ,то замінити значення di,j на di, k + dk,і . В іншому разі залишити значення di,j без змін.
5. Якщо j <= п, то перейти до наступної вершини j+ 1 і повернутися до п. 4.
6. Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.
7. Якщо k<=n, то перейти до наступної вершини k + 1 і повернутися до п. 2,
8. Завершити алгоритм.
У результаті виконання алгоритму елементи di,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];
|
4
0 20 3 2
20 0 40 3
3 40 0 4
2 3 4 0
|
0 5 3 2
5 0 7 3
3 7 0 4
2 3 4 0
|
|
0 20 3 2
20 0 40 3
3 40 0 4
2 3 4 0
|
0 20 3 2
20 0 23 3
3 40 0 4
2 3 4 0
|
0 20 3 2
20 0 23 3
3 23 0 4
2 3 4 0
|
0 5 3 2
20 0 23 3
3 23 0 4
2 3 4 0
|
0 5 3 2
5 0 23 3
3 23 0 4
2 3 4 0
|
0 5 3 2
5 0 7 3
3 23 0 4
2 3 4 0
|
0 5 3 2
5 0 7 3
3 7 0 4
2 3 4 0
|
|
