题目概要
题目描述
给一个数k,问最少可以用几个斐波那契数加加减减凑出来
例如
10=5+519=21−217=13+5−11070=987+89−5−1
样例输入
1
1070
样例输出
4
数据范围
k≤1017
多组数据,不超过10组.
解题报告
题意理解
给一个数k,问最少可以用几个斐波那契数加加减减凑出来.
算法解析
首先我们得知道,因为斐波那契数列,有如下这个特殊数字.
a0=0,a1=1,a2=1,a3=2an=an−1+an−2n≥2
那么一个数字,总能被几个斐波那契数组合而成.
证明不太会,大佬可以在下面留言,教教我.
我们接着理解,对于一个整数,它的斐波那契数表示如下.
x=a1±a2±a3±⋯±acnt其中ai为斐波那契数
而题目的要求,就是让我们找到这个最小的cnt
假如说,我们发现,在这个表达数列之中,有两个数a,b满足.
定义:Rank(a)表示为a在斐波那契数列中的位置若Rank(a)=Rank(b)+1或者Rank(b)=Rank(a)+1
那么,我们可以使用,一个数c,代替a,b.
c=a+b
或者说,本来表达数列是.
x=a+b⇒x=cx=p−a−b⇒x=p−c
比如说.
x=14=1+13=1+5+813=15+81,5,8,13,都是斐波那契数
这有什么用处?
这可以让我们推出贪心
对于一个数x,我们找到与x差值最小的斐波拉契数,将新的x赋为差值,每次进行这个操作,统计次数,直到x为0,输出次数。
这个的证明,其实在上面就已经体现了.
f[x]=min(f[p]−x,x−f[p−1])p为大于等于x,中最小的数p−1自然就是小于等于x,中最大的数
代码解析
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=110;
int f[N],x,n;
inline int check(int x)
{
int cnt=0,p=0;
while(x)
{
p=lower_bound(f+1,f+1+98,x)-f;//大于等于x中最小的那一个数
x=min(x-f[p-1],f[p]-x);//p-1为小于等于x中最大的那一个数
cnt++;
}
return cnt;
}
inline void init()
{
scanf("%lld",&n);
f[1]=1;
for(int i=2; i<=98; i++)//预处理斐波那契数
f[i]=f[i-1]+f[i-2];
while(n--)
{
scanf("%lld",&x);
printf("%lld\n",check(x));
}
}
signed main()
{
init();
return 0;
}
上面有个13=15+8。。。
突然高产hhh
我似乎写题解像单峰函数.