Dados cinco enteros i, F i , j, F j y N . Donde F i y F j son el término i -ésimo y j -ésimo de una secuencia que sigue la recurrencia de Fibonacci , es decir , F N = F N – 1 + F N – 2 . La tarea es encontrar el N -ésimo término de la secuencia original.
Ejemplos:
Entrada: i = 3, F 3 = 5, j = -1, F -1 = 4, N = 5
Salida: 12 La
secuencia de Fibonacci se puede reconstruir utilizando valores conocidos:
…, F -1 = 4, F 0 = -1 , F 1 = 3, F 2 = 2, F 3 = 5, F 4 = 7, F 5 = 12, …
Entrada: i = 0, F 0 = 1, j = 1, F 1 = 4, N = – 2
Salida: -2
Enfoque: tenga en cuenta que, si se conocen los dos términos consecutivos de la sucesión de Fibonacci, el término N se puede determinar fácilmente. Suponiendo i < j , según la condición de Fibonacci:
F i+1 = 1*F i+1 + 0*F i
F i+2 = 1*F i+1 + 1*F i
F i+3 = F i+2 + F i+1 = 2*F i+1 + 1*F i
F i+4 = F i+3 + F i+2 = 3*F i+1 + 2*F i
F i+5 = F i+4 + F i+3 = 5 *F i+1 + 3*F i
.. .. ..
y así sucesivamente
Tenga en cuenta que los coeficientes de F i+1 y F i en el conjunto de ecuaciones anterior no son más que los términos de la secuencia estándar de Fibonacci .
Entonces, considerando la secuencia estándar de Fibonacci, es decir, f 0 = 0, f 1 = 1, f 2 = 1, f 3 = 2, f 4 = 3, … ; podemos generalizar, el conjunto anterior de ecuaciones (para k > 0) como:
F i+k = f k *F i+1 + f k-1 *F i …(1)
Ahora considera,
k = ji …(2)
Ahora, sustituyendo la ecuación (2) en la ecuación (1) , obtenemos:
Fj = fj -i *Fi +1 + fj-i-1 * Fi
Por lo tanto, podemos calcular F i+1 a partir de valores conocidos de F i y F j . Ahora que conocemos dos términos consecutivos de la secuencia F , podemos reconstruir fácilmente F y determinar el valor de F N.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to calculate kth Fibonacci number
// in the standard Fibonacci sequence
int fibonacci(int k)
{
int a = 0, b = 1, c = 0;
if( k == 0)
return a;
if (k == 1)
return b;
for(int i = 2; i < k + 1; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
// Function to determine the value of F(n)
int determineFn(int i, int Fi, int j, int Fj, int n)
{
if (j < i)
{
swap(i, j);
swap(Fi, Fj);
}
// Find the value of F(i + 1)
// from F(i) and F(j)
int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) /
fibonacci(j - i);
// When n is equal to i
int Fn = 0;
if (n == i)
Fn = Fi;
// When n is greater than i
else if (n > i)
{
int b = Fi;
Fn = Fi1;
n = n - 1;
while (n != i)
{
n = n - 1;
int a = b;
b = Fn;
Fn = a + b;
}
}
// When n is smaller than i
else
{
int a = Fi;
int b = Fi1;
while (n != i)
{
n = n + 1;
Fn = b - a;
b = a;
a = Fn;
}
}
return Fn;
}
// Driver code
int main()
{
int i = 3;
int Fi = 5;
int j = -1;
int Fj = 4;
int n = 5;
cout << (determineFn(i, Fi, j, Fj, n));
}
// This code is contributed by Mohit Kumar
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to calculate kth Fibonacci number
// in the standard Fibonacci sequence
static int fibonacci(int k)
{
int a = 0, b = 1, c = 0;
if (k == 0)
return a;
if (k == 1)
return b;
for (int i = 2; i < k + 1; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
// Function to determine the value of F(n)
static int determineFn(int i, int Fi,
int j, int Fj, int n)
{
if (j < i)
{
// Swap i, j
i = i + j;
j = i - j;
i = i - j;
// swap Fi, Fj
Fi = Fi + Fj;
Fj = Fi - Fj;
Fi = Fi - Fj;
}
// Find the value of F(i + 1)
// from F(i) and F(j)
int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) /
fibonacci(j - i);
// When n is equal to i
int Fn = 0;
if (n == i)
Fn = Fi;
// When n is greater than i
else if (n > i)
{
int b = Fi;
Fn = Fi1;
n = n - 1;
while (n != i)
{
n = n - 1;
int a = b;
b = Fn;
Fn = a + b;
}
}
// When n is smaller than i
else
{
int a = Fi;
int b = Fi1;
while (n != i)
{
n = n + 1;
Fn = b - a;
b = a;
a = Fn;
}
}
return Fn;
}
// Driver Code
public static void main(String[] args)
{
int i = 3;
int Fi = 5;
int j = -1;
int Fj = 4;
int n = 5;
System.out.println(determineFn(i, Fi, j, Fj, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach # Function to calculate kth Fibonacci number # in the standard Fibonacci sequence def fibonacci(k): a = 0 b = 1 if k == 0: return a if k == 1: return b for i in range(2, k + 1): c = a + b a = b b = c return c # Function to determine # the value of F(n) def determineFn(i, Fi, j, Fj, n): if j<i: i, j = j, i Fi, Fj = Fj, Fi # Find the value of F(i + 1) # from F(i) and F(j) Fi1 = (Fj - fibonacci(j-i-1)*Fi)\ //fibonacci(j-i) # When n is equal to i if n == i: Fn = Fi # When n is greater than i elif n>i: b = Fi Fn = Fi1 n = n - 1 while n != i: n = n - 1 a = b b = Fn Fn = a + b # When n is smaller than i else: a = Fi b = Fi1 while n != i: n = n + 1 Fn = b - a b = a a = Fn return Fn # Driver code if __name__ == '__main__': i = 3 Fi = 5 j = -1 Fj = 4 n = 5 print(determineFn(i, Fi, j, Fj, n))
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to calculate kth Fibonacci number
// in the standard Fibonacci sequence
static int fibonacci(int k)
{
int a = 0, b = 1, c = 0;
if (k == 0)
return a;
if (k == 1)
return b;
for (int i = 2; i < k + 1; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
// Function to determine the value of F(n)
static int determineFn(int i, int Fi,
int j, int Fj, int n)
{
if (j < i)
{
// Swap i, j
i = i + j;
j = i - j;
i = i - j;
// swap Fi, Fj
Fi = Fi + Fj;
Fj = Fi - Fj;
Fi = Fi - Fj;
}
// Find the value of F(i + 1)
// from F(i) and F(j)
int Fi1 = (Fj - fibonacci(j - i - 1) * Fi) /
fibonacci(j - i);
// When n is equal to i
int Fn = 0;
if (n == i)
Fn = Fi;
// When n is greater than i
else if (n > i)
{
int b = Fi;
Fn = Fi1;
n = n - 1;
while (n != i)
{
n = n - 1;
int a = b;
b = Fn;
Fn = a + b;
}
}
// When n is smaller than i
else
{
int a = Fi;
int b = Fi1;
while (n != i)
{
n = n + 1;
Fn = b - a;
b = a;
a = Fn;
}
}
return Fn;
}
// Driver Code
public static void Main(String[] args)
{
int i = 3;
int Fi = 5;
int j = -1;
int Fj = 4;
int n = 5;
Console.WriteLine(determineFn(i, Fi, j, Fj, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to calculate kth Fibonacci number
// in the standard Fibonacci sequence
function fibonacci(k)
{
let a = 0, b = 1, c = 0;
if( k == 0)
return a;
if (k == 1)
return b;
for(let i = 2; i < k + 1; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
// Function to determine the value of F(n)
function determineFn(i, Fi, j, Fj, n)
{
if (j < i)
{
// Swap i, j
i = i + j;
j = i - j;
i = i - j;
// swap Fi, Fj
Fi = Fi + Fj;
Fj = Fi - Fj;
Fi = Fi - Fj;
}
// Find the value of F(i + 1)
// from F(i) and F(j)
let Fi1 = parseInt((Fj - fibonacci(j - i - 1) * Fi) /
fibonacci(j - i));
// When n is equal to i
let Fn = 0;
if (n == i)
Fn = Fi;
// When n is greater than i
else if (n > i)
{
let b = Fi;
Fn = Fi1;
n = n - 1;
while (n != i)
{
n = n - 1;
let a = b;
b = Fn;
Fn = a + b;
}
}
// When n is smaller than i
else
{
let a = Fi;
let b = Fi1;
while (n != i)
{
n = n + 1;
Fn = b - a;
b = a;
a = Fn;
}
}
return Fn;
}
// Driver code
let i = 3;
let Fi = 5;
let j = -1;
let Fj = 4;
let n = 5;
document.write(determineFn(i, Fi, j, Fj, n));
</script>
12
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)