NÚMERO DE PELL

Experimente no GfG Practice ' title=

#practiceLinkDiv { display: nenhum! Importante; }

Os números de Pell são números semelhantes aos números de Fibonacci e são gerados pela fórmula abaixo da seguinte forma:

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

Os primeiros números de Pell são 0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 .... Escreva uma função int pell(int n) que retorna P_n.

divisão de string c++

Exemplos:

Input : n = 4 Output :12

Input : n = 7 Output : 169

Recommended Practice Número de Pell Experimente!

Método 1 (usando recursão)

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>

Saída

Complexidade de tempo: O(2ⁿ) ou seja, complexidade de tempo exponencial.

Espaço Auxiliar: Sobre)

Método 2 (iterativo)

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>

Saída:

Complexidade de tempo: O(n)

Espaço Auxiliar: O(1)

Usando cálculo matricial :

Este é outro O(n) que se baseia no fato de que se multiplicarmos n vezes a matriz M = {{2 1} {1 0}} por si mesma (em outras palavras, calcular a potência (M n)), obteremos o (n+1)-ésimo número de Pell como o elemento na linha e na coluna (0 0) na matriz resultante.

M^n=início{bmatriz} P_{n+1} &P_n \ P_n &P_{n-1} fim{bmatriz}

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

fonte gimp

Complexidade de tempo: O (log n) Como podemos calcular a n-ésima potência de uma matriz 2 × 2 em O (log n) vezes

Criar questionário