Zadanie z matury 2012 maj

Question

Witam! Mam taki jeden malutki problem jeśli chodzi o zadanie z matury z maja 2012 roku.

Treść brzmi tak:

 

Zadanie 1.

Dana jest liczba naturalna n>0 i tablica o różnych liczbach całkowitych a[1..n]. Rozważmy następującą rekurencyjną funkcję F z argumentem i będącym liczbą naturalną 1<=i<=n.

Funkcja F(i)

 jeżeli i=n to

   wynikiem jest n

w przeciwnym razie

  j:=F(i+1)

  jeżeli a[i]<a[j] wtedy

     wynikiem jest i

  w przeciwnym razie

    wynikiem jest j

 

a) Dla danej 10-elementowej tablicy a=[5,1,8,9,7,2,3,11,20,15] podaj wynik wywołania funkcji F dla argumentu i.

i = 9; F(i) =?

i = 7; F(i) = ?

i = 5; F(i) = ?

 

Ogólnie to tak, zrobiłem to zadanie. Dla i=9 wyszło mi 10, dla i=7 wyszło mi 7 a dla i=5 wyszło mi 6.

Problem w tym, że później jest takie zadanie:

c) Ile porównan między elementami tablicy zostanie wykonanych przy wywołaniu F(512) dla n=2012?

No to patrząc na ten algorytm na górze to uznałem, że ilość powtórzen to bedzie 2012-512 czyli 1500.

Problem w tym, że tamto zadanie z podpunktu a robilem na jednym porównaniu a nie na kilku tj.

dla i = 9  zrobilem tak:

czy i=n? Nie, więc j=F(9+1)

Czy a[9] < a[10]? Czyli czy 20 < 15? Nie, więc wynikiem jest j = 10.

 

Ale rozwaliła mnie ta ilość powtórzeń w podpunkcie c. Ktoś podpowie jak rozwiązać zadanie z podpunktu a stosując się do tego, że tutaj są jakieś ilości powtórzeń tak jak w podpunkcie c?

Answer 1

Przykładowa realizacja dla i=7;

1. i nie jest równe n więc idziemy dalej

2. j=f(8)

3. a[7](w tym przypadku trójka)<a[f(8)] zwróć i; Jeżeli nie zwróć j;

3.1 ---> f(8)

3.2 ---> j=f(9)

3.3 ---> a[8](w tym przypadku 11)<a[f(9)] zwróć i; Jeżeli nie zwróć j;

3.3.1 ---> f(9)

3.3.2 ---> j=f(10)

3.3.3 ---> a[9](w tym przypadku 20]<a[f(10)] zwróć i; Jeżeli nie zwróć j;

3.3.3.1 ---> f(10)=10

I teraz cofamy bo mamy już konkretną wartość: 

(a[9]=20)<a[10]=15) ---> zwraca j czyli 10;

(a[8]=11<a[10]=15) ---> zwraca i czyli 8;

(a[7]=3<a[8]=11) ---> zwraca i czyli 7;

 

Im mniejsze i tym więcej porównań, zresztą jak sam zauważyłeś n-i;

 

Comments

Rozumiem, że znajdujemy już to, że i==n, czyli 10.

Tylko nie rozumiem, dlaczego jak już przyrównamy i do n to cofamy się w tych warunkach z tablicami?

---

Tak działa funkcja rekurencyjna. Żeby obliczyć f(9) potrzebujesz f(10).

Jeżeli f(6) to potrzebujesz f(7) czyli f(8) czyli f(9) czyli f(10).

Mając f(10), która zwraca konkretną wartość jesteś w stanie policzyć f(9) co za tym idzie f(8) i tak w dół.

---

Dziękuję bardzo za wyjaśnienie :D

Teraz już wszystko stało się jasne.