Jak (Poprawnie) zapisać to równanie rekursją?

Question

Cześć.

Uczę się na studiach języka c++ i dostaliśmy zadanie rozwiązania rekursją tego równania:

Mam napisać procedurę rekurencyjną, gdzie jedynym parametrem jest X (Cn na obrazku).

Bez bicia przyznaję, że rekurencja to nie jest moja mocna strona. Napisałem coś takiego:

#include <iostream>

using namespace std;

int c(int x)
{
    if(x == 1) return 1;
    else return c(0.5*x) - 0.25*c(5*x+2)*c(((-1)^x)-1);

}

int main()
{
    cout << "Hello world!" << endl;
    int x;
    cin>>x;
    c(x);
    return 0;
}

Jeśli Ktoś byłby w stanie mi pomóc zrozumieć rekurencję w c++ byłbym wdzięczny :)

Dziękuję.

Answer 1

pierwsze wyołanie: szukasz c(n/2) a nie 1/2 c(n) drugie wywołanie to samo szukasz c(5n + 2) amiast 5c(n)+2 i ostatnie szukasz c((-1)^n -1) z nie (-1)^c(n)-1.

Reukrencja polega na tym, że funkcja aby osiągnąć cel wywołuje samą siebie z innym argumentem. U Ciebie tok rozumowania jest w miarę poprawny ale gubisz się w argumencie. Spróbuj na początku zadawać sobie pytania biorę połowę wartości c(n) czy funkcję dla dwa razy mniejszego argumentu. to samo w drugim przypadku a w trzecim -1 musisz podnieść do wartości c(n). Ciężko to wytłumaczyć a nie chcę podawać gotowego rozwiązania. Spróbuj pomyśleć na tym i pisz w komentarzu co zmieniłeś, a ja będe naprowadzał dalej.

Jeszcze warunek w if'ie może być potencjalnie problematyczny, co jeśli użytkownik poda liczbę ujemną? Program będzie się wykonywał w nieskończoność czego nie chcemy więc ja bym zmienił warunekna '<='.

Comments

using namespace std;

int c(int x)
{
    if(x == 1) return 1;
    else return c(x/2) - 0.25* (5*c(x) + 2) * ((-1)^c(x)-1);

}

Nadal chyba nie rozumiem :(

Funkcja cały czas wywołuje się od tego samego 'x' tylko za każdym razem ten 'x' ma się zmniejszyć tak? W którym momencie tak naprawde powinno się umiesczać rekurencję? Np: dla silni używa się "n*silnia(n-1)" i tutaj następuje dekrementacja w każdym wywołaniu (silnia(n-1). Czy w moim przypadku to ma się dziać w wywołaniu "c(x/2)" ?

---

W twoim przypadku jest anaogicznie jak w silni czyli w argumenicie masz c(x-1) ale dalej jest błąd w pierwszym wywołaniu. A dwa pozostałe zrobiłeś dobrze tylko zmień argument na x-1.

---

Jeśli dobrze rozumiem, pierwsze wywołanie to c(x/2) tak?
Rozumiem dlaczego zmniejszam za każdym razem.
Zmieniłem (co prawda niewiele:

 else return (c(x-1)/2) - 0.25 * c(5*(x-1)+2) - c((-1)^(x-1) - 1);

Tylko nadal program po wprowadzeniu 'x' chwile "mieli" poczym zwraca minus ileś milionów. rozumiem, że przerywa się sam i stąd ten wynik?

 

---

No właśnie nie. We wzorze masz 0,5 cn czyli bierzesz połowę z otrzymanej wartości a nie wysyłasz dwa razy mniejszy argument. Argument musi być o jeden mniejszy bo tak zdefiniowany jest ten ciąg. Wróciłeś do pierwotnej błędnej formuły, druga przez Ciebie zaproponowana była dobra dla drugiego i trzeciego wywołania(nie licząc x zamiast x-1 w argumencie), a ta jest zła dla wszystkich.

EDIT: Mam jakiś problem z wyświetlaniem okna z kodem. Napisałeś kod poprawnie dla pierwszego argumentu ale pozostałe są z pierwszej wersji, która jest błędna, druga była poprawna dla drugiego i trzeciego. Nie rozumiem jednego: fragment kodu jest napisany poprawnie ale w komentarzu napisałeś o tym błędnie ma być c(x-1) jak w kodzie a nie c(x/2) jak w komentarzu.

---

int c(int x)
{
    if(x == 1) return 1;
    else return (c(x-1)/2) - 0.25* (5*c(x-1) + 2) * ((-1)^c(x-1)-1);

}

Dziękuję :) Nie wywala. Jeszcze mam pytanie, jak mogę wypisać na ekreanie kolejne obliczone wartości 'x'?

Funkcja za każdym razem "schodzi" do 1 i wtedy zwraca mi 1 tak jak w warunku.

---

Najprościej zrobić w klauzuli else dodatkową zmienną.

else {
    int wynik = c(x-1)/2 - 0,25*(5*c(x-1)+2) * ((-1)^c(x-1)-1);
    cout << wynik << endl;
    return wynik;
}

Jak już opanujesz rekurencję to zainteresuj się programowaniem dynamicznym. W skrócie polega to na tym, że zapamiętujesz wyniki dla poszczególnych x-ów i nie wywołujesz funkcji kilkakrotnie dla tej samej wartości. Zastosowanie programowania dynamicznego może znacznie przyspieszyć Twój program. Może dla tak małych programów to nie ma znaczenia ale dla większych projektów przyspieszenie programu trzykrotnie może dać dużo. Ale najpierw musisz porządnie opanować rekurencję.

---

Dziękuję Ci serdecznie :)

Wszystko śmiga jak należy ^^