zadanie z funkcji Arek: Witam, Czy jest tu ktoś tak dobry i będzie w stanie mi pomóc z tym zadaniem ,bo ja już nie daje rady Do każdego z tych pod punktów trzeba zaznaczyć odpowiedz tak lub nie. Do obliczanie wartości funkcji f : N₀ → N₀,f(n) = {n, dla n<2 {f(n−2) +2f(n−1) + n² dla n≥2 dysponujemy funkcja rekurencyjna opartą wprost na definicji.Ilerazy będzie ona wołana do obliczenia f(b) podczas wywołania do obliczenia f(a)? Wskazać zdania prawdziwe. A) Jeśli a = 5,b = 2 to będą 3 wywołania. odpowiedz tak lub nie B) Jeśli a = 6,b = 2 to będzie 8 wywołań. odpowiedz tak lub nie C) Jeśli a = 16,b = 6 to będzie 55 wywołań. odpowiedz tak lub nie Bardzo proszę o pomoc

Arek: bump

Arek: ?

Pytający: g:ℕ₀²→ℕ₀ g(a,b) − liczba wywołań f(b) podczas wywołania f(a) • Oczywiście g(a,b)=0 dla a<2 ⋁ a−b≤0. // dla a<2 nie ma wywołań rekurencyjnych // zmniejszamy zmienną w wywołaniach, więc nie ma wywołań dla a≤b • Dla a≥2 ∧ (a−2=b ∨ a−1=b) mamy g(a,b)=1+g(a−1,b)+g(a−2,b). // dla a≥2 ∧ (a−2=b ∨ a−1=b) wywołując f(a) wywołujemy jednokrotnie f(a−1) oraz jednokrotnie f(a−2), zatem f(b) będzie tu wywołane raz + tyle razy, ile w wywołaniach f(a−1) i f(a−2) • Dla a≥2 ∧ a−b>2 mamy g(a,b)=g(a−1,b)+g(a−2,b). // dla a≥2 ∧ a−2>b wywołując f(a) wywołujemy jednokrotnie f(a−1) oraz jednokrotnie f(a−2), zatem f(b) będzie tu wywołane tyle razy, ile w wywołaniach f(a−1) i f(a−2) Mamy coś takiego: b\a|0 1 2 3 4 5 6 −−−−−−−−−−−−− 0 |0 0 1 1 2 3 5 1 |0 0 1 2 3 5 8 2 |0 0 0 1 2 3 5 3 |0 0 0 0 1 2 3 4 |0 0 0 0 0 1 2 5 |0 0 0 0 0 0 1 Jak łatwo zauważyć: g(a,b)=F_a−b+1 dla 1≤b<a, gdzie F_n to n−ty wyraz ciągu Fibonacciego https://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego a) tak b) nie c) nie

Arek: Dziękuje bardzo