Dados dos números K y N . La tarea es representar el número K dado como una suma de varios números N-bonacci .
Ejemplos:
Entrada: K = 21, N = 5
Salida: 3
Los tres números de los 5-bonacci son: 16, 4, 1.
Explicación:
Para N = 5, la serie será: 1, 1, 2, 4, 8 , 16, 31, 61, 120, etc. Los tres números 16, 4 y 1 suman 21.Entrada: K = 500, N = 43
Salida: 6
Los números de 43-bonacci que suman 500 son: 256 128 64 32 16 4
Enfoque ingenuo:
el enfoque más simple es generar la serie N-bonacci de hasta 50 términos y almacenar sus valores en una array. Encuentre el subconjunto de la array que tiene la suma dada e imprima el tamaño del subconjunto.
Complejidad del tiempo: O(2 N )
Enfoque eficiente : este enfoque se basa en el enfoque eficiente sobre cómo formar números de N-bonacci, discutido en este artículo .
Siga los pasos a continuación para resolver el problema:
- Genere la serie N-bonacci y almacene los valores en una array, digamos N_bonacci[] . (hasta 50 términos)
- Inicialice otra array, ans[] , para guardar los números de la serie cuya suma es K .
- Recorra la array N-bonacci en el orden inverso y siga comprobando si, K – N_bonacci[i] >= 0 . Si es verdadero, empuje N_bonacci[i] a la array ans y reduzca K a K – N_bonacci[i] .
- Continúe disminuyendo K hasta que se convierta en 0 y, finalmente, genere el tamaño y los elementos de la array ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
// array to store the N-Bonacci series
long long N_bonacci[100];
// Function to express K as sum of
// several N_bonacci numbers
void N_bonacci_nums(int n, int k)
{
N_bonacci[0] = 1;
for (int i = 1; i <= 50; ++i) {
for (int j = i - 1;
j >= i - k and j >= 0;
--j)
N_bonacci[i]
+= N_bonacci[j];
}
vector<long long> ans;
for (int i = 50; i >= 0; --i)
if (n - N_bonacci[i] >= 0) {
ans.push_back(N_bonacci[i]);
n -= N_bonacci[i];
}
if (ans.size() == 1)
ans.push_back(0);
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); ++i)
cout << ans[i] << ", ";
}
// Driver code
int main()
{
int n = 21, k = 5;
N_bonacci_nums(n, k);
return 0;
}
Java
// Java program for the above problem
import java.util.*;
class GFG{
// Array to store the N-Bonacci series
public static long []N_bonacci= new long [100];
// Function to express K as sum of
// several N_bonacci numbers
@SuppressWarnings("unchecked")
public static void N_bonacci_nums(int n, int k)
{
N_bonacci[0] = 1;
for(int i = 1; i <= 50; ++i)
{
for(int j = i - 1;
j >= i - k && j >= 0 ;--j)
N_bonacci[i]+= N_bonacci[j];
}
Vector ans = new Vector();
for(int i = 50; i >= 0; --i)
if (n - N_bonacci[i] >= 0)
{
ans.add(N_bonacci[i]);
n -= N_bonacci[i];
}
if (ans.size() == 1)
ans.add(0);
System.out.println(ans.size());
for(int i = 0; i < ans.size(); ++i)
System.out.print(ans.get(i) + ", ");
}
// Driver code
public static void main(String args[])
{
int n = 21, k = 5;
N_bonacci_nums(n, k);
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 program for the above problem # Array to store the N-Bonacci series N_bonacci = [0] * 100 # Function to express K as sum of # several N_bonacci numbers def N_bonacci_nums(n, k): N_bonacci[0] = 1 for i in range(1, 51): j = i - 1 while j >= i - k and j >= 0: N_bonacci[i] += N_bonacci[j] j -= 1 ans = [] for i in range(50, -1, -1): if (n - N_bonacci[i] >= 0): ans.append(N_bonacci[i]) n -= N_bonacci[i] if (len(ans) == 1): ans.append(0) print(len(ans)) for i in ans: print(i, end = ", ") # Driver code if __name__ == '__main__': n = 21 k = 5 N_bonacci_nums(n, k) # This code is contributed by mohit kumar 29
C#
// C# program for the above problem
using System;
using System.Collections.Generic;
class GFG{
// Array to store the N-Bonacci series
public static long []N_bonacci = new long [100];
// Function to express K as sum of
// several N_bonacci numbers
static void N_bonacci_nums(long n, long k)
{
N_bonacci[0] = 1;
for(int i = 1; i <= 50; ++i)
{
for(int j = i - 1;
j >= i - k && j >= 0; --j)
N_bonacci[i] += N_bonacci[j];
}
List<long> ans = new List<long>();
for(int i = 50; i >= 0; --i)
if (n - N_bonacci[i] >= 0)
{
ans.Add(N_bonacci[i]);
n -= N_bonacci[i];
}
if (ans.Count == 1)
ans.Add(0);
Console.WriteLine(ans.Count);
for(int i = 0; i < ans.Count; ++i)
Console.Write(ans[i] + ", ");
}
// Driver code
static void Main()
{
long n = 21, k = 5;
N_bonacci_nums(n, k);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above problem
// Array to store the N-Bonacci series
let N_bonacci= new Array(100);
for(let i = 0; i < 100; i++)
{
N_bonacci[i] = 0;
}
// Function to express K as sum of
// several N_bonacci numbers
function N_bonacci_nums(n, k)
{
N_bonacci[0] = 1;
for(let i = 1; i <= 50; ++i)
{
for(let j = i - 1;
j >= i - k && j >= 0 ;--j)
N_bonacci[i]+= N_bonacci[j];
}
let ans = [];
for(let i = 50; i >= 0; --i)
if (n - N_bonacci[i] >= 0)
{
ans.push(N_bonacci[i]);
n -= N_bonacci[i];
}
if (ans.length == 1)
ans.push(0);
document.write(ans.length+"<br>");
for(let i = 0; i < ans.length; ++i)
document.write(ans[i] + ", ");
}
// Driver code
let n = 21, k = 5;
N_bonacci_nums(n, k);
// This code is contributed by unknown2108
</script>
3 16, 4, 1,
Complejidad de Tiempo: O(K * K)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA