Pellin numero
Kokeile sitä GfG Practicessa 
#practiceLinkDiv { näyttö: ei mitään !tärkeää; }
Lähtö
#practiceLinkDiv { näyttö: ei mitään !tärkeää; } Pell-luvut ovat lukuja, jotka ovat samanlaisia kuin Fibonacci-luvut ja jotka generoidaan alla olevalla kaavalla seuraavasti:
P n = 2*P n-1 + P n-2 with seeds P 0 = 0 and P 1 = 1
Ensimmäiset Pell-luvut ovat 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Kirjoita funktio int pell(int n), joka palauttaa P n .
Esimerkkejä:
Input : n = 4 Output :12
Input : n = 7 Output : 169Recommended Practice Pellin numero Kokeile sitä!
Tapa 1 (Rekursion käyttö)
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>
Lähtö
12
Aika monimutkaisuus: O(2 n ) eli eksponentiaalinen aikamonimutkaisuus.
Aputila: O(n)
Menetelmä 2 (Iteratiivinen)
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>
Lähtö:
12
Aika monimutkaisuus: O(n)
Aputila: O(1)
Matriisilaskelman käyttö :
Tämä toinen O(n), joka perustuu siihen tosiasiaan, että jos kerromme n kertaa matriisin M = {{2 1} {1 0}} itselleen (eli laskemme teho(M n)), niin saadaan tuloksena olevan matriisin rivin ja sarakkeen (0 0) elementiksi (n+1) Pell-luku.
M^n=alku{bmatriisi} P_{n+1} &P_n \ P_n &P_{n-1} loppu{bmatriisi}
Missä M=alku{bmatriisi} 2 &1 \ 1 &0 loppu{bmatriisi}
Aika monimutkaisuus: O(log n) Koska voimme laskea 2 × 2 matriisin n:nnen potenssin O(log n) kertaa
Luo tietokilpailu
