Programowanie dynamiczne

Odpowiedz Nowy wątek
2012-08-21 12:21
0

Jak rozwiązać takie zadanie:
zadanie_algo.jpg

Z tego co wiem podczas programowania dynamicznego powinno się zapisywać wszystkie wyniki np. w tablicy, ale nie wiem jak to powinno wyglądać w pseudokodzie, i jak obliczyć złożoność algorytmiczną ?

Pseudokod który napisałem bez użycia tablicy wygląda następująco :

F(n,k)

if k=0
  return 1
if n=0 i k>0
  return 2*k
else 
  return F(n,k-1)+F(n-1,k)

Jak należy go zmienić aby był wykonany za pomocą metody programowania dynamicznego ?


"I have no details because sometimes I feel lost, in my code."

Pozostało 580 znaków

2012-08-21 12:38
1

Należy pomyśleć. Zrób sobie tablicę gdzie będziesz przechowywał wartości f(x,y) i licz tą tablicę od początku. Następnie w pętli zamiast liczyć na pałę wszystkie współczynniki potrzebne do wyliczenia f(k,n) zrobisz po prostu
tablica[n,k-1]+tablica[n-1,k]


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-08-21 13:06
0
F(n,k)

if k=0
  return T[n,k]<-1
if n=0 i k>0
  return T[n,k]<-(2*k)
else 
  return T[n,k-1]+T[n-1,k]

W ten sposób ?


"I have no details because sometimes I feel lost, in my code."

Pozostało 580 znaków

2012-08-21 13:38
0

Tak. W ten właśnie sposób :)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2012-08-21 13:54
0

Ok, dzięki za pomoc :) A jak obliczyć teraz złożoność takiego algorytmu?


"I have no details because sometimes I feel lost, in my code."

Pozostało 580 znaków

2012-08-21 14:02

Bardzo prosto. Policz ile operacji musisz wykonać żeby wyliczyć f(n,k). Łatwo zauważyć że aby wyliczyć f(n,k) wystarczy ci jedno przejście przez tablicę, więc złożoność to O(n*k)


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
@Shalom: szybkie pytanie o algorytmy dynamiczne, bo robie sobie przypomnienie po wielu latach przerwy. Czy to sie z grubsza sprowadza do tego ze jak problem ma odpowiednia podstrukture i da sie go opisac funkcja rekurencyjna to potem jak w przykladzie z tego watku z grubsza zamienia sie na tablice i koniec ? Czy sa jakies "haczyki" ? - WhiteLightning 2019-06-01 23:33
Hmm no niekoniecznie da się opisać rekurencyjnie i nie chodzi o zamianę na tablicę :D Jeśli problem na własność optymalnej podstruktury to znaczy że znając optymalne rozwiązanie problemu mniejszego, można je wykorzystać do konstrukcji rozwiązania problemu większego. I tyle. - Shalom 2019-06-01 23:58

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0