C++ Dany jest wzór ciągu, za pomoca rekurencji oblicz resztę z dzielenia wyrazu An przez 2011

obliczanie wartości elementów ciągu określonego wzorami: A(0)=4, A(1)=7, A(n)=2A(n-1)+5A(n-2) dla n>=2. Taki ciąg rośnie bardzo szybko, a więc chcemy poznać tylko reszty z dzielenia jego wyrazów przez 2011. Najpierw użytkownik podaje ile liczb wprowadzi.Dla każdej liczby wypisz w osobnej linii resztę z dzielenia wartości A(n) przez 2011. Np jeżeli użytkownik wprowadzi: 3 0 1 2 to na ekranie powinno wyświetlić się: 4 7 34

Jak by ktoś mógł zamieścić chociaż wzór f.rekurencyjnej która by obliczała wartość reszty z dzielenia, to myślę, że z resztą bym sobie poradził. Pozdrawiam.

a potęgować potrafimy szybko, nawet macierze

Witam, napisałem taki kod ale ponoć jest w nim błąd, mógł byś zerknąć w którym miejscu ?

 #include <cstdlib>
#include <iostream>


using namespace std;

int main()
{
    int lt=0;
    int temp=0;
    cin>>lt;
    int * stab=new int[lt];
    for (int i=0; i<lt; i++)
    {
        cin >> stab[i];
    }
    int tab[100];
    tab[0]=4;
    tab[1]=7;
    for (int k=2; k<=100; k++)
    {
                       tab[k]=(2*tab[k-1])+(5*tab[k-2]); 
    }
    for (int j=0; j<lt; j++)
    {
        if (stab[j]==0)
           cout << tab[0] <<endl;
        if (stab[j]==1)
           cout << tab[1] <<endl;
        if (stab[j]!=0 && stab[j]!=1)
           cout << tab[stab[j]]%2011 <<endl;
    }
    delete [] stab;
    
    system("PAUSE");
    return 0;
}

Xitami napisał(a)

a potęgować potrafimy szybko, nawet macierze

To jedynie przyspieszy obliczania.
Trzeba skorzystać z właściwości arytmetyki modularnej, by nie przekroczyć zakresu liczb int.

Takie coś rozwiązuje problem bez implementowania szybkiego potęgowania:

int aN_modulo_2011[MaximumNValueAndOne];
aN_modulo_2011[0] = 4;
aN_modulo_2011[1] = 7;

for (int i=2; i<=max; ++i) {
     aN_modulo_2011[i] = (2 * aN_modulo_2011[n-1]+5 * aN_modulo_2011[n-2]) % 2011;
}

MaximumValueAndOne
Co to jest za wartość ? czy mógł byś umieścić swój skrawek w całym kodzie bo coś nie działa.

no cóż, wydawało się, że o oczywistych oczywistościach nie warto wspominać

Marku@
chyba nie do końca rozumiesz różnicę między O(n) a O(log n)
powiedzmy, że n to 10^24, załóżmy, że potrafisz wykonać miliard operacji na sekundę, ale jest kłopot, wiek wszechświata szacuje się tylko na kilkanaście miliardów lat
24 to fajna liczba, bo log(24!)=(około)24

jeszcze jedno, potęgować potrafimy nawet szybciej niż "szybko"

ta kwadratowa macierz to jedynka poniżej głównej przekątnej plus ostatnia kolumna
nie tylko takie heteryczne funkcje potrafimy sprowadzić do takiej postaci, można jeszcze dodać wielomian od n

prosiłbym jeszcze o dowód, że w:
aN_modulo_2011[i] = (2 * aN_modulo_2011[n-1]+5 * aN_modulo_2011[n-2]) % 2011;
nie pojawi się niejawne modulo 2^32, mile widziany matematyczny, wystarczy silny eksperymentalny.