d**********1
发帖数: 37 | 1 If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 +
2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101.
The Question was, given n, I need to get all possible representations of n
in Fibonacci Binary Number System. as 10 = 8 + 2 ==> 10010 also 10 = 5 + 3
+ 2 ==> 1110
小弟认为
1） 求出Fibonacci序列 F[0-k], where F[k]<=N, F[k+1]>N;
2) 问题就转化为 从一个array里面找 “和为N” 的所有子序列。 找出以后再打印
binary的形式。
其中第二步可以用回溯法来遍历，但是时间复杂度貌似很高。 试着想了想DP，没想明
白。
这里插个话题，突然想到回溯法的时间复杂度，查了一下，好像是O(n^3),百思不得其
解。。不知道为
什么是n^3。
请高人指点。。 | g**e
发帖数: 6127 | 2 用数学归纳法容易证明，任何自然数n都可以表示为一系列fibonacci数之和。我觉得可
以用贪心算法
先算出小于n的素有fibonacci数列f[i],同时计算s[i]=f[1]+..+f[i]。对所有的f[i]
&&s[i]>=n开始用贪心算法回溯，找到所有的组合
【在 d**********1 的大作中提到】
: If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 +
: 2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101.
: The Question was, given n, I need to get all possible representations of n
: in Fibonacci Binary Number System. as 10 = 8 + 2 ==> 10010 also 10 = 5 + 3
: + 2 ==> 1110
: 小弟认为
: 1） 求出Fibonacci序列 F[0-k], where F[k]<=N, F[k+1]>N;
: 2) 问题就转化为 从一个array里面找 “和为N” 的所有子序列。 找出以后再打印
: binary的形式。
: 其中第二步可以用回溯法来遍历，但是时间复杂度貌似很高。 试着想了想DP，没想明
| d**********1
发帖数: 37 | 3 你的想法跟我一样，可是就是说不清楚回溯的时间复杂度，怎么看都应该是n^n，可是
记忆中这个复杂度应该是n^3 | a*****j
发帖数: 2 | 4 FindFibSum(n, fib_list)
Find k such that Fib(k)< n < Fib(k+1)
Add k into the fib_list
FindFibSum(n-Fib(k));
End
Expand the fib_list using Fib(k) = Fib(k-1) + Fib(k-2) rules
For example,
n = 12
FindFibSum(12) ->
k = 5, FindFibSum(4) ->
k = 3, FindFibSum(1) ->
k = 1
fib_list = 5, 3, 1
-> 4, 3, 3, 1 x
-> 5, 2, 1, 1 x
The final answer is 5, 3, 1 = 10101 | g**e
发帖数: 6127 | 5 因为fibonacci数列是成指数上升的，f(n+1)/f(n)极限趋近黄金分割1.618. 对于相当
大的n，小于n的fibonacci个数远小于n。所以我觉得这个复杂度应该接近O(n^2)，或者
是你说的O(n^3)。
我数学是半吊子，请数学大牛解答
【在 d**********1 的大作中提到】
: 你的想法跟我一样，可是就是说不清楚回溯的时间复杂度，怎么看都应该是n^n，可是
: 记忆中这个复杂度应该是n^3
| r*******y
发帖数: 1081 | 6 no need to prove this one. hehe
if no consective F numbers to use in the representation, then any number
n can have a uniqe F representation.
【在 g**e 的大作中提到】
: 用数学归纳法容易证明，任何自然数n都可以表示为一系列fibonacci数之和。我觉得可
: 以用贪心算法
: 先算出小于n的素有fibonacci数列f[i],同时计算s[i]=f[1]+..+f[i]。对所有的f[i]: &&s[i]>=n开始用贪心算法回溯，找到所有的组合
| g**e
发帖数: 6127 | 7 yeah, this is Zeckendorf's theorem. I learned this later.
【在 r*******y 的大作中提到】
: no need to prove this one. hehe
: if no consective F numbers to use in the representation, then any number
: n can have a uniqe F representation.
:
:
|
|
