Динамічне програмування Печать
Добавил(а) Вчитель   
05.11.10 12:04

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

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

 

Задача 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