[C][C++]Obliczanie n-tego wyrazu ciągu według podanego wzoru

[radzym94]

Witam, mam następujący problem.
Mamy dany wzór na obliczanie elementów ciągu.

\(\displaystyle{ C_{n+1}= \frac{1}{2} \cdot C_{n}- \frac{1}{4} \left( 5 C_{n}+2 \right) \left( \left( -1 \right) ^{C_{n}}-1 \right)}\) i tak np dla \(\displaystyle{ C_0=11}\) mamy:

\(\displaystyle{ 11,34,17,52,26,13,40,20,10,5,16,8,4,2,1}\).
Zawsze ostatnim elementem jest \(\displaystyle{ 1}\).

Zadanie brzmi: Napisz procedure rekurencyjna c(x,n), która dla podanego argumentu całkowitego \(\displaystyle{ x>0}\) oblicza jego n-ty wyraz ciagu i wypisuje na ekranie. (Ciąg ten zaczyna się od \(\displaystyle{ x}\) a kończy na \(\displaystyle{ 1}\))

Napisałem narazie taki kod procedury:

Kod: Zaznacz cały

void c(int x, int n)
{
	if (x > 0)
	{
		if (x != 1) 
                  {
			for (int i = 0; i < n - 1; i++)
			{
				x = (0.5*x) - 0.25*(5 * x + 2)*(pow(-1, x) - 1);

			         if (i == n - 2){ cout << x << endl;   }
			}
	           }

		else cout << x << endl;
	}
}
main()
{
c(11,5);
}

Jak widać , funkcja działa poprawnie, jednak nie ma ona wymaganej rekurencji. Czy ktoś mógłby zatem mi pomóc w zrobieniu jej? Nie bardzo wiem jak w tym przypadku mam to wykonać, więc każda podpowiedź będzie pomocna. Z góry dziękuję za pomoc, i pozdrawiam

[Gouranga]

Kod: Zaznacz cały

int c(int x, int n){
  if (n==1){
    return x;
  } else {
    int cn = c(x, n-1);
    int znak = cn % 2 == 0 ? 1 : -1;
    return (int)(0.5 * cn - 0.25 * (5*cn+2)*(znak-1));
  }
}

potem wywołujesz tylko wyświetlenie c(x,n) jako inta

można to też zrobić z cache'owaniem ale to trochę więcej zabawy

[radzym94]

Dziękuję bardzo za pomoc, aczkolwiek popełniłem mały błąd i chodziło o procedurę , a nie funkcję, aczkolwiek i tak dziękuję bardzo, mógłby Pan wyjaśnić mi

Kod: Zaznacz cały

int cn = c(x, n-1);
   

tą linijkę? Czy program najpierw oblicza poprzednie wyrazy ciągu a dopiero teraz aktualny? Procedurę da się z tego zrobić?

[Gouranga]

1. w C nie ma procedur, to nie Pascal
2. funkcje w C można robić rekurencyjnie aczkolwiek należy uważać np. przy wyświetlaniu czegoś rekurencyjnie bo trzeba ogarniać w jakiej kolejności będzie się to pojawiać
3. w tej linii jest właśnie wywołanie rekurencyjne i rozważmy taki proces:
-wywołujemy c(11,3)
-program robi cn = c(11,2)
-licząc to wywołuje c(11,1)
-to wywołanie zwraca 11
-na podstawie tego 11 liczy się to c(11,2)
-na podstawie tego liczy dopiero c(11,3)
czyli generalnie zagłebia rekurencję coraz bardziej i wszystko pamięta a potem od środka z wynikami wraca do zewnątrz redukując tę rekurencję.
4. da się zrobić funkcję void, jednak to trochę cięższa sprawa bo potrzeba by dodatkowego argumentu na przekazywanie wyników między poziomami rekurencji

[radzym94]

TAk oczywiście, myśląc procedura chodziło mi oczywiście o funkcję void, aczkolwiek mój błąd Czyli reasumując funkcja najpierw przechodzi coraz głębiej, następnie gdy osiągnie 1 wyraz ciagu , to wtedy wraca po kolei do oczekiwanego elementu? A ta rekurencja nie będzie się wykonywała w nieskończoność? Jeśli osiągnie 1 element ciągu, no to ponownie wywoła tą funkcje.

[Kacperdev]

Dokładnie mówiąc odkłada wartości na stos, a następnie po kolei zdejmuje.

[Gouranga]

Dokładnie, tak działa każda rekurencja.
Dobrze obrazuje to liczenie silni:
\(\displaystyle{ 0! = 1\\
n! = n\cdot (n-1)!}\)
komputer oblicza tak:
\(\displaystyle{ 3! = 3\cdot 2! = 3\cdot 2 \cdot 1! = 3\cdot 2 \cdot 1 \cdot 0! = 3\cdot 2 \cdot 1 \cdot 1 = 3\cdot 2 \cdot 1 = 3\cdot 2 = 6}\)

[radzym94]

Czyli jeśli funkcją osiągnie n=1 to wtedy bierze tylko wartość x , i nie wywoła kolejny raz funkcji (bo w tym fragmencie funkcji nie ma kolejnego wywołania), tylko przejdzie w programie dalej , do liczenia poszczególnych wartości ze wzoru?

[Gouranga]

Tak. funkcja rekurencyjna zawsze ma warunek początkowy i ogólny. Przy początkowym jej wartość jest określona, przy ogólnym korzysta z poprzednich. Oczywiście początkowych może być kilka jak np. w ciągu Fibonacciego

[radzym94]

To jeszcze jedno pytanie. Dobrze rozumiem ,że to dzieje się tak, że funkcja przechodzi wgłąb do elementu który jest znany (czyli element 1) i później z tą wartością elementu wędruje do linijki

Kod: Zaznacz cały

return (int)(0.5 * cn - 0.25 * (5*cn+2)*(znak-1));

funkcji o poziom wyższej czyli do funkcji obliczającej 2 element pomijając już kolejne wywołanie czyli linijkę

Kod: Zaznacz cały

int cn = c(x, n-1);

w tej funkcji?

[Gouranga]

Tak. Schodzi do znanej wartości i z nią wraca

[radzym94]

Pomijając kolejne wywołania? I on to robi bo tak działa rekurencja, a nie ze wzgl na jakieś zabezpieczenie w kodzie , żeby nie wywoływać jej kolejny raz?

[Gouranga]

No zawsze masz warunek if który sprawdza, czy zostało wywołane dla znanej wartości, jeśli tak to ją zwraca, jeśli nie to liczy.