题目大意
数列k-bonacci (k is integer, k > 1)的定义如下：
- F(k, n) = 0, for integer n, 1 ≤ n < k;
- F(k, k) = 1;
- F(k, n) = F(k, n - 1) + F(k, n - 2) + … + F(k, n - k), for integer n, n > k.
给出一个整数s，在数列中找出几个不同的元素使其和等于s。
思路
我们可以先暴力求出所有值小于s的元素，由题目input中给出的数据范围(1 ≤ s, k ≤ 10^9; k > 1)可以推知小于s的元素的数量不会很多。
求取结果是一个贪心的过程。由大到小遍历元素，如果当前元素不大于s，则将s减去此元素，并将此元素作为结果记录下来。重复上述步骤直至s等于0。
代码
#include
#include
#include
using namespace std;
int f[100],res[100];
//f[i]表示f(k,k+i-1)
//res[]存储结果
int N_f,N_res;
//N_f表示f[]中元素的数量
//N_res表示res[]中元素的数量
int s,k;
void init()
//初始化
{
memset(f,0,sizeof(f));
memset(res,0,sizeof(res));
}
void get_f()
//计算f[]
{
f[1]=1;
//f(k,k)=1
for(N_f=2;f[N_f-1]=1&&i>=N_f-k;i--)
f[N_f]+=f[i];
}
void get_res()
//计算res[]
{
for(int i=N_f-1;i>=1&&s;i--)
if(f[i]<=s)
{
res[N_res++]=f[i];
s-=f[i];
}
}
void input()
//输入
{
scanf("%d%d",&s,&k);
}
void output()
//输出
//每次都在结果末尾加一个0，避免结果数不足2的情况发生。
{
printf("%d\n",N_res+1);
for(int i=0;i<N_res;i++)
printf("%d ",res[i]);
printf("0\n");
}
int main()
{
init();
input();
get_f();
get_res();
output();
}