Encuentra el enésimo número de Fibonacci usando la proporción áurea

Serie de Fibonacci = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …….. Ya se han discutido
diferentes métodos para encontrar el n-ésimo número de Fibonacci . Otra forma sencilla de encontrar el número de Fibonacci enésimo es usar la proporción áurea, ya que los números de Fibonacci mantienen una proporción áurea aproximada hasta el infinito. 
Proporción áurea: 
\varphi ={\frac {1+{\sqrt {5}}}{2}}=1.6180339887\ldots
Ejemplos: 
 

Input : n = 9
Output : 34

Input : n = 7
Output : 13

Enfoque: 
la proporción áurea puede darnos una respuesta incorrecta.  
Podemos obtener el resultado correcto si redondeamos el resultado en cada punto. 
 

nth fibonacci number = round(n-1th Fibonacci number X golden ratio)
                  fn = round(fn-1 * \varphi)

Hasta el cuarto término, la proporción no se acerca mucho a la proporción áurea (como 3/2 = 1,5, 2/1 = 2, …). Entonces, consideraremos desde el quinto término para obtener el siguiente número de Fibonacci. Para encontrar el noveno número de fibonacci f9 (n = 9): 
 

     f6 = round(f5 * \varphi) = 8f7 = round(f6 * \varphi) = 13f8 = round(f7 * \varphi) = 21f9 = round(f8 * \varphi) = 34

Nota: Este método puede calcular correctamente los primeros 34 números de Fibonacci. Después de eso, puede haber una diferencia con el valor correcto. 
A continuación se muestra la implementación del enfoque anterior: 
 

CPP

// CPP program to find n-th Fibonacci number
#include <bits/stdc++.h>
using namespace std;
 
// Approximate value of golden ratio
double PHI = 1.6180339;
 
// Fibonacci numbers upto n = 5
int f[6] = { 0, 1, 1, 2, 3, 5 };
 
// Function to find nth
// Fibonacci number
int fib(int n)
{
    // Fibonacci numbers for n < 6
    if (n < 6)
        return f[n];
 
    // Else start counting from
    // 5th term
    int t = 5, fn = 5;
    while (t < n) {
        fn = round(fn * PHI);
        t++;
    }
    return fn;
}
 
// driver code
int main()
{
    int n = 9;
    cout << n << "th Fibonacci Number = " << fib(n) << endl;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// C program to find n-th Fibonacci number
#include <math.h>
#include <stdio.h>
 
// Approximate value of golden ratio
double PHI = 1.6180339;
 
// Fibonacci numbers upto n = 5
int f[6] = { 0, 1, 1, 2, 3, 5 };
 
// Function to find nth
// Fibonacci number
int fib(int n)
{
    // Fibonacci numbers for n < 6
    if (n < 6)
        return f[n];
 
    // Else start counting from
    // 5th term
    int t = 5, fn = 5;
 
    while (t < n) {
        fn = round(fn * PHI);
        t++;
    }
 
    return fn;
}
 
// driver code
int main()
{
    int n = 9;
    printf("%d th Fibonacci Number = %d\n", n, fib(n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// Java program to find n-th Fibonacci number
 
class GFG
{
    // Approximate value of golden ratio
    static double PHI = 1.6180339;
     
    // Fibonacci numbers upto n = 5
    static int f[] = { 0, 1, 1, 2, 3, 5 };
     
    // Function to find nth
    // Fibonacci number
    static int fib (int n)
    {
        // Fibonacci numbers for n < 6
        if (n < 6)
            return f[n];
     
        // Else start counting from
        // 5th term
        int t = 5;
        int fn = 5;
     
        while (t < n) {
            fn = (int)Math.round(fn * PHI);
            t++;
        }
     
        return fn;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 9;
        System.out.println(n + "th Fibonacci Number = "
                                                +fib(n));
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 code to find n-th Fibonacci number
 
# Approximate value of golden ratio
PHI = 1.6180339
 
# Fibonacci numbers upto n = 5
f = [ 0, 1, 1, 2, 3, 5 ]
 
# Function to find nth
# Fibonacci number
def fib ( n ):
 
    # Fibonacci numbers for n < 6
    if n < 6:
        return f[n]
 
    # Else start counting from
    # 5th term
    t = 5
    fn = 5
     
    while t < n:
        fn = round(fn * PHI)
        t+=1
     
    return fn
 
# driver code
n = 9
print(n, "th Fibonacci Number =", fib(n))
 
# This code is contributed by "Sharad_Bhardwaj".

C#

// C# program to find n-th Fibonacci
// number
using System;
 
class GFG {
     
    // Approximate value of golden ratio
    static double PHI = 1.6180339;
     
    // Fibonacci numbers upto n = 5
    static int []f = { 0, 1, 1, 2, 3, 5 };
     
    // Function to find nth
    // Fibonacci number
    static int fib (int n)
    {
         
        // Fibonacci numbers for n < 6
        if (n < 6)
            return f[n];
     
        // Else start counting from
        // 5th term
        int t = 5;
        int fn = 5;
     
        while (t < n) {
            fn = (int)Math.Round(fn * PHI);
            t++;
        }
     
        return fn;
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 9;
         
        Console.WriteLine(n + "th Fibonacci"
                    + " Number = " + fib(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to find n-th
// Fibonacci number Approximate
// value of golden ratio
$PHI = 1.6180339;
 
// Fibonacci numbers
// upto n = 5
 
// Function to find nth
// Fibonacci number
function fib ($n)
{
    global $PHI;
    $f = array(0, 1, 1, 2, 3, 5);
     
    // Fibonacci numbers
    // for n < 6
    if ($n < 6)
        return $f[$n];
 
    // Else start counting
    // from 5th term
    $t = 5;
    $fn = 5;
 
    while ($t < $n)
    {
        $fn = round($fn * $PHI);
        $t++;
    }
 
    return $fn;
}
 
    // Driver Code
    $n = 9;
    echo $n, "th Fibonacci Number = ",
        fib($n), "\n";
 
// This code is contributed by aj_36
?>

Javascript

<script>
 
// JavaScript program to find n-th Fibonacci number
 
  // Approximate value of golden ratio
    let PHI = 1.6180339;
   
    // Fibonacci numbers upto n = 5
    let f = [ 0, 1, 1, 2, 3, 5 ];
   
    // Function to find nth
    // Fibonacci number
    function fib (n)
    {
        // Fibonacci numbers for n < 6
        if (n < 6)
            return f[n];
   
        // Else start counting from 
        // 5th term
        let t = 5, fn = 5;
   
        while (t < n) {
             fn = Math.round(fn * PHI);
             t++;
        }
   
        return fn;   
    }
   
    // driver code
 
    let n = 9;
     document.write(n + "th Fibonacci Number = " + fib(n) + "<br>");
   
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 
 

9th Fibonacci Number = 34

Podemos optimizar el trabajo de solución anterior en O (Log n) mediante el uso de un método eficiente para calcular la potencia .
Es posible que el método anterior no siempre produzca resultados correctos, ya que se trata de cálculos de coma flotante. Esta es la razón por la que este método no se usa en la práctica, incluso si se puede optimizar para que funcione en O (Log n). Consulte el siguiente video del MIT para obtener más detalles.
https://www.youtube.com/watch?v=-EQTVuAhSFY
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *