Pell číslo
Vyskúšajte to na GfG Practice 
#practiceLinkDiv { display: none !important; }
Výstup
#practiceLinkDiv { display: none !important; } Čísla peliet sú čísla, ktoré sú podobné Fibonacciho číslam a sú generované nasledujúcim vzorcom:
P n = 2*P n-1 + P n-2 with seeds P 0 = 0 and P 1 = 1
Prvých pár čísel Pellu je 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Napíšte funkciu int pell(int n), ktorá vráti P n .
Príklady:
Input : n = 4 Output :12
Input : n = 7 Output : 169Recommended Practice Pell číslo Skúste to!
Metóda 1 (pomocou rekurzie)
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>
Výstup
12
Časová zložitosť: O(2 n ) t. j. exponenciálna časová zložitosť.
Pomocný priestor: O(n)
Metóda 2 (opakovaná)
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>
výstup:
12
Časová zložitosť: O(n)
Pomocný priestor: O(1)
Použitie maticového výpočtu :
Toto je ďalšie O(n), ktoré sa spolieha na skutočnosť, že ak n-krát vynásobíme maticu M = {{2 1} {1 0}} sama k sebe (inými slovami vypočítame mocninu (M n)), potom dostaneme (n+1)-té Pellovo číslo ako prvok v riadku a stĺpci (0 0) vo výslednej matici.
M^n=začiatok{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} koniec{bmatrix}
Kde M=začiatok{bmatrix} 2 &1 \ 1 &0 koniec{bmatrix}
Časová zložitosť: O(log n) Pretože môžeme vypočítať n-tu mocninu matice 2 × 2 v O(log n) krát
Vytvoriť kvíz
