Recuento de formas en que N se puede representar como suma de números de Fibonacci sin repetición

Dado un número N , la tarea es encontrar el número de formas en que el número entero N se puede representar como una suma de números de Fibonacci sin repetición de ningún número de Fibonacci. 

Ejemplos:

Entrada: N = 13
Salida: 3
Explicación: 
Las formas posibles de seleccionar N como 13 son: {13} {8, 5} {8, 3, 2}. Tenga en cuenta que no es posible seleccionar {5 + 5 + 3} porque 5 aparece dos veces.

Entrada: N = 87
Salida : 5
Explicación:
Las formas posibles de seleccionar N como 13 son: {55 + 21 + 8 + 3}, {55 + 21 + 8 + 2 + 1}, {55 + 21 + 5 + 3 + 2 + 1}, {55 + 13 + 8 + 5 + 3 + 2 + 1}, {34 + 21 + 13 + 8 + 5 + 3 + 2 + 1}.

Enfoque ingenuo: la idea ingenua es escribir todas las combinaciones posibles que suman el número N dado . Verifique si alguna combinación tiene enteros repetidos, luego no aumente el contador; de lo contrario, aumente el conteo en 1 cada vez. Devuelve la cuenta al final.

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es utilizar la programación dinámica para optimizar el enfoque anterior. A continuación se muestran los pasos:

• Representemos un número en el código Fibonacci .

Imagine la codificación de Fibonacci de la siguiente manera: el i-ésimo bit del número corresponde al i-ésimo número de Fibonacci . 
Por ejemplo: 16 = 13 + 3 se escribirá como 100100.

• Escriba el código de Fibonacci para cada número positivo tal que no haya dos bits adyacentes que sean 1 .
• Esto es cierto para todos los números porque si hay dos bits adyacentes de 1 bit, podemos transformarlo en un solo bit de 1 bit por propiedad del número de Fibonacci. Llamemos a esta representación como representación canónica.
• Obtener la Representación Canónica . Genere varios números de Fibonacci (alrededor de 90 ) y luego intente restarlos todos en orden decreciente.
• Almacenemos posiciones de 1 bit de la representación canónica de un número dado en una array v en orden creciente y descompongamos cualquier 1 bit en dos 1 bits de la siguiente manera:

Representación canónica inicial: 1000000001
Después de descomponer el 1 bit más a la izquierda en dos 1 bits más pequeños: 0110000001 Después de descomponer el 2.º bit más a la
izquierda en dos 1 bits más pequeños: 0101100001 
Después de descomponer el 3.er bit más a la izquierda en dos 1-bit más pequeños bits: 0101011001
Después de descomponer el cuarto bit más a la izquierda en dos bits más pequeños: 0101010111 

• Después de varias operaciones de este tipo, obtendremos el siguiente bit (o el final del número). Este 1 bit también se puede descomponer, pero solo se puede desplazar un bit.
• Inicializar una array dp dp1[] , dp1[i] es una serie de formas de representar un número que consiste en los 1 bits más a la izquierda del número para el caso en que todos los 1 bits restantes no se descomponen. Además, tome dp2[i], que marca el número de formas de representar un número que consta de los 1 bits más a la izquierda del número para el caso en que se descomponen todos los 1 bits restantes.

Por ejemplo: N= 87

Forma canónica de N = 101010100  
Otras 4 representaciones posibles de N son 101010011, 101001111, 100111111, 011111111

A continuación se muestra la ilustración del mismo:

Por lo tanto, la respuesta es dp1[cnt] + dp2[cnt] , donde cnt es el número total de bits de 1 en la representación canónica.
 

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
long long fib[101], dp1[101];
long long dp2[101], v[101];
 
