ペル番号
GfG Practice で試してみる 
#practiceLinkDiv { 表示: なし !重要; }
出力
#practiceLinkDiv { 表示: なし !重要; } ペル数はフィボナッチ数に似た数であり、次の式によって生成されます。
P n = 2*P n-1 + P n-2 with seeds P 0 = 0 and P 1 = 1
最初のいくつかの Pell 番号は 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... P を返す関数 int pell(int n) を作成します。 n 。
例:
Input : n = 4 Output :12
Input : n = 7 Output : 169Recommended Practice ペル番号 試してみてください!
方法 1 (再帰を使用する)
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>
出力
12
時間計算量: O(2 n ) つまり、指数関数的な時間計算量。
補助スペース: の上）
方法 2 (反復)
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>
出力：
12
時間計算量: O(n)
補助スペース: O(1)
マトリックス計算を使用する :
これは、行列 M = {{2 1} {1 0}} を n 回乗算すると (つまり、power(M n) を計算すると)、結果の行列の行と列 (0 0) の要素として (n+1) 番目のペル番号が得られるという事実に依存するもう 1 つの O(n) です。
M^n=begin{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} end{bmatrix}
ここで、M=begin{bmatrix} 2 &1 \ 1 &0 end{bmatrix}
時間計算量: O(log n) 2 × 2 行列の n 乗を O(log n) 回で計算できるため
クイズの作成
