Pell-Nummer
Probieren Sie es bei GfG Practice aus 
#practiceLinkDiv { display: none !important; }
Ausgabe
#practiceLinkDiv { display: none !important; } Pell-Zahlen sind Zahlen, die den Fibonacci-Zahlen ähneln und mit der folgenden Formel wie folgt generiert werden:
P n = 2*P n-1 + P n-2 with seeds P 0 = 0 and P 1 = 1
Die ersten paar Pell-Zahlen sind 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Schreiben Sie eine Funktion int pell(int n), die P zurückgibt N .
Beispiele:
Input : n = 4 Output :12
Input : n = 7 Output : 169Recommended Practice Pell-Nummer Probieren Sie es aus!
Methode 1 (mit Rekursion)
C++ // Pell Number Series using Recursion in C++ #include using namespace std ; // calculate nth pell number int pell ( int n ) { if ( n <= 2 ) return n ; return 2 * pell ( n - 1 ) + pell ( n - 2 ); } // Driver Code int main () { int n = 4 ; cout < < ' ' < < pell ( n ); return 0 ; } // This code is contributed by shivanisinghss2110
C // Pell Number Series using Recursion in C #include // calculate nth pell number int pell ( int n ) { if ( n <= 2 ) return n ; return 2 * pell ( n - 1 ) + pell ( n - 2 ); } // driver function int main () { int n = 4 ; printf ( '%d' pell ( n )); return 0 ; }
Java // Pell Number Series using Recursion in JAVA class PellNumber { // calculate n-th Pell number public static int pell ( int n ) { if ( n <= 2 ) return n ; return 2 * pell ( n - 1 ) + pell ( n - 2 ); } // driver function public static void main ( String args [] ) { int n = 4 ; System . out . println ( pell ( n )); } }
Python3 # Pell Number Series using # Recursion in Python3 # Calculate nth pell number def pell ( n ) : if ( n <= 2 ) : return n return ( 2 * pell ( n - 1 ) + pell ( n - 2 )) # Driver function n = 4 ; print ( pell ( n )) # This code is contributed by Nikita Tiwari.
C# // Pell Number Series using Recursion in C# using System ; class PellNumber { // calculate n-th Pell number public static int pell ( int n ) { if ( n <= 2 ) return n ; return 2 * pell ( n - 1 ) + pell ( n - 2 ); } // Driver function public static void Main () { int n = 4 ; Console . Write ( pell ( n )); } } // This code is contributed by vt_m.
PHP // Pell Number Series using // Recursion in PHP // calculate nth pell number function pell ( $n ) { if ( $n <= 2 ) return $n ; return 2 * pell ( $n - 1 ) + pell ( $n - 2 ); } // Driver Code $n = 4 ; echo ( pell ( $n )); // This code is contributed by Ajit. ?>
JavaScript < script > // Pell Number Series using // Recursion in Javascript // calculate nth pell number function pell ( n ) { if ( n <= 2 ) return n ; return 2 * pell ( n - 1 ) + pell ( n - 2 ); } // Driver Code let n = 4 ; document . write ( pell ( n )); // This code is contributed by _saurabh_jaiswal. < /script>
Ausgabe
12
Zeitkomplexität: O(2 N ) d. h. exponentielle Zeitkomplexität.
Hilfsraum: An)
Methode 2 (Iterativ)
C++ // Iterative Pell Number Series in C++ #include using namespace std ; // Calculate nth pell number int pell ( int n ) { if ( n <= 2 ) return n ; int a = 1 ; int b = 2 ; int c i ; for ( i = 3 ; i <= n ; i ++ ) { c = 2 * b + a ; a = b ; b = c ; } return b ; } // Driver Code int main () { int n = 4 ; cout < < pell ( n ); return 0 ; } // This code is contributed by nidhi_biet
C // Iterative Pell Number Series in C #include // calculate nth pell number int pell ( int n ) { if ( n <= 2 ) return n ; int a = 1 ; int b = 2 ; int c i ; for ( i = 3 ; i <= n ; i ++ ) { c = 2 * b + a ; a = b ; b = c ; } return b ; } // driver function int main () { int n = 4 ; printf ( '%d' pell ( n )); return 0 ; }
Java // Iterative Pell Number Series in Java class PellNumber { // calculate nth pell number public static int pell ( int n ) { if ( n <= 2 ) return n ; int a = 1 ; int b = 2 ; int c ; for ( int i = 3 ; i <= n ; i ++ ) { c = 2 * b + a ; a = b ; b = c ; } return b ; } // driver function public static void main ( String args [] ) { int n = 4 ; System . out . println ( pell ( n )); } }
Python # Iterative Pell Number # Series in Python 3 # calculate nth pell number def pell ( n ) : if ( n <= 2 ) : return n a = 1 b = 2 for i in range ( 3 n + 1 ) : c = 2 * b + a a = b b = c return b # driver function n = 4 print ( pell ( n )) # This code is contributed by Nikita Tiwari.
C# // Iterative Pell Number Series in C# using System ; class PellNumber { // calculate nth pell number public static int pell ( int n ) { if ( n <= 2 ) return n ; int a = 1 ; int b = 2 ; int c ; for ( int i = 3 ; i <= n ; i ++ ) { c = 2 * b + a ; a = b ; b = c ; } return b ; } // Driver function public static void Main () { int n = 4 ; Console . Write ( pell ( n )); } } // This code is contributed by vt_m.
PHP // Iterative Pell Number Series in PHP // calculate nth pell number function pell ( $n ) { if ( $n <= 2 ) return $n ; $a = 1 ; $b = 2 ; $c ; $i ; for ( $i = 3 ; $i <= $n ; $i ++ ) { $c = 2 * $b + $a ; $a = $b ; $b = $c ; } return $b ; } // Driver Code $n = 4 ; echo ( pell ( $n )); // This code is contributed by Ajit. ?>
JavaScript < script > // Iterative Pell Number Series in Javascript // calculate nth pell number function pell ( n ) { if ( n <= 2 ) return n ; let a = 1 ; let b = 2 ; let c ; for ( let i = 3 ; i <= n ; i ++ ) { c = 2 * b + a ; a = b ; b = c ; } return b ; } let n = 4 ; document . write ( pell ( n )); < /script>
Ausgabe:
12
Zeitkomplexität: O(n)
Hilfsraum: O(1)
Mit Matrixberechnung :
Dies ist ein weiteres O(n), das auf der Tatsache beruht, dass wir, wenn wir die Matrix M = {{2 1} {1 0}} n-mal mit sich selbst multiplizieren (mit anderen Worten die Potenz (M n) berechnen), die (n+1)-te Pell-Zahl als Element in Zeile und Spalte (0 0) in der resultierenden Matrix erhalten.
M^n=begin{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} end{bmatrix}
Wobei M=begin{bmatrix} 2 &1 \ 1 &0 end{bmatrix}
Zeitkomplexität: O(log n) Da wir die n-te Potenz einer 2 × 2-Matrix in O(log n)-Zeiten berechnen können
Quiz erstellen
