本文共 1426 字，大约阅读时间需要 4 分钟。

Number of ways to represent a number as sum of k fibonacci numbers

Given two numbers N and K. Find the number of ways to represent N as the sum of K Fibonacci numbers.

Examples:

Input : n = 12, k = 1

Output : 0

Input : n = 13, k = 3

思路：

用k限制递归次数，每次遍历所有可能的Fibonacci数，但是这里需要注意，会有重复的情况，例如13 = 2 +3 + 8

13 = 3 + 2 + 8  等 只能算为1种组合。所以需要一个有序的Fibnocci序列，然后按照一定顺序试探能否满足条件（这里采用倒序，即last标识上一次试探的位置，为了不重复，下一次减去的值只能为在该位置的值及之前的值）。

code中 k*a[i] >= n 可视为剪枝，此时只有k步，当前最大fibnocci 值为 a[i]  如果k*a[i] < n，那么后面的值之和不可能为当前的n。

code:

#include
   
    #define pb(i) push_back(i)using namespace std;int a[40];int tol;int vis[40];void rec(int n,int k,int last){    if(k == 0){        if(n == 0){            ++tol;            for(int i = 0; i < 40; ++i){                if(vis[i]){                    for(int j = 0; j < vis[i]; ++j)                        printf("%d ",a[i]);                }            }            printf("\n");        }        return;    }    if(n < 0)        return ;    for(int i = last; i >= 0 && a[i]*k >= n; --i){        if(a[i] <= n){            ++vis[i];            rec(n-a[i],k-1,i);            vis[i] = 0;        }    }}int main()    {        int n,k;        // 为了防止重复 取起始的2个一 中的一个1        a[0] = 1;a[1] = 2;        for(int i = 2; i < 40; ++i){            a[i] = a[i-1] + a[i-2];        }        scanf("%d%d",&n,&k);        rec(n,k,39);        printf("%d\b",tol);        return 0;    }
   

转载地址：http://iwsmi.baihongyu.com/