Dado un número entero N (menos de 10^6), la tarea es encontrar un par de números de Fibonacci cuya suma sea igual al N dado , y la diferencia absoluta entre el par elegido sea mínima.
Imprime -1 si no hay solución.
Ejemplos:
Entrada: N = 199
Salida: 55 144
Explicación
199 se puede representar como la suma de 55 y 144 que tiene la diferencia mínima.
Entrada: N = 1830
Salida: 233 1597
Explicación
1830 se puede representar como la suma de 233 y 1597 que tiene la diferencia mínima.
Enfoque: La idea es usar hashing para precalcular y almacenar los Nodes de Fibonacci hasta el valor máximo para que la verificación sea fácil y eficiente (en tiempo O(1)).
Después de precalcular el hash :
- Inicie un bucle de (N / 2) a 1 (para minimizar la diferencia absoluta) y verifique si el contador de bucle ‘i’ y ‘N – i’ son ambos Fibonacci.
- Si son Fibonacci, los imprimiremos y saldremos del bucle.
- Si el número N no se puede representar como la suma de dos números de Fibonacci, imprimiremos -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the pair of
// Fibonacci numbers with a given sum
// and minimum absolute difference
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000005
// Hash to store all the
// Fibonacci numbers
set<int> fib;
// Function to generate fibonacci Series
// and create hash table
// to check Fibonacci numbers
void fibonacci()
{
// Adding the first two Fibonacci
// numbers into the Hash set
int prev = 0, curr = 1, len = 2;
fib.insert(prev);
fib.insert(curr);
// Computing the remaining Fibonacci
// numbers based on the previous
// two numbers
while (len <= MAX) {
int temp = curr + prev;
fib.insert(temp);
prev = curr;
curr = temp;
len++;
}
}
// Function to find the pair of
// Fibonacci numbers with the given
// sum and minimum absolute difference
void findFibonacci(int N)
{
// Start from N/2 such that the
// difference between i and
// N - i will be minimum
for (int i = N / 2; i > 1; i--) {
// If both 'i' and 'sum - i' are
// fibonacci numbers then print
// them and break the loop
if (fib.find(i) != fib.end()
&& fib.find(N - i) != fib.end()) {
cout << i << " " << (N - i) << endl;
return;
}
}
// If there is no Fibonacci pair
// possible
cout << "-1" << endl;
}
// Driver code
int main()
{
// Generate the Fibonacci numbers
fibonacci();
int sum = 199;
// Find the Fibonacci pair
findFibonacci(sum);
return 0;
}
Java
// Java program to find the pair of
// Fibonacci numbers with a given sum
// and minimum absolute difference
import java.util.*;
class GFG{
// Hash to store all the
// Fibonacci numbers
static int MAX=1000005;
static Set<Integer> fib=new HashSet<Integer>();
// Function to generate fibonacci Series
// and create hash table
// to check Fibonacci numbers
static void fibonacci()
{
// Adding the first two Fibonacci
// numbers into the Hash set
int prev = 0, curr = 1, len = 2;
fib.add(prev);
fib.add(curr);
// Computing the remaining Fibonacci
// numbers based on the previous
// two numbers
while (len <= MAX) {
int temp = curr + prev;
fib.add(temp);
prev = curr;
curr = temp;
len++;
}
}
// Function to find the pair of
// Fibonacci numbers with the given
// sum and minimum absolute difference
static void findFibonacci(int N)
{
// Start from N/2 such that the
// difference between i and
// N - i will be minimum
for (int i = N / 2; i > 1; i--) {
// If both 'i' and 'sum - i' are
// fibonacci numbers then print
// them and break the loop
if (fib.contains(i) && fib.contains(N - i)) {
System.out.println(i+" "+(N - i));
return;
}
}
// If there is no Fibonacci pair
// possible
System.out.println("-1");
}
// Driver code
public static void main(String args[])
{
// Generate the Fibonacci numbers
fibonacci();
int sum = 199;
// Find the Fibonacci pair
findFibonacci(sum);
}
}
// This code is contributed by AbhiThakur
Python3
# Python 3 program to find
# the pair of Fibonacci numbers
# with a given sum and minimum
# absolute difference
MAX = 10005
# Hash to store all the
# Fibonacci numbers
fib = set()
# Function to generate
# fibonacci Series and
# create hash table
# to check Fibonacci
# numbers
def fibonacci():
global fib
global MAX
# Adding the first
# two Fibonacci numbers
# into the Hash set
prev = 0
curr = 1
l = 2
fib.add(prev)
fib.add(curr)
# Computing the remaining
# Fibonacci numbers based
# on the previous two numbers
while(l <= MAX):
temp = curr + prev
fib.add(temp)
prev = curr
curr = temp
l += 1
# Function to find the
# pair of Fibonacci numbers
# with the given sum and
# minimum absolute difference
def findFibonacci(N):
global fib
# Start from N/2 such
# that the difference
# between i and N - i
# will be minimum
i = N//2
while(i > 1):
# If both 'i' and 'sum - i'
# are fibonacci numbers then
# print them and break the loop
if (i in fib and
(N - i) in fib):
print(i, (N - i))
return
i -= 1
# If there is no Fibonacci
# pair possible
print("-1")
# Driver code
if __name__ == '__main__':
# Generate the Fibonacci
# numbers
fibonacci()
sum = 199
# Find the Fibonacci pair
findFibonacci(sum)
# This code is contributed by bgangwar59
C#
// C# program to find the pair of
// Fibonacci numbers with a given sum
// and minimum absolute difference
using System;
using System.Collections.Generic;
class GFG{
// Hash to store all the
// Fibonacci numbers
static int MAX=100005;
static HashSet<int> fib=new HashSet<int>();
// Function to generate fibonacci Series
// and create hash table
// to check Fibonacci numbers
static void fibonacci()
{
// Adding the first two Fibonacci
// numbers into the Hash set
int prev = 0, curr = 1, len = 2;
fib.Add(prev);
fib.Add(curr);
// Computing the remaining Fibonacci
// numbers based on the previous
// two numbers
while (len <= MAX) {
int temp = curr + prev;
fib.Add(temp);
prev = curr;
curr = temp;
len++;
}
}
// Function to find the pair of
// Fibonacci numbers with the given
// sum and minimum absolute difference
static void findFibonacci(int N)
{
// Start from N/2 such that the
// difference between i and
// N - i will be minimum
for (int i = N / 2; i > 1; i--) {
// If both 'i' and 'sum - i' are
// fibonacci numbers then print
// them and break the loop
if (fib.Contains(i) && fib.Contains(N - i)) {
Console.WriteLine(i+" "+(N - i));
return;
}
}
// If there is no Fibonacci pair
// possible
Console.WriteLine("-1");
}
// Driver code
public static void Main(String []args)
{
// Generate the Fibonacci numbers
fibonacci();
int sum = 199;
// Find the Fibonacci pair
findFibonacci(sum);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program to find the pair of
// Fibonacci numbers with a given sum
// and minimum absolute difference
// Hash to store all the
// Fibonacci numbers
let MAX=1000005;
let fib=new Set();
// Function to generate fibonacci Series
// and create hash table
// to check Fibonacci numbers
function fibonacci()
{
// Adding the first two Fibonacci
// numbers into the Hash set
let prev = 0, curr = 1, len = 2;
fib.add(prev);
fib.add(curr);
// Computing the remaining Fibonacci
// numbers based on the previous
// two numbers
while (len <= MAX) {
let temp = curr + prev;
fib.add(temp);
prev = curr;
curr = temp;
len++;
}
}
// Function to find the pair of
// Fibonacci numbers with the given
// sum and minimum absolute difference
function findFibonacci(N)
{
// Start from N/2 such that the
// difference between i and
// N - i will be minimum
for (let i = Math.floor(N / 2); i > 1; i--) {
// If both 'i' and 'sum - i' are
// fibonacci numbers then print
// them and break the loop
if (fib.has(i) && fib.has(N - i)) {
document.write(i+" "+(N - i));
return;
}
}
// If there is no Fibonacci pair
// possible
document.write("-1");
}
// Driver code
// Generate the Fibonacci numbers
fibonacci();
let sum = 199;
// Find the Fibonacci pair
findFibonacci(sum);
// This code is contributed by sanjoy_62.
</script>
Producción:
55 144
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA