NUMER PELLA

Wypróbuj w praktyce GfG ' title=

#practiceLinkDiv { display: none !important; }

Liczby Pella to liczby podobne do liczb Fibonacciego i generowane za pomocą poniższego wzoru w następujący sposób:

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

Pierwsze kilka liczb Pella to 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Napisz funkcję int pell(int n), która zwraca P_N.

Przykłady:

poradnik Java dla początkujących

Input : n = 4 Output :12

Input : n = 7 Output : 169

Recommended Practice Numer Pella Spróbuj!

Metoda 1 (przy użyciu rekurencji)

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>

Wyjście

Złożoność czasowa: O(2^N) tj. wykładnicza złożoność czasowa.

Przestrzeń pomocnicza: NA)

Metoda 2 (iteracyjna)

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>

Wyjście:

nieważne 0

Złożoność czasowa: O(n)

Przestrzeń pomocnicza: O(1)

Korzystanie z obliczeń macierzowych :

To kolejne O(n), które opiera się na fakcie, że jeśli n razy pomnożymy macierz M = {{2 1} {1 0}} przez samą siebie (innymi słowy obliczymy potęgę (M n)), to otrzymamy (n+1) liczbę Pell jako element w wierszu i kolumnie (0 0) wynikowej macierzy.

struktury danych java

M^n=begin{bmatrix} P_{n+1} &P_n \ P_n &P_{n-1} end{bmatrix}

Gdzie M=begin{bmatrix} 2 &1 \ 1 &0 end{bmatrix}

Złożoność czasowa: O(log n) Ponieważ n-tą potęgę macierzy 2 × 2 możemy obliczyć w O(log n) razy

Utwórz quiz