// Function to generate the
// fibonacci number
void fibonacci()
{
    // First two number of
    // fibonacci sequence
    fib[1] = 1;
    fib[2] = 2;
 
    for (int i = 3; i <= 87; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
 
// Function to find maximum ways to
// represent num as the sum of
// fibonacci number
int find(int num)
{
    int cnt = 0;
 
    // Generate the Canonical form
    // of given number
    for (int i = 87; i > 0; i--) {
        if (num >= fib[i]) {
            v[cnt++] = i;
            num -= fib[i];
        }
    }
 
    // Reverse the number
    reverse(v, v + cnt);
 
    // Base condition of dp1 and dp2
    dp1[0] = 1;
    dp2[0] = (v[0] - 1) / 2;
 
    // Iterate from 1 to cnt
    for (int i = 1; i < cnt; i++) {
 
        // Calculate dp1[]
        dp1[i] = dp1[i - 1] + dp2[i - 1];
 
        // Calculate dp2[]
        dp2[i] = ((v[i] - v[i - 1]) / 2)
                     * dp2[i - 1]
                 + ((v[i] - v[i - 1] - 1) / 2)
                       * dp1[i - 1];
    }
 
    // Return final ans
    return (dp1[cnt - 1] + dp2[cnt - 1]);
}
 
// Driver Code
int main()
{
    // Function call to generate the
    // fibonacci numbers
    fibonacci();
 
    // Given Number
    int num = 13;
 
    // Function Call
    cout << find(num);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static long[] fib = new long[101];
static long[] dp1 = new long[101];
static long[] dp2 = new long[101];
static long[] v = new long[101];
 
// Function to generate the
// fibonacci number
static void fibonacci()
{
     
    // First two number of
    // fibonacci sequence
    fib[1] = 1;
    fib[2] = 2;
 
    for(int i = 3; i <= 87; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
 
// Function to find maximum ways to
// represent num as the sum of
// fibonacci number
static long find(int num)
{
    int cnt = 0;
 
    // Generate the Canonical form
    // of given number
    for(int i = 87; i > 0; i--)
    {
        if (num >= fib[i])
        {
            v[cnt++] = i;
            num -= fib[i];
        }
    }
 
    // Reverse the number
    for(int i = 0; i < cnt / 2; i++)
    {
        long t = v[i];
        v[i] = v[cnt - i - 1];
        v[cnt - i - 1] = t;
    }
     
    // Base condition of dp1 and dp2
    dp1[0] = 1;
    dp2[0] = (v[0] - 1) / 2;
 
    // Iterate from 1 to cnt
    for(int i = 1; i < cnt; i++)
    {
         
        // Calculate dp1[]
        dp1[i] = dp1[i - 1] + dp2[i - 1];
 
        // Calculate dp2[]
        dp2[i] = ((v[i] - v[i - 1]) / 2) *
                 dp2[i - 1] +
                 ((v[i] - v[i - 1] - 1) / 2) *
                 dp1[i - 1];
    }
 
    // Return final ans
    return (dp1[cnt - 1] + dp2[cnt - 1]);
}
 
// Driver code
public static void main (String[] args)
{
     
    // Function call to generate the
    // fibonacci numbers
    fibonacci();
     
    // Given number
    int num = 13;
     
    // Function call
    System.out.print(find(num));
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
fib = [0] * 101
dp1 = [0] * 101
dp2 = [0] * 101
v = [0] * 101
 
# Function to generate the
# fibonacci number
def fibonacci():
 
    # First two number of
    # fibonacci sequence
    fib[1] = 1
    fib[2] = 2
 
    for i in range(3, 87 + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
 
# Function to find maximum ways to
# represent num as the sum of
# fibonacci number
def find(num):
 
    cnt = 0
 
    # Generate the Canonical form
    # of given number
    for i in range(87, 0, -1):
        if(num >= fib[i]):
            v[cnt] = i
            cnt += 1
            num -= fib[i]
 
    # Reverse the number
    v[::-1]
 
    # Base condition of dp1 and dp2
    dp1[0] = 1
    dp2[0] = (v[0] - 1) // 2
 
    # Iterate from 1 to cnt
    for i in range(1, cnt):
 
        # Calculate dp1[]
        dp1[i] = dp1[i - 1] + dp2[i - 1]
 
        # Calculate dp2[]
        dp2[i] = (((v[i] - v[i - 1]) // 2) *
                  dp2[i - 1] +
                  ((v[i] - v[i - 1] - 1) // 2) *
                  dp1[i - 1])
 
    # Return final ans
    return dp1[cnt - 1] + dp2[cnt - 1]
 
# Driver Code
 
# Function call to generate the
# fibonacci numbers
fibonacci()
 
# Given number
num = 13
 
# Function call
print(find(num))
 
# This code is contributed by Shivam Singh

// C# program for the above approach
using System;
 
class GFG{
 
static long[] fib = new long[101];
static long[] dp1 = new long[101]; 
static long[] dp2 = new long[101];
static long[] v = new long[101]; 
   
// Function to generate the 
// fibonacci number 
static void fibonacci() 
{
     
    // First two number of 
    // fibonacci sequence 
    fib[1] = 1; 
    fib[2] = 2; 
   
    for(int i = 3; i <= 87; i++)
    { 
        fib[i] = fib[i - 1] + fib[i - 2]; 
    } 
} 
   
// Function to find maximum ways to 
// represent num as the sum of 
// fibonacci number 
static long find(long num) 
{ 
    int cnt = 0; 
   
    // Generate the Canonical form 
    // of given number 
    for(int i = 87; i > 0; i--) 
    { 
        if (num >= fib[i])
        { 
            v[cnt++] = i; 
            num -= fib[i]; 
        } 
    } 
   
    // Reverse the number 
    for(int i = 0; i < cnt / 2; i++)
    { 
        long t = v[i]; 
        v[i] = v[cnt - i - 1]; 
        v[cnt - i - 1] = t; 
    }
       
    // Base condition of dp1 and dp2 
    dp1[0] = 1; 
    dp2[0] = (v[0] - 1) / 2; 
   
    // Iterate from 1 to cnt 
    for(int i = 1; i < cnt; i++)
    { 
           
        // Calculate dp1[] 
        dp1[i] = dp1[i - 1] + dp2[i - 1]; 
   
        // Calculate dp2[] 
        dp2[i] = ((v[i] - v[i - 1]) / 2) * 
                 dp2[i - 1] +
                 ((v[i] - v[i - 1] - 1) / 2) * 
                 dp1[i - 1]; 
    } 
   
    // Return final ans 
    return (dp1[cnt - 1] + dp2[cnt - 1]); 
} 
 
// Driver code
static void Main()
{
     
    // Function call to generate the 
    // fibonacci numbers 
    fibonacci(); 
       
    // Given number 
    int num = 13; 
       
    // Function call 
    Console.Write(find(num));
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
 
// Javascript program for the above approach
var fib = Array(101).fill(0);
var dp1 = Array(101).fill(0);
var dp2 = Array(101).fill(0);
var v = Array(101).fill(0);
 
// Function to generate the
// fibonacci number
function fibonacci()
{
     
    // First two number of
    // fibonacci sequence
    fib[1] = 1;
    fib[2] = 2;
 
    for(i = 3; i <= 87; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}
 
// Function to find maximum ways to
// represent num as the sum of
// fibonacci number
function find(num)
{
    var cnt = 0;
     
    // Generate the Canonical form
    // of given number
    for(i = 87; i > 0; i--)
    {
        if (num >= fib[i])
        {
            v[cnt++] = i;
            num -= fib[i];
        }
    }
 
    // Reverse the number
    for(i = 0; i < cnt / 2; i++)
    {
        var t = v[i];
        v[i] = v[cnt - i - 1];
        v[cnt - i - 1] = t;
    }
 
    // Base condition of dp1 and dp2
    dp1[0] = 1;
    dp2[0] = parseInt((v[0] - 1) / 2);
 
    // Iterate from 1 to cnt
    for(i = 1; i < cnt; i++)
    {
         
        // Calculate dp1
        dp1[i] = dp1[i - 1] + dp2[i - 1];
 
        // Calculate dp2
        dp2[i] = parseInt((v[i] - v[i - 1]) /
                           2) * dp2[i - 1] +
                 parseInt((v[i] - v[i - 1] - 1) /
                           2) * dp1[i - 1];
    }
 
    // Return final ans
    return (dp1[cnt - 1] + dp2[cnt - 1]);
}
 
// Driver code
 
// Function call to generate the
// fibonacci numbers
fibonacci();
 
// Given number
var num = 13;
 
// Function call
document.write(find(num));
 
// This code is contributed by todaysgaurav
 
</script>

3

Complejidad temporal: O(log N)
Espacio auxiliar: O(log N)