Number of ways to represent a number as sum of k fibonacci numbers | C ++ implementation of above approach ; to store fibonacci numbers 42 second number in fibonacci series largest possible integer ; Function to generate fibonacci series ; Recursive function to return the number of ways ; base condition ; for recursive function call ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int fib [ 43 ] = { 0 } ; void fibonacci ( ) { fib [ 0 ] = 1 ; fib [ 1 ] = 2 ; for ( int i = 2 ; i < 43 ; i ++ ) fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] ; } int rec ( int x , int y , int last ) { if ( y == 0 ) { if ( x == 0 ) return 1 ; return 0 ; } int sum = 0 ; 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 ; } int main ( ) { fibonacci ( ) ; int n = 13 , k = 3 ; cout << " Possible ▁ ways ▁ are : ▁ " << rec ( n , k , 42 ) ; return 0 ; }