ŠTEVILKA PELL

Preizkusite na GfG Practice ' title=

#practiceLinkDiv { display: none !important; }

Pellova števila so števila, ki so podobna Fibonaccijevim številom in so ustvarjena s spodnjo formulo, kot sledi:

P_n = 2*P_n-1 + P_n-2 with seeds P₀ = 0 and P₁ = 1

Prvih nekaj Pellovih števil je 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Napišite funkcijo int pell(int n), ki vrne P_n.

Primeri:

char in int java

Input : n = 4 Output :12

Input : n = 7 Output : 169

Recommended Practice Številka Pell Poskusite!

1. način (uporaba rekurzije)

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

// 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.

// 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>

Izhod

Časovna zapletenost: O(2ⁿ) tj. eksponentna časovna kompleksnost.

Pomožni prostor: O(n)

Metoda 2 (iterativna)

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

// 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.

// 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>

Izhod:

Časovna zahtevnost: O(n)

Pomožni prostor: O(1)

Uporaba matričnega izračuna :

To je še en O(n), ki temelji na dejstvu, da če n-krat pomnožimo matriko M = {{2 1} {1 0}} nase (z drugimi besedami izračunamo moč (M n)), potem dobimo (n+1)-to Pellovo število kot element v vrstici in stolpcu (0 0) v rezultantni matriki.

M^n=začetek{bmatrika} P_{n+1} &P_n \ P_n &P_{n-1} konec{bmatrika}

Kjer je M=začetek{bmatrix} 2 &1 \ 1 &0 konec{bmatrix}

Časovna zapletenost: O(log n) Ker lahko izračunamo n-to potenco matrike 2 × 2 v O(log n)-krat

bah če drugače

Ustvari kviz