[Rekurencja] Funkcja rekurencyjna, ilość porównań

[kejkun7]

Dana jest liczba naturalna \(\displaystyle{ n>0}\) i tablica różnych liczb całkowitych \(\displaystyle{ a[1..n]}\) . Rozważamy
następującą rekurencyjną funkcję F z argumentem i będącym liczbą naturalną, \(\displaystyle{ 1 \le i \le n}\)
Funkcja \(\displaystyle{ f(i)}\)
jeżeli \(\displaystyle{ i=n}\) to
wynikiem jest \(\displaystyle{ n}\)
w przeciwnym razie
\(\displaystyle{ j:=F(i+1)}\)
jeżeli \(\displaystyle{ a <a[j]}\) wtedy
wynikiem jest \(\displaystyle{ i}\)
w przeciwnym razie
wynikiem jest \(\displaystyle{ j}\)
\(\displaystyle{ a[5,1,8,9,7, 2,3,11, 20,15]}\)
c )
Ile porównań między elementami tablicy zostanie wykonanych przy wywołaniu\(\displaystyle{ f(512)}\)
dla \(\displaystyle{ n = 2012}\) ?

[dexter90]

Do kiedy będzie wykonywany proces porównywania??

[kejkun7]

przepraszam, ale to już całe polecenie : (
odpowiedź to \(\displaystyle{ 1500}\)

[dexter90]

Hehe, ja Tobie zadałem pytanie, odpowiedz mi na nie. Odpowiedź to ja znam

[kejkun7]

to jak mam być szczery to nie czaję tego : P .


"Do kiedy będzie wykonywany proces porównywania??"
no pewnie do otrzymania wyniku ;x hmm ?

ale nie czaję skąd taka odpowiedź jak ja tu widze jedno porównanie między elementami
\(\displaystyle{ a < a[j]}\) ; x ?

[dexter90]

Proces porównywania będzie do momentu, kiedy \(\displaystyle{ i != n}\), w każdej operacji \(\displaystyle{ i}\) zwiększa się o 1, obecnie \(\displaystyle{ i=512 \ n=2012}\), musi się odbyć 1500 operacji,wywołań,iteracji aby \(\displaystyle{ i==n}\).

[kejkun7]

łoł..
poprosiłbym o wyjaśnienie
\(\displaystyle{ i!}\)
czyli : \(\displaystyle{ 512 ! = n}\)
czyli \(\displaystyle{ 512 ! = 2012}\)
ee ?

nie czaję , jak \(\displaystyle{ 512 !}\) to w huk dużo

Proces porównywania nic nie ma wspólnego z poprzednią formułą, tylko o to chodzi
aby doszło do momentu kiedy
\(\displaystyle{ i = n}\)
tak : ) ?
to czaję : )
\(\displaystyle{ i = 512 n = 512 * 2012}\) hmm ?

zawsze się dodaję w takich wypadkach po \(\displaystyle{ 1}\) hmm ?

[dexter90]

W informatyce, niemal każdym ( no w FORTRANIE można inaczej zapisać ), wyrażenie \(\displaystyle{ !=}\) oznacza "różne".

Odnośnie pytania, proces porównywania w naszej treści jest pewnego rodzaju "stopem", pytają "kiedy program przestaje porównywać liczby"? Ty patrzysz na kodu i widzisz:

\(\displaystyle{ F(i) \ if(i==n) \ return \ n;}\)

No wtedy kiedy nasze \(\displaystyle{ i}\) ( obecnie 512 ) osiągnie wartość \(\displaystyle{ n}\) czyli 2012.

//EDIT:

Nie zawsze, w zadaniu masz, że jeżeli \(\displaystyle{ i!=n}\) to funkcja \(\displaystyle{ F()}\) przyjmuje argument o +1 większy.