n-te Glied der Reihe

müssen wir http://oeis.org/A028859 n-te Glied der Reihe

n < = 1000000000

die n-te Glied dieser Serie finden Sie Antwort 1000000007 Modulo sollte

ich habe den Code geschrieben, aber Frist überschreitet, wenn na ist eine riesige Nummer.

#include<iostream> 
using namespace std 

int main() 
{ 
    long long int n; 
    cin>>n; 

    long long int a,b,c; 
    a=1; 
    b=3; 

    int i; 
    for(i=3;i<=n;i++) 
    { 
     c=(2ll*(a+b))%1000000007; 
     a=b; 
     b=c; 
    } 

    cout<<c; 
}

Quelle

2012-07-01 user1484638

Jede Chance, Sie in einem saubereren Code Probe als diese, die über geeignete Vertiefung und die Vermeidung des übermäßigen Leerraum einfügen könnte? –

Was hat das mit dynamischer Programmierung zu tun? – Mathias

Versuchen Sie, die rekursive Version dieses Algorithmus und Sie werden verstehen, wie dies ein dynamischer Programmieralgorithmus ist. Grundsätzlich speichern wir die berechneten Werte von n-1 und n-2. Sagen wir, es ist eine grundlegende Version von DP. –

Die Standardtechnik für diese Art der Problemlösung ist es als eine Matrix-Multiplikation neu zu schreiben und dann exponentiation by squaring verwenden, um effizient Kräfte der Matrix zu berechnen.

In diesem Fall gilt:

a(n+2) = 2 a(n+1) + 2 a(n) 
a(n+1) = a(n+1) 

(a(n+2)) = (2 2) * (a(n+1)) 
(a(n+1)) (1 0) (a(n) )

Wenn wir also die Matrix A = [2,2 definieren; 1,0], dann können Sie die n-te Term berechnen, indem

[1,0] * A^(n-2) * [3;1]

Alle diese Operationen können Modulo 1000000007 so dass keine große Anzahl Bibliothek durchgeführt werden muss.

Es erfordert O (log (n)) 2 * 2 Matrixmultiplikationen, um A^N zu berechnen, also ist diese Methode insgesamt O (log (n)), während Ihre ursprüngliche Methode O (n) war.

EDIT

Here ist eine gute Erklärung und eine C++ Implementierung dieses Verfahrens.

Quelle

2012-07-01 21:19:28

[Hier] (http://stackoverflow.com/a/26281100/461597) Ich habe eine ähnliche Frage beantwortet, verwende aber zusätzlich Eulers Theorem. 1000 ... 07 ist eine Primzahl, Sie müssen also nicht A^N berechnen, aber A^(N% (p-1)) ist genug. Auf diese Weise wird das Verfahren O (1) (oder O (p), aber p ist konstant) anstelle von O (log (n)). – Unapiedra

Wenn long long nicht genug ist, wollen Sie wahrscheinlich eine bignum Bibliothek verwenden. Zum Beispiel GNU MP.

Quelle

2012-07-01 20:56:58 iblue

aber wir müssen Antwort geben modulo 1000000007 – user1484638

Nicht nur ist ** lang lang int ** genug, aber ich glaube ** unsigned long int ** ist auch ausreichend, da der maximal mögliche Wert 4 * 10000007 <4294967295 ist. –

ok .. können Sie einen Ansatz für dieses Problem vorschlagen – user1484638

Antwort

Verwandte Themen