El teorema de Zeckendorf establece que cada número entero positivo se puede escribir de forma única como una suma de distintos números de Fibonacci no vecinos. Dos números de Fibonacci son vecinos si van uno tras otro en la secuencia de Fibonacci (0, 1, 1, 2, 3, 5, ..). Por ejemplo, 3 y 5 son vecinos, pero 2 y 5 no lo son.
Dado un número, encuentre una representación del número como suma de números de Fibonacci no consecutivos.
Ejemplos:
Input: n = 10 Output: 8 2 8 and 2 are two non-consecutive Fibonacci Numbers and sum of them is 10. Input: n = 30 Output: 21 8 1 21, 8 and 1 are non-consecutive Fibonacci Numbers and sum of them is 30.
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es usar el Algoritmo Codicioso .
1) Let n be input number
2) While n >= 0
a) Find the greatest Fibonacci Number smaller than n.
Let this number be 'f'. Print 'f'
b) n = n - f
C++
// C++ program for Zeckendorf's theorem. It finds
// representation of n as sum of
// non-neighbouring Fibonacci Numbers.
#include <bits/stdc++.h>
using namespace std;
// Returns the greatest Fibonacci Number smaller than
// or equal to n.
int nearestSmallerEqFib(int n)
{
// Corner cases
if (n == 0 || n == 1)
return n;
// Find the greatest Fibonacci Number smaller
// than n.
int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n)
{
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
// Prints Fibonacci Representation of n using
// greedy algorithm
void printFibRepresntation(int n)
{
while (n > 0)
{
// Find the greates Fibonacci Number smaller
// than or equal to n
int f = nearestSmallerEqFib(n);
// Print the found fibonacci number
cout << f << " ";
// Reduce n
n = n - f;
}
}
// Driver code
int main()
{
int n = 30;
cout << "Non-neighbouring Fibonacci Representation of "
<< n << " is \n";
printFibRepresntation(n);
return 0;
}
Java
// Java program for Zeckendorf's theorem. It finds
// representation of n as sum of non-neighbouring
// Fibonacci Numbers.
class GFG {
public static int nearestSmallerEqFib(int n)
{
// Corner cases
if (n == 0 || n == 1)
return n;
// Find the greatest Fibonacci Number smaller
// than n.
int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
// Prints Fibonacci Representation of n using
// greedy algorithm
public static void printFibRepresntation(int n)
{
while (n > 0) {
// Find the greates Fibonacci Number smaller
// than or equal to n
int f = nearestSmallerEqFib(n);
// Print the found fibonacci number
System.out.print(f + " ");
// Reduce n
n = n - f;
}
}
// Driver method to test
public static void main(String[] args)
{
int n = 30;
System.out.println("Non-neighbouring Fibonacci "
+ " Representation of " + n + " is");
printFibRepresntation(n);
}
}
// Code Contributed by Mohit Gupta_OMG
Python3
# Python program for Zeckendorf's theorem. It finds
# representation of n as sum of non-neighbouring
# Fibonacci Numbers.
# Returns the greatest Fibonacci Number smaller than
# or equal to n.
def nearestSmallerEqFib(n):
# Corner cases
if (n == 0 or n == 1):
return n
# Finds the greatest Fibonacci Number smaller
# than n.
f1, f2, f3 = 0, 1, 1
while (f3 <= n):
f1 = f2;
f2 = f3;
f3 = f1 + f2;
return f2;
# Prints Fibonacci Representation of n using
# greedy algorithm
def printFibRepresntation(n):
while (n>0):
# Find the greates Fibonacci Number smaller
# than or equal to n
f = nearestSmallerEqFib(n);
# Print the found fibonacci number
print (f,end=" ")
# Reduce n
n = n-f
# Driver code test above functions
n = 30
print ("Non-neighbouring Fibonacci Representation of", n, "is")
printFibRepresntation(n)
C#
// C# program for Zeckendorf's theorem.
// It finds the representation of n as
// sum of non-neighbouring Fibonacci
// Numbers.
using System;
class GFG {
public static int nearestSmallerEqFib(int n)
{
// Corner cases
if (n == 0 || n == 1)
return n;
// Find the greatest Fibonacci
// Number smaller than n.
int f1 = 0, f2 = 1, f3 = 1;
while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
// Prints Fibonacci Representation
// of n using greedy algorithm
public static void printFibRepresntation(int n)
{
while (n > 0) {
// Find the greates Fibonacci
// Number smallerthan or equal
// to n
int f = nearestSmallerEqFib(n);
// Print the found fibonacci number
Console.Write(f + " ");
// Reduce n
n = n - f;
}
}
// Driver method
public static void Main()
{
int n = 40;
Console.WriteLine("Non-neighbouring Fibonacci "
+ " Representation of " + n + " is");
printFibRepresntation(n);
}
}
// Code Contributed by vt_m
PHP
<?php
// PHP program for Zeckendorf's theorem.
// It finds representation of n as sum
// of non-neighbouring Fibonacci Numbers.
// Returns the greatest Fibonacci
// Number smaller than or equal
// to n.
function nearestSmallerEqFib($n)
{
// Corner cases
if ($n == 0 || $n==1)
return $n;
// Find the greatest Fibonacci
// Number smaller than n.
$f1 = 0;
$f2 = 1;
$f3 = 1;
while ($f3 <= $n)
{
$f1 = $f2;
$f2 = $f3;
$f3 = $f1 + $f2;
}
return $f2;
}
// Prints Fibonacci Representation
// of n using greedy algorithm
function printFibRepresntation($n)
{
while ($n > 0)
{
// Find the greates Fibonacci
// Number smaller than or
// equal to n
$f = nearestSmallerEqFib($n);
// Print the found
// fibonacci number
echo $f, " ";
// Reduce n
$n = $n - $f;
}
}
// Driver Code
$n = 30;
echo "Non-neighbouring Fibonacci Representation of ",
$n, " is \n";
printFibRepresntation($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program for Zeckendorf's theorem.
// It finds representation of n as sum
// of non-neighbouring Fibonacci Numbers.
// Returns the greatest Fibonacci
// Number smaller than or equal
// to n.
function nearestSmallerEqFib(n)
{
// Corner cases
if (n == 0 || n==1)
return n;
// Find the greatest Fibonacci
// Number smaller than n.
let f1 = 0;
let f2 = 1;
let f3 = 1;
while (f3 <= n)
{
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}
return f2;
}
// Prints Fibonacci Representation
// of n using greedy algorithm
function printFibRepresntation(n)
{
while (n > 0)
{
// Find the greates Fibonacci
// Number smaller than or
// equal to n
let f = nearestSmallerEqFib(n);
// Print the found
// fibonacci number
document.write(f, " ");
// Reduce n
n = n - f;
}
}
// Driver Code
let n = 30;
document.write("Non-neighbouring Fibonacci Representation of " +
n + " is <br>");
printFibRepresntation(n);
// This code is contributed by _saurabh_jaiswal
</script>
Non-neighbouring Fibonacci Representation of 30 is 21 8 1
Complejidad de tiempo: O(N*LogN)
¿Cómo funciona el algoritmo codicioso anterior?
Sea fib(i) [i-ésimo número de Fibonacci] el mayor número de Fibonacci menor o igual que ‘n’.
Entonces n – fib(i) tendrá su propia representación como suma de números de Fibonacci no vecinos.
Todo lo que queremos asegurarnos es que no haya ningún problema vecino. Por inducción, n-fib(i) no tiene un problema vecino, entonces la única forma en que n podría tener un problema vecino es si n-fib(i) usa fib(i-1) en su representación.
Así que todo lo que tenemos que probar es que n-fib(i) no usa fib(i-1) en su representación
. Probémoslo usando la contradicción. Si n-fib(i) = fib(i-1) + fib(ix) +…, entonces fib(i) no puede ser el número de Fibonacci más pequeño más cercano a n, ya que fib(i) + fib(i-1) en sí mismo es fib(i+1).
Entonces, si n-fib(i) contiene fib(i-1) en su representación, entonces fib(i+1) sería el número de fib más pequeño más cercano a n, contradiciendo nuestra suposición de que fib(i) es el número de fib más pequeño más cercano a n .
¿Puede ser útil esta representación?
Como representación binaria. Esta puede ser una representación alternativa para representar números positivos. Una observación importante sobre esta representación es que el número de 1 en la representación de Fibonacci tiende a ser mucho menor que el número de 1 en la representación binaria. Por lo tanto, si en alguna aplicación donde es más costoso almacenar un 1 que almacenar un 0, tendría sentido usar la representación de Fibonacci.
Este artículo es una contribución de Gaurav Saxena . 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