[Rekurencja] Funkcja rekurencyjna, zapis iteracyjny

[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]}\)

zapisz podaną funkcję iteracyjnię

nie podoba mi się odpowiedź, ale może to z tego wynika, że ja czegoś nie rozumiem : P
jest ona taka :
1. \(\displaystyle{ ind_min := n}\)
2. jeśli \(\displaystyle{ i = n}\)przejdź do kroku 4
3. od \(\displaystyle{ k = n–1}\) do \(\displaystyle{ i}\)
jeśli \(\displaystyle{ a[k] < a[ind_min]}\) to\(\displaystyle{ ind_min:=k}\)
4. wypisz \(\displaystyle{ ind_min}\)

po 1. po co w 1 jest napisane \(\displaystyle{ ind_min := n}\)
sądzę, że równie dobrze mogłoby zostać samo \(\displaystyle{ n}\)
2. \(\displaystyle{ n = 10}\)


sprawdźmy zachowanie kodu dla \(\displaystyle{ i = 8}\)


1. \(\displaystyle{ ind_min := n = 10}\)
2. jeśli \(\displaystyle{ 10 \neq 8}\)przejdź do kroku 4
3. od \(\displaystyle{ k = n–1 = 9}\) do \(\displaystyle{ i = 8}\)
od kiedy robi się coś od \(\displaystyle{ 9}\) do\(\displaystyle{ 8}\)
?? trochę jakoś na odwrót powinno być , co nie ?
czy po prostu zbadać dla \(\displaystyle{ 8}\) i \(\displaystyle{ 9}\) hmm ?

jeśli \(\displaystyle{ a[9] < a[10]
\(\displaystyle{ 20 < 15}\)
to\(\displaystyle{ ind_min:=9}\)
4. wypisz \(\displaystyle{ 9}\)

czy mogłoby to tak wyglądać ? :


1. jeśli \(\displaystyle{ i = n}\)przejdź do kroku 3
2. od \(\displaystyle{ k = n–1}\) do \(\displaystyle{ i}\)
jeśli \(\displaystyle{ a[k] < a[n]}\) to\(\displaystyle{ n:=k}\)
3. wypisz \(\displaystyle{ n}\)


sprawdźmy zachowanie kodu dla \(\displaystyle{ i = 8}\)

1. jeśli \(\displaystyle{ 10 \neq 8}\)przejdź do kroku 3
2. od \(\displaystyle{ k = 9}\) do \(\displaystyle{ 8}\) znów jak to rozumieć hmm ?
sprawdzamy najpierw dla \(\displaystyle{ k = 9}\) a potem dla \(\displaystyle{ k = 8}\)
hmm ?

jeśli \(\displaystyle{ a[9] < a[10]}\)
\(\displaystyle{ 20 < 15}\)
to\(\displaystyle{ n:=k}\)\(\displaystyle{ 10:=9}\)
3. wypisz \(\displaystyle{ n}\)\(\displaystyle{ 10}\)

ale dla \(\displaystyle{ k = 8}\)
jeśli \(\displaystyle{ a[8] < a[10]}\)
\(\displaystyle{ 11< 15}\)
\(\displaystyle{ 9}\)

i wtedy wyniki się różnią hmm..}\)

[dexter90]

Tyle tego napisałeś, że sam nie wiem od czego zacząć. Nie trzymaj się ściśle odpowiedzi bo też nie o to chodzi. W algorytmice ważna jest poprawność, nazewnictwo to kwestia kosmetyki ( w dużych projektach ekstramalnie ważna rzecz ).

Ja bym Ci na samym początku poradził nauke schematów blokowych i pseudokodów, to zadanie zostaw sobie na później. Widzę, że robisz cały czas to zadania, a ten przykład jest najlepszym momentem, aby zachaczyć o ważne aspekty w/w.

[kejkun7]

to może napiszę po swojemu powiesz mi co źle ;x ?

Kod: Zaznacz cały

1. 
 begin 
 if  i = n 

go to step # 4 
 else  
go to step #2


2.  j : = i  + 1 

3.
  if \
a [i ]  < a [ j ]\  


go to step # 4


  \ else 
 go to step #5
4.  write   i  

 end. 


5.  write   j  

 end. 

[dexter90]

Teraz to bardziej przypomina maszynę ram, ale na upartego ujdzie.

[kejkun7]

to trochę nie czaję,
bo polecenie brzmiało

"zapisz iteracyjnie "

iteracja to powtórzenie, a w moim kodzie jakby nigdzie nie używam ;x ?
ale mówisz, że w porządku ?
to dzięki : )

[dexter90]

U nich widzę "prowizoryczną pętle?", ale sensu jej nie widzę, skoro w pamięci mamy zapisaną przykładową tablice j/w.

Pozdrawiam.

[ksisquare]

Kod: Zaznacz cały

if( i==n) {
	// 4.
} else {
	j=i+1
	if( a[i]<a[j] )
		;
	else
		i tu logika umyka

[dexter90]

Zgadza się, przeoczyłem. Przepraszam za błędy, ale 12 godzin przed komputerem robi swoje. Pytania kierować na PW.