Numer Pella
Wypróbuj w praktyce GfG 
#practiceLinkDiv { display: none !important; }
Wyjście
#practiceLinkDiv { display: none !important; } Liczby Pella to liczby podobne do liczb Fibonacciego i generowane za pomocą poniższego wzoru w następujący sposób:
P n = 2*P n-1 + P n-2 with seeds P 0 = 0 and P 1 = 1
Pierwsze kilka liczb Pella to 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Napisz funkcję int pell(int n), która zwraca P N .
Przykłady:
Input : n = 4 Output :12
Input : n = 7 Output : 169Recommended Practice Numer Pella Spróbuj!
Metoda 1 (przy użyciu rekurencji)
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>
Wyjście
12
Złożoność czasowa: O(2 N ) tj. wykładnicza złożoność czasowa.
Przestrzeń pomocnicza: NA)
Metoda 2 (iteracyjna)
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>
Wyjście:
12
Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(1)
Korzystanie z obliczeń macierzowych :
To kolejne O(n), które opiera się na fakcie, że jeśli n razy pomnożymy macierz M = {{2 1} {1 0}} przez samą siebie (innymi słowy obliczymy potęgę (M n)), to otrzymamy (n+1) liczbę Pell jako element w wierszu i kolumnie (0 0) wynikowej macierzy.
M^n=begin{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} end{bmatrix}
Gdzie M=begin{bmatrix} 2 &1 \ 1 &0 end{bmatrix}
Złożoność czasowa: O(log n) Ponieważ n-tą potęgę macierzy 2 × 2 możemy obliczyć w O(log n) razy
Utwórz quiz
