Jak zapisywać algorytmy rekurencyjne w sposób iteracyjny
Jeśli chodzi o przykłady to można wziąć
Sortowanie przez kopcowanie (wersja umieszczona w książce Cormena)
Sortowanie przez scalanie
Sortowanie przez podział (tzw szybkie)
Wieże Hanoi
Zapisywanie algorytmów rekurencyjnych w sposób iteracyjny
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Rozkręcam się
- Posty: 39
- Rejestracja: 24 maja 2016, 11:44
- Otrzymane podziękowania: 9 razy
- Płeć:
Algorytm rekurencyjny można zaimplementować nie zapisując wprost wołania funkcji przez samą siebie. Np. algorytm sprawdzania, czy liczba znajduje się w posortowanej tablicy metodą połowienia w języku C może wyglądać tak:
lub tak:
Ten kod napisałem na szybko bez uruchomienia i przetestowania, na pewno ma bugi, ale chodzi mi o pokazanie idei.
W przypadku bardziej złożonych algorytmów zrezygnowanie z rekurencji jest o wiele trudniejsze, ponieważ w każdym wywołaniu funkcja rekurencyjna woła samą siebie kilka razy. Jednym ze sposobów byłoby manualne zaimplementowanie stosu rekurencji. W tym celu należałoby zadeklarować strukturę zawierającą wszystkie dane podproblemu. Następnie tworzymy stos obiektów tej struktury i umieszczamy na nim jeden obiekt opisujący wejściowy problem. Następnie kręcimy się w pętli while, dopóki stos nie będzie pusty. W każdej iteracji pętli pobieramy i przetwarzamy element ze stosu. Jeśli rozwiązanie wymaga rozwiązania podproblemów, to umieszczamy je na stosie.
Czy odpowiedziałem na twoje pytanie? W razie czego dopytuj śmiało
Kod: Zaznacz cały
int exists (int *array, int N, int element)
{
if (N == 1)
{
return (array[0] == element);
}
else if (array[N/2] >= element)
{
return exists (array, N/2);
}
else
{
return exists (array + N/2, N/2);
}
}
Kod: Zaznacz cały
int exists (int *array, int N, int element)
{
int left = 0, right = N-1;
while (left != right)
{
int center = (left + right) / 2;
if ( array[center] >= element )
{
right = center;
}
else
{
left = center;
}
}
return (array [left] == element)
}
W przypadku bardziej złożonych algorytmów zrezygnowanie z rekurencji jest o wiele trudniejsze, ponieważ w każdym wywołaniu funkcja rekurencyjna woła samą siebie kilka razy. Jednym ze sposobów byłoby manualne zaimplementowanie stosu rekurencji. W tym celu należałoby zadeklarować strukturę zawierającą wszystkie dane podproblemu. Następnie tworzymy stos obiektów tej struktury i umieszczamy na nim jeden obiekt opisujący wejściowy problem. Następnie kręcimy się w pętli while, dopóki stos nie będzie pusty. W każdej iteracji pętli pobieramy i przetwarzamy element ze stosu. Jeśli rozwiązanie wymaga rozwiązania podproblemów, to umieszczamy je na stosie.
Czy odpowiedziałem na twoje pytanie? W razie czego dopytuj śmiało
Matematyka: Generator zadań - darmowa apka dla Androida generuje losowe zadania i pokazuje pełne rozwiązania
-
- Czasem tu bywam
- Posty: 149
- Rejestracja: 30 wrz 2012, 20:36
- Podziękowania: 2 razy
- Otrzymane podziękowania: 13 razy
- Płeć:
Re: Zapisywanie algorytmów rekurencyjnych w sposób iteracyjn
Kod: Zaznacz cały
const maxA=1000;
type TElem=integer;
TArray=array[1..maxA]of TElem;
procedure heapify(var A:TArray;i,heapsize:integer);
var left,right,largest:integer;
temp:TElem;
begin
left:=2*i;
right:=2*i+1;
if((left<=heapsize)and(A[left]>A[i])) then
largest:=left
else
largest:=i;
if((right<=heapsize)and(A[right]>A[largest])) then
largest:=right;
if(largest<>i)then
begin
temp:=A[i];
A[i]:=A[largest];
A[largest]:=temp;
heapify(A,largest,heapsize);
end;
end;
Jak zamienić ją na iterację bez żadnych instrukcji break i innych goto