PELL SZÁM

Próbáld ki a GfG Practice-n ' title=

#practiceLinkDiv { display: none !important; }

A Pell-számok olyan számok, amelyek hasonlóak a Fibonacci-számokhoz, és az alábbi képlettel jönnek létre:

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

Az első néhány Pell-szám 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Írjon egy int pell(int n) függvényt, amely P-t adja vissza_n.

Példák:

Input : n = 4 Output :12

Input : n = 7 Output : 169

Recommended Practice Pell szám Próbáld ki!

1. módszer (Rekurzió használata)

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>

Kimenet

Időbeli összetettség: O(2ⁿ) azaz exponenciális időbonyolultság.

Segédtér: On)

2. módszer (Iteratív)

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>

Kimenet:

Időbonyolultság: O(n)

Segédtér: O(1)

Mátrix számítás használata :

Ez egy másik O(n), amely azon alapul, hogy ha az M = {{2 1} {1 0}} mátrixot n-szer megszorozzuk önmagával (más szóval kiszámoljuk a teljesítményt (M n)), akkor az (n+1)-edik Pell-számot kapjuk elemként a (0 0) sorban és oszlopban a kapott mátrixban.

M^n=kezdet{bmátrix} P_{n+1} &P_n \ P_n &P_{n-1} vége{bmátrix}

ahol M=kezdet{bmátrix} 2 &1 \ 1 &0 vége{bmátrix}

Időbeli összetettség: O(log n) Mivel egy 2 × 2-es mátrix n-edik hatványát ki tudjuk számítani O(log n)-szer

Kvíz létrehozása