齐肯多夫表示
* * * *
拉格朗日计划
* * * *
齐肯多夫表示

每个自然数或者在斐波那契数列中,或者可以写成若干个斐波那契数列中的不同且非连续项的数之和,这一写法称为该数的齐肯多夫表示。例如$10=8+2$,$64=55+8+1$。

对每个给定的数(注:以字符串形式给出),输出其齐肯多夫表示,不同的数之间用" + "连接。例如给定10,则对应的输出应该是8 + 2。

每个输入数据都是小于$2^{31}$的自然数。

本题难度:



解答

设$y=f(x)$是斐波那契数列中最大的不超过x的数,$g(x)$是x的齐肯多夫表示,那么显然有递推关系: $$g(x)=y+g(x-y)$$ 注意$g(0)$为空。根据本题的数据范围,先生成50项斐波那契数,再递归打印输出。

最终代码有四行。

代码长度:168字节 vs. 全站第一:112字节。

import sys,bisect as s
f=[1,1];exec('f+=[f[-1]+f[-2]];'*48)
g=lambda x:[str(y:=f[s.bisect(f,x)-1])]+g(x-y)if x else[]
for a in sys.argv[1:]:print(" + ".join(g(int(a))))