[C++] Ciąg z rekurencyjnego na iteracyjne

[MathMaster]

Witam

Mam takie zadanie

Agnieszka tak polubiła ciągi rekurencyjne, że nie zastanawia się już dłużej nad królikami, tylko analizuje same wzory. Tym razem prosi o obliczenie wartości elementów ciągu określonego wzorami: \(\displaystyle{ A(0)=4, A(1)=7, A(n)=2A(n-1)+5A(n-2)}\) dla \(\displaystyle{ n \ge 2}\). Agnieszka zdaje sobie sprawę, że taki ciąg rośnie bardzo szybko, a więc chciałaby poznać tylko reszty z dzielenia jego wyrazów przez \(\displaystyle{ 2011}\).

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita \(\displaystyle{ t \le 10}\) oznaczająca liczbę testów.
W kolejnych liniach znajdują się poszczególne testy. Każdy z nich składa się z jednej liczby całkowitej \(\displaystyle{ n (0 \le n \text 100)}\).

Wyjście

Dla każdego testu wypisz w osobnej linii resztę z dzielenia wartości \(\displaystyle{ A(n)}\) przez \(\displaystyle{ 2011}\).

Przykład

Kod: Zaznacz cały

Wejście:
3
0
1
2

Wyjście:
4
7
34

Rozwiązałem zadanie w c++ rekurencyjnie, niestety profesor prosił by rozwiązać je iteracyjnie, czyli poprzez pętle i nie mam pojęcia jak przekształcić algorytm. Jakieś sugestie?

Kod: Zaznacz cały

#include <iostream>
using namespace std;

int A(int n) {
	if (n == 0) return 4;
	else if (n == 1) return 7;
	else return 2*A(n-1)+5*A(n-2) % 2011;
}

int main() {
	int t, tab[10];
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> tab[i];
	}
	for (int i = 0; i < t; i++) {
		cout << A(tab[i]) << endl;
	}
	return 0;
}

Z góry dziękuję za pomoc .

Pozdrawiam.

[vpprof]

Potrzebujesz tablicy, w której przechowasz \(\displaystyle{ 3}\) kolejne wyrazy ciągu \(\displaystyle{ a_n}\): dwa wcześniejsze potrzebne do obliczenia trzeciego.

[pawel_wr]

W linii 7 twojego kodu jest błąd -> brakuje nawiasów.

Wersja iteracyjna wygląda tak

Kod: Zaznacz cały

    int a[10];
    int n;  //n<<11
     
    cin>>n;
    
    a[0]=4;
    a[1]=7;
    
    for(int i=2 ; i<n ; i++)
        a[i]=2*a[i-1]+7*a[i-2];
 
    for(int i=0 ; i<n ; i++)
        cout<<a[i]%2011<<endl;; 

[MathMaster]

Pomijam fakt, że pomyliłeś się przy przepisywaniu wzoru a[i]=2*a[i-1]+[b]5[/b]*a[i-2];

Ale twój tok myślenia bardzo mi pomógł, dzięki temu skonstruowałem program już w wersji iteracyjnej, lecz nie wiadomo czemu zaczyna on podawać złe wyniki przy większych liczbach ciągu.

Kod: Zaznacz cały

#include <iostream>
using namespace std;
int A(int n) {
	int tab[n];
	tab[0] = 4;
	tab[1] = 7;
	if (n > 1) {
		for (int i = 2; i <= n; i++) {
			tab[i] = 2 * tab[i - 1] + 5 * tab[n - 2] ; 
		}
	}
	return tab[n];
}

int main() {
	int t;
	cin >> t;
	int tabt[t];
	for (int i = 0; i < t; i++) cin >> tabt[i];
	for (int i = 0; i < t; i++) cout << A(tabt[i]) % 2011 << endl;
	return 0;
}

Przy \(\displaystyle{ n=3}\) powinno być 103, a program wyświetla 133 dla \(\displaystyle{ n \ge 3}\), wszystkie wyniki są błędne.

[pawel_wr]

Masz błąd w linii nr 9

Kod: Zaznacz cały

 tab[i] = 2 * tab[i - 1] + 5 * tab[n - 2] ;   ////// !!!!  n zamiast i

ma być 5*tab[i-2] , a jest 5*tab[n-2].

[MathMaster]

Rzeczywiście dzięki bardzo. Program działa.