Dados dos números N y K. Encuentra el número de formas de representar N como la suma de K números de Fibonacci.
Ejemplos :
Input : n = 12, k = 1 Output : 0 Input : n = 13, k = 3 Output : 2 Explanation : 2 + 3 + 8, 3 + 5 + 5.
Enfoque: La serie de Fibonacci es f(0)=1, f(1)=2 y f(i)=f(i-1)+f(i-2) para i>1. Supongamos que F(x, k, n) es el número de formas de formar la suma x usando exactamente k números de f(0), f(1), …f(n-1). Para encontrar una recurrencia para F(x, k, n), observe que hay dos casos: si f(n-1) en la suma o no.
- Si f(n-1) no está en la suma, entonces x se forma como una suma usando exactamente k números de f(0), f(1), …, f(n-2).
- Si f(n-1) está en la suma, entonces el xf(n-1) restante se forma usando exactamente k-1 números de f(0), f(1), …, f(n-1). (Observe que f(n-1) aún se incluye porque se permiten números duplicados).
Entonces la relación de recurrencia será:
F(x, k, n)= F(x, k, n-1)+F(xf(n-1), k-1, n)
Casos base:
- Si k=0, entonces hay cero números de la serie, por lo que la suma solo puede ser 0. Por lo tanto, F(0, 0, n)=1.
- F(x, 0, n)=0, si x no es igual a 0.
Además, hay otros casos que hacen que F(x, k, n)=0, como el siguiente:
- Si k>0 y x=0 porque tener al menos un número positivo debe dar como resultado una suma positiva.
- Si k>0 y n=0 porque no queda ninguna elección posible de números.
- Si x<0 porque no hay forma de formar una suma negativa usando un número finito de números no negativos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// to store fibonacci numbers
// 42 second number in fibonacci series
// largest possible integer
int fib[43] = { 0 };
// Function to generate fibonacci series
void fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
// Recursive function to return the
// number of ways
int rec(int x, int y, int last)
{
// base condition
if (y == 0) {
if (x == 0)
return 1;
return 0;
}
int sum = 0;
// for recursive function call
for (int i = last; i >= 0 and fib[i] * y >= x; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], y - 1, i);
}
return sum;
}
// Driver code
int main()
{
fibonacci();
int n = 13, k = 3;
cout << "Possible ways are: "
<< rec(n, k, 42);
return 0;
}
C
// C implementation of above approach
#include <stdio.h>
// to store fibonacci numbers
// 42 second number in fibonacci series
// largest possible integer
int fib[43] = { 0 };
// Function to generate fibonacci series
void fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
// Recursive function to return the
// number of ways
int rec(int x, int y, int last)
{
// base condition
if (y == 0) {
if (x == 0)
return 1;
return 0;
}
int sum = 0;
// for recursive function call
for (int i = last; i >= 0 && fib[i] * y >= x; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], y - 1, i);
}
return sum;
}
// Driver code
int main()
{
fibonacci();
int n = 13, k = 3;
printf("Possible ways are: %d",rec(n, k, 42));
return 0;
}
// This code is contributed by kothavvsaakash.
Java
//Java implementation of above approach
public class AQW {
//to store fibonacci numbers
//42 second number in fibonacci series
//largest possible integer
static int fib[] = new int[43];
//Function to generate fibonacci series
static void fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
//Recursive function to return the
//number of ways
static int rec(int x, int y, int last)
{
// base condition
if (y == 0) {
if (x == 0)
return 1;
return 0;
}
int sum = 0;
// for recursive function call
for (int i = last; i >= 0 && fib[i] * y >= x; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], y - 1, i);
}
return sum;
}
//Driver code
public static void main(String[] args) {
fibonacci();
int n = 13, k = 3;
System.out.println("Possible ways are: "+ rec(n, k, 42));
}
}
Python3
# Python3 implementation of the above approach
# To store fibonacci numbers 42 second
# number in fibonacci series largest
# possible integer
fib = [0] * 43
# Function to generate fibonacci
# series
def fibonacci():
fib[0] = 1
fib[1] = 2
for i in range(2, 43):
fib[i] = fib[i - 1] + fib[i - 2]
# Recursive function to return the
# number of ways
def rec(x, y, last):
# base condition
if y == 0:
if x == 0:
return 1
return 0
Sum, i = 0, last
# for recursive function call
while i >= 0 and fib[i] * y >= x:
if fib[i] > x:
i -= 1
continue
Sum += rec(x - fib[i], y - 1, i)
i -= 1
return Sum
# Driver code
if __name__ == "__main__":
fibonacci()
n, k = 13, 3
print("Possible ways are:", rec(n, k, 42))
# This code is contributed
# by Rituraj Jain
C#
// C# implementation of above approach
using System;
class GFG
{
// to store fibonacci numbers
// 42 second number in fibonacci series
// largest possible integer
static int[] fib = new int[43];
// Function to generate fibonacci series
public static void fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (int i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
// Recursive function to return the
// number of ways
public static int rec(int x, int y, int last)
{
// base condition
if (y == 0) {
if (x == 0)
return 1;
return 0;
}
int sum = 0;
// for recursive function call
for (int i = last; i >= 0 && fib[i] * y >= x; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], y - 1, i);
}
return sum;
}
// Driver code
static void Main()
{
for(int i = 0; i < 43; i++)
fib[i] = 0;
fibonacci();
int n = 13, k = 3;
Console.Write("Possible ways are: " + rec(n, k, 42));
}
//This code is contributed by DrRoot_
}
PHP
<?php
// PHP implementation of above approach
// To store fibonacci numbers
// 42 second number in fibonacci series
// largest possible integer
$fib = array_fill(0, 43, 0);
// Function to generate
// fibonacci series
function fibonacci()
{
global $fib;
$fib[0] = 1;
$fib[1] = 2;
for ($i = 2; $i < 43; $i++)
$fib[$i] = $fib[$i - 1] +
$fib[$i - 2];
}
// Recursive function to return
// the number of ways
function rec($x, $y, $last)
{
global $fib;
// base condition
if ($y == 0)
{
if ($x == 0)
return 1;
return 0;
}
$sum = 0;
// for recursive function call
for ($i = $last; $i >= 0 and
$fib[$i] * $y >= $x; $i--)
{
if ($fib[$i] > $x)
continue;
$sum += rec($x - $fib[$i],
$y - 1, $i);
}
return $sum;
}
// Driver code
fibonacci();
$n = 13;
$k = 3;
echo "Possible ways are: " .
rec($n, $k, 42);
// This code is contributed by mits
?>
Javascript
<script>
//Javascript implementation of above approach
//to store fibonacci numbers
//42 second number in fibonacci series
//largest possible integer
let fib=new Array(43);
//Function to generate fibonacci series
function fibonacci()
{
fib[0] = 1;
fib[1] = 2;
for (let i = 2; i < 43; i++)
fib[i] = fib[i - 1] + fib[i - 2];
}
//Recursive function to return the
//number of ways
function rec(x,y,last)
{
// base condition
if (y == 0) {
if (x == 0)
return 1;
return 0;
}
let sum = 0;
// for recursive function call
for (let i = last; i >= 0 && fib[i] * y >= x; i--) {
if (fib[i] > x)
continue;
sum += rec(x - fib[i], y - 1, i);
}
return sum;
}
//Driver code
fibonacci();
let n = 13, k = 3;
document.write("Possible ways are: "+ rec(n, k, 42));
// This code is contributed by rag2127
</script>
Producción:
Possible ways are: 2
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA