Olimpiade Sains Provinsi (OSP) 2012 - Komputer, Nomor 29–30

29. F5(4) dieksekusi 5 kali

30. membentuk deret fibonacci

f(8)=1

f(7)=1

f(6)=2

f(5)=3

f(4)=5

f(n-k)=banyaknya eksekusi f(n-k+1)+banyaknya eksekusi f(n-k+2)

kita misalkan g(n-k) fungsi untuk menghitung banyak eksekusi f(n-k) pada f(n). untuk n-k < 0 kita anggap g(n-k) = 0

mari kita analisa polanya:

f(7) -> f(6) + f(5)=13

f(6) -> f(5) + f(4)=8

f(5) -> f(4) + f(3) =5

f(4) ->f(3)+f(2) = 3

f(3)->f(2)+f(1) = 2

misalkan n=7 k=5 maka yg kita cari adalah banyaknya f(2): 

banyak f(n-k) pada f(x) adalah (banyak f(n-k) pada f(x-1)) + (banyak f(n-k) pada f(x-2))

f(x)        banyak eksekusi:    f(2)                            f(3)

f(1)                                      0                                 0

f(2)                                      1                                              0

f(3)             f(2) + f(1)        g(3-2) = 0+1  = 1                      g(3-3) = g(0) = 1 = f(1) 

f(4)             f(3) + f(2)        g(4-2) = 1+1= 2                        g(4-3) = g(1) = 1 = f(2)

f(5)             f(4) + f(3)        g(5-2) = 1+ 2 = 3                      g(5-3) = g(2) = 2 = f(3)

f(6)              f(5) + f(4)       g(6-2) = 2+3 = 5                       g(6-3) = g(3) = 3 = f(4)

f(7)              f(6) + f(5)       g(7-2) = 3+5=8                         g(7-3) = g(4) = 5 = f(5)

atau dengan kata lain bisa kita sederhanakan persamaannya, kita dapat menyimpulkan g(n-k) = f(k+1)