Рубрики

N-е число Фибоначчи с использованием уравнения Пелла

Учитывая целое число N , задача состоит в том, чтобы найти N- е число Фибоначчи .

Input: N = 13
Output: 144

Input: N = 19
Output: 2584

Подход: N- е число Фибоначчи можно найти, используя корни уравнения Пелла . Уравнение Пеллса обычно имеет вид (x 2 ) — n (y 2 ) = | 1 | ,
Здесь рассмотрим y 2 = x, n = 1 . Кроме того, положительный (+1) в правой части.
Теперь уравнение становится x 2 — x = 1, что совпадает с x 2 — x — 1 = 0 .
Здесь {x = (p i — q i ) / (p — q)} обозначается как N- й член ряда Фибоначчи, где i = n — 1, а (p, q) — корни уравнения Пелла.

To find roots of general quadratic equation (a*x2 + b*x + c = 0).
x1 = [-b + math.sqrt(b2 – 4*a*c)] / 2*a
x2 = [-b – math.sqrt(b2 – 4*a*c)] / 2*a
i.e.
p = (1 + math.sqrt(5)) / 2
q = (1 – math.sqrt(5)) / 2

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата
// число Фибоначчи

int fib(int n)

{

    // Назначаем корни пелла

    // уравнение для p и q

    double p = ((1 + sqrt(5)) / 2);

    double q = ((1 - sqrt(5)) / 2);

    int i = n - 1;

    int x = (int) ((pow(p, i) - 

                    pow(q, i)) / (p - q));

    return x;

}

  
// Код драйвера

int main()

{

    int n = 5;

    cout << fib(n);

}

  
// Этот код предоставлен PrinciRaj1992

Джава

// Java реализация подхода

class GFG 

{

      
// Назначаем корни пелла
// уравнение для p и q

static double p = ((1 + Math.sqrt(5)) / 2);

static double q = ((1 - Math.sqrt(5)) / 2);

  
// Функция для возврата
// число Фибоначчи

static int fib(int n)

{

    int i = n - 1;

    int x = (int) ((Math.pow(p, i) - 

                    Math.pow(q, i)) / (p - q));

    return x;

}

  
// Код драйвера

public static void main(String[] args) 

{

    int n = 5;

    System.out.println(fib(n));

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 реализация подхода

import math

  
# Назначить корни пелла
# уравнение для p и q

p = (1 + math.sqrt(5)) / 2

q = (1 - math.sqrt(5)) / 2

  
# Функция для возврата
номер n числа Фибоначчи

def fib(n):

    i = n - 1

    x = (p**i - q**i) / (p - q)

    return int(x)

  
# Код драйвера

n = 5

print(fib(n))

C #

// C # реализация подхода

using System;

  

class GFG

{

          
// Назначаем корни пелла
// уравнение для p и q

static double p = ((1 + Math.Sqrt(5)) / 2);

static double q = ((1 - Math.Sqrt(5)) / 2);

  
// Функция для возврата
// число Фибоначчи

static int fib(int n)

{

    int i = n - 1;

    int x = (int) ((Math.Pow(p, i) - 

                    Math.Pow(q, i)) / (p - q));

    return x;

}

  
// Код драйвера

static public void Main ()

{

    int n = 5;

    Console.Write(fib(n));

}

  
// Этот код предоставлен @ajit ..

Выход:

3

Рекомендуемые посты:

N-е число Фибоначчи с использованием уравнения Пелла

0.00 (0%) 0 votes