Número de teléfono – Barcelona Geeks

Los números de Pell son números que son similares a los números de Fibonacci y se generan mediante la siguiente fórmula

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

Los primeros números de Pell son 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, ….
Escriba una función int pell(int n) que devuelva P _n .
Ejemplos:

Input : n = 4
Output :12

Input  : n = 7
Output : 169

Método 1 (usando recursividad)

C++

// Pell Number Series using Recursion in C++
#include <bits/stdc++.h>
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 <stdio.h>
 
// 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

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

Producción :

Método 2 (iterativo)

C++

// Iterative Pell Number Series in C++
#include <bits/stdc++.h>
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 <stdio.h>
 
// 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

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

Producción:

Complejidad de tiempo: O(n)
Espacio extra: O(1)
Uso de cálculo matricial :
este otro O(n) que se basa en el hecho de que si multiplicamos n veces la array M = {{2, 1}, {1, 0 }} a sí mismo (en otras palabras, calcule la potencia (M, n)), luego obtenemos el (n+1) número de Pell como el elemento en la fila y la columna (0, 0) en la array resultante.
$M^n=\begin{bmatrix} P_{n+1} &P_n \\ P_n &P_{n-1} \end{bmatrix}$
$Where, M=\begin{bmatrix} 2 &1 \\ 1 &0 \end{bmatrix}$
Complejidad de tiempo: dado que podemos calcular la potencia n-ésima de una array de 2 × 2 en tiempo O (log n), la complejidad de tiempo de esta solución es O (log n) Pavan Gopal Rayapati
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

C

Java

Python3

C#

PHP

Javascript

C++

C

Java

Python

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta