La codificación de Fibonacci codifica un número entero en un número binario utilizando la Representación de Fibonacci del número. La idea se basa en el teorema de Zeckendorf, que establece que todo número entero positivo se puede escribir de forma única como una suma de números de Fibonacci distintos no vecinos (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..).
La palabra clave de Fibonacci para un número entero en particular es exactamente la representación de Zeckendorf del número entero con el orden de sus dígitos invertido y un «1» adicional agregado al final. El 1 adicional se agrega para indicar el final del código (tenga en cuenta que el código nunca contiene dos 1 consecutivos según el teorema de Zeckendorf . La representación usa números de Fibonacci que comienzan en 1 (2º número de Fibonacci). Por lo tanto, los números de Fibonacci utilizados son 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, …….
Dado un número n, imprime su código Fibonacci.
Ejemplos:
Input: n = 1 Output: 11 1 is first Fibonacci number in this representation and an extra 1 is appended at the end. Input: n = 11 Output: 001011 11 is sum of 8 and 3. The last 1 represents extra 1 that is always added. A 1 before it represents 8. The third 1 (from beginning) represents 3.
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
El siguiente algoritmo toma un número entero como entrada y genera una string que almacena la codificación Fibonacci.
Encuentre el mayor número de Fibonacci f menor o igual a n. Digamos que es el i-ésimo número de la serie de Fibonacci. La longitud de la palabra clave para n será de i+3 caracteres (uno para 1 extra añadido al final, uno porque i es un índice y otro para ‘\0’). Suponiendo que se almacena la serie de Fibonacci:
- Sea f el Fibonacci más grande menor o igual que n, anteponga ‘1’ en la string binaria. Esto indica el uso de f en representación de n. Resta f de n: n = n – f
- De lo contrario, si f es mayor que n, anteponga ‘0’ a la string binaria.
- Muévase al número de Fibonacci un poco más pequeño que f .
- Repetir hasta cero resto (n = 0)
- Agregue un ‘1’ adicional a la string binaria. Obtenemos una codificación tal que dos 1 consecutivos indican el final de un número (y el comienzo del siguiente).
A continuación se muestra la implementación del algoritmo anterior.
C++
/* C++ program for Fibonacci Encoding of a positive integer n */
#include <bits/stdc++.h>
using namespace std;
// To limit on the largest Fibonacci number to be used
#define N 30
/* Array to store fibonacci numbers. fib[i] is going
to store (i+2)'th Fibonacci number*/
int fib[N];
// Stores values in fib and returns index of the largest
// fibonacci number smaller than n.
int largestFiboLessOrEqual(int n)
{
fib[0] = 1; // Fib[0] stores 2nd Fibonacci No.
fib[1] = 2; // Fib[1] stores 3rd Fibonacci No.
// Keep Generating remaining numbers while previously
// generated number is smaller
int i;
for (i=2; fib[i-1]<=n; i++)
fib[i] = fib[i-1] + fib[i-2];
// Return index of the largest fibonacci number
// smaller than or equal to n. Note that the above
// loop stopped when fib[i-1] became larger.
return (i-2);
}
/* Returns pointer to the char string which corresponds to
code for n */
char* fibonacciEncoding(int n)
{
int index = largestFiboLessOrEqual(n);
//allocate memory for codeword
char *codeword = (char*)malloc(sizeof(char)*(index+3));
// index of the largest Fibonacci f <= n
int i = index;
while (n)
{
// Mark usage of Fibonacci f (1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used (0 bit),
// progress backwards
while (i>=0 && fib[i]>n)
{
codeword[i] = '0';
i = i - 1;
}
}
//additional '1' bit
codeword[index+1] = '1';
codeword[index+2] = '\0';
//return pointer to codeword
return codeword;
}
/* driver function */
int main()
{
int n = 143;
cout <<"Fibonacci code word for " <<n <<" is " << fibonacciEncoding(n);
return 0;
}
// This code is contributed by shivanisinghss2110
C
/* C program for Fibonacci Encoding of a positive integer n */
#include<stdio.h>
#include<stdlib.h>
// To limit on the largest Fibonacci number to be used
#define N 30
/* Array to store fibonacci numbers. fib[i] is going
to store (i+2)'th Fibonacci number*/
int fib[N];
// Stores values in fib and returns index of the largest
// fibonacci number smaller than n.
int largestFiboLessOrEqual(int n)
{
fib[0] = 1; // Fib[0] stores 2nd Fibonacci No.
fib[1] = 2; // Fib[1] stores 3rd Fibonacci No.
// Keep Generating remaining numbers while previously
// generated number is smaller
int i;
for (i=2; fib[i-1]<=n; i++)
fib[i] = fib[i-1] + fib[i-2];
// Return index of the largest fibonacci number
// smaller than or equal to n. Note that the above
// loop stopped when fib[i-1] became larger.
return (i-2);
}
/* Returns pointer to the char string which corresponds to
code for n */
char* fibonacciEncoding(int n)
{
int index = largestFiboLessOrEqual(n);
//allocate memory for codeword
char *codeword = (char*)malloc(sizeof(char)*(index+3));
// index of the largest Fibonacci f <= n
int i = index;
while (n)
{
// Mark usage of Fibonacci f (1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used (0 bit),
// progress backwards
while (i>=0 && fib[i]>n)
{
codeword[i] = '0';
i = i - 1;
}
}
//additional '1' bit
codeword[index+1] = '1';
codeword[index+2] = '\0';
//return pointer to codeword
return codeword;
}
/* driver function */
int main()
{
int n = 143;
printf("Fibonacci code word for %d is %s\n", n, fibonacciEncoding(n));
return 0;
}
Java
// Java program for Fibonacci Encoding
// of a positive integer n
import java.io.*;
class GFG{
// To limit on the largest Fibonacci
// number to be used
public static int N = 30;
// Array to store fibonacci numbers.
// fib[i] is going to store (i+2)'th
// Fibonacci number
public static int[] fib = new int[N];
// Stores values in fib and returns index of
// the largest fibonacci number smaller than n.
public static int largestFiboLessOrEqual(int n)
{
// Fib[0] stores 2nd Fibonacci No.
fib[0] = 1;
// Fib[1] stores 3rd Fibonacci No.
fib[1] = 2;
// Keep Generating remaining numbers while
// previously generated number is smaller
int i;
for(i = 2; fib[i - 1] <= n; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
// Return index of the largest fibonacci
// number smaller than or equal to n.
// Note that the above loop stopped when
// fib[i-1] became larger.
return(i - 2);
}
// Returns pointer to the char string which
// corresponds to code for n
public static String fibonacciEncoding(int n)
{
int index = largestFiboLessOrEqual(n);
// Allocate memory for codeword
char[] codeword = new char[index + 3];
// Index of the largest Fibonacci f <= n
int i = index;
while (n > 0)
{
// Mark usage of Fibonacci f(1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used
// (0 bit), progress backwards
while (i >= 0 && fib[i] > n)
{
codeword[i] = '0';
i = i - 1;
}
}
// Additional '1' bit
codeword[index + 1] = '1';
codeword[index + 2] = '\0';
String string = new String(codeword);
// Return pointer to codeword
return string;
}
// Driver code
public static void main(String[] args)
{
int n = 143;
System.out.println("Fibonacci code word for " +
n + " is " + fibonacciEncoding(n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for Fibonacci Encoding
# of a positive integer n
# To limit on the largest
# Fibonacci number to be used
N = 30
# Array to store fibonacci numbers.
# fib[i] is going to store
# (i+2)'th Fibonacci number
fib = [0 for i in range(N)]
# Stores values in fib and returns index of
# the largest fibonacci number smaller than n.
def largestFiboLessOrEqual(n):
fib[0] = 1 # Fib[0] stores 2nd Fibonacci No.
fib[1] = 2 # Fib[1] stores 3rd Fibonacci No.
# Keep Generating remaining numbers while
# previously generated number is smaller
i = 2
while fib[i - 1] <= n:
fib[i] = fib[i - 1] + fib[i - 2]
i += 1
# Return index of the largest fibonacci number
# smaller than or equal to n. Note that the above
# loop stopped when fib[i-1] became larger.
return (i - 2)
# Returns pointer to the char string which
# corresponds to code for n
def fibonacciEncoding(n):
index = largestFiboLessOrEqual(n)
# allocate memory for codeword
codeword = ['a' for i in range(index + 2)]
# index of the largest Fibonacci f <= n
i = index
while (n):
# Mark usage of Fibonacci f (1 bit)
codeword[i] = '1'
# Subtract f from n
n = n - fib[i]
# Move to Fibonacci just smaller than f
i = i - 1
# Mark all Fibonacci > n as not used (0 bit),
# progress backwards
while (i >= 0 and fib[i] > n):
codeword[i] = '0'
i = i - 1
# additional '1' bit
codeword[index + 1] = '1'
# return pointer to codeword
return "".join(codeword)
# Driver Code
n = 143
print("Fibonacci code word for", n,
"is", fibonacciEncoding(n))
# This code is contributed by Mohit Kumar
C#
// C# program for Fibonacci Encoding
// of a positive integer n
using System;
class GFG{
// To limit on the largest Fibonacci
// number to be used
public static int N = 30;
// Array to store fibonacci numbers.
// fib[i] is going to store (i+2)'th
// Fibonacci number
public static int[] fib = new int[N];
// Stores values in fib and returns index of
// the largest fibonacci number smaller than n.
public static int largestFiboLessOrEqual(int n)
{
// Fib[0] stores 2nd Fibonacci No.
fib[0] = 1;
// Fib[1] stores 3rd Fibonacci No.
fib[1] = 2;
// Keep Generating remaining numbers while
// previously generated number is smaller
int i;
for(i = 2; fib[i - 1] <= n; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
// Return index of the largest fibonacci
// number smaller than or equal to n.
// Note that the above loop stopped when
// fib[i-1] became larger.
return(i - 2);
}
// Returns pointer to the char string which
// corresponds to code for n
public static String fibonacciEncoding(int n)
{
int index = largestFiboLessOrEqual(n);
// Allocate memory for codeword
char[] codeword = new char[index + 3];
// Index of the largest Fibonacci f <= n
int i = index;
while (n > 0)
{
// Mark usage of Fibonacci f(1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used
// (0 bit), progress backwards
while (i >= 0 && fib[i] > n)
{
codeword[i] = '0';
i = i - 1;
}
}
// Additional '1' bit
codeword[index + 1] = '1';
codeword[index + 2] = '\0';
string str = new string(codeword);
// Return pointer to codeword
return str;
}
// Driver code
static public void Main()
{
int n = 143;
Console.WriteLine("Fibonacci code word for " +
n + " is " + fibonacciEncoding(n));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for Fibonacci Encoding
// of a positive integer n
// To limit on the largest Fibonacci
// number to be used
let N = 30;
// Array to store fibonacci numbers.
// fib[i] is going to store (i+2)'th
// Fibonacci number
let fib = new Array(N);
// Stores values in fib and returns index of
// the largest fibonacci number smaller than n.
function largestFiboLessOrEqual(n)
{
// Fib[0] stores 2nd Fibonacci No.
fib[0] = 1;
// Fib[1] stores 3rd Fibonacci No.
fib[1] = 2;
// Keep Generating remaining numbers while
// previously generated number is smaller
let i;
for(i = 2; fib[i - 1] <= n; i++)
{
fib[i] = fib[i - 1] + fib[i - 2];
}
// Return index of the largest fibonacci
// number smaller than or equal to n.
// Note that the above loop stopped when
// fib[i-1] became larger.
return(i - 2);
}
// Returns pointer to the char string which
// corresponds to code for n
function fibonacciEncoding(n)
{
let index = largestFiboLessOrEqual(n);
// Allocate memory for codeword
let codeword = new Array(index + 3);
// Index of the largest Fibonacci f <= n
let i = index;
while (n > 0)
{
// Mark usage of Fibonacci f(1 bit)
codeword[i] = '1';
// Subtract f from n
n = n - fib[i];
// Move to Fibonacci just smaller than f
i = i - 1;
// Mark all Fibonacci > n as not used
// (0 bit), progress backwards
while (i >= 0 && fib[i] > n)
{
codeword[i] = '0';
i = i - 1;
}
}
// Additional '1' bit
codeword[index + 1] = '1';
codeword[index + 2] = '\0';
let string =(codeword).join("");
// Return pointer to codeword
return string;
}
// Driver code
let n = 143;
document.write("Fibonacci code word for " +
n + " is " + fibonacciEncoding(n));
// This code is contributed by unknown2108
</script>
Producción:
Fibonacci code word for 143 is 01010101011
Ilustración
Campo de aplicación:
Procesamiento y compresión de datos: representar los datos (que pueden ser texto, imagen, video…) de tal manera que el espacio necesario para almacenar o transmitir datos sea menor que el tamaño de los datos de entrada. Los métodos estadísticos usan códigos de longitud variable, con los códigos más cortos asignados a símbolos o grupos de símbolos que tienen una mayor probabilidad de ocurrencia. Si los códigos se van a utilizar en un canal de comunicación ruidoso, su resistencia a las inserciones, eliminaciones y cambios de bits es de gran importancia.
Lea más sobre la aplicación aquí .
Este artículo es una contribución de Yash Varyani . 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