D*******e
发帖数: 151 | 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. Got it?? 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
Any one solves this efficiently? |
g**********y
发帖数: 14569 | 2 就是一个DFS:
public class FibonacciExpression {
private int[] f;
private int[] m;
public void express(int n) {
f = new int[128];
f[0] = 1;
f[1] = 2;
int N = 2;
while (f[N-1] < n) {
f[N] = f[N-1] + f[N-2];
N++;
}
m = new int[128];
m[0] = 1;
for (int i=1; i
dfs(n, "", N-1);
}
private void dfs(int n, String solution, int i) {
if (i < 0) {
if (n == 0) System.out.println(solution);
return;
}
if (n<0 || n > m[i]) return;
dfs(n - f[i], solution + "1", i-1);
dfs(n, solution.length()==0? solution : solution + "0", i-1);
}
public static void main(String[] args) {
new FibonacciExpression().express(100000000);
}
} |
D*******e
发帖数: 151 | 3 Then why Fibonacci here? This condition is not used.
If f(x) + f(y) = n, at least you can expand x and y to get a series of
solutions.
【在 g**********y 的大作中提到】
: 就是一个DFS:
: public class FibonacciExpression {
: private int[] f;
: private int[] m;
:
: public void express(int n) {
: f = new int[128];
: f[0] = 1;
: f[1] = 2;
:
|
D*******e
发帖数: 151 | 4 I mean expand f(x)
【在 D*******e 的大作中提到】
: Then why Fibonacci here? This condition is not used.
: If f(x) + f(y) = n, at least you can expand x and y to get a series of
: solutions.
|
g**********y
发帖数: 14569 | 5 请读程序，或者运行验证一下。
【在 D*******e 的大作中提到】
: Then why Fibonacci here? This condition is not used.
: If f(x) + f(y) = n, at least you can expand x and y to get a series of
: solutions.
|
D*******e
发帖数: 151 | 6 where did you make use of the property of Fibonacci?
For any sorted array, it seems your algorithm works the same way.
【在 g**********y 的大作中提到】
: 请读程序，或者运行验证一下。
|
D*******e
发帖数: 151 | 7 I mean your solution is trivial.
Or did I miss sth?
【在 g**********y 的大作中提到】
: 请读程序，或者运行验证一下。
|
g**********y
发帖数: 14569 | 8 int[] f is Fibonacci sequence, int[] m is sum of 0..i Fibonacci numbers.
If the code looks trivial, that's because this is not a hard problem.
【在 D*******e 的大作中提到】
: I mean your solution is trivial.
: Or did I miss sth?
|
D*******e
发帖数: 151 | 9 You simply didn't read my reply.
Your solution is exponential. Every number can be taken or not taken. m[]
cuts some branches.
I knew you generate Fibonacci at the first place. I mean you didn't makes
use of its property.
Suppose you have the coding for f(x) and f(n) = f(x) + f(y), at least you
can submit the coding of f(x) into f(n) to save some computation.
However I won't say your solution is meaningless because I don't know how to
make the solution complete, besides the way you used here.
【在 g**********y 的大作中提到】
: int[] f is Fibonacci sequence, int[] m is sum of 0..i Fibonacci numbers.
: If the code looks trivial, that's because this is not a hard problem.
|
D*******e
发帖数: 151 | 10 because the single bit at f(x) can be replaced by the two bits at f(x-1) and
f(x - 2)
to
【在 D*******e 的大作中提到】
: You simply didn't read my reply.
: Your solution is exponential. Every number can be taken or not taken. m[]
: cuts some branches.
: I knew you generate Fibonacci at the first place. I mean you didn't makes
: use of its property.
: Suppose you have the coding for f(x) and f(n) = f(x) + f(y), at least you
: can submit the coding of f(x) into f(n) to save some computation.
: However I won't say your solution is meaningless because I don't know how to
: make the solution complete, besides the way you used here.
|
|
|
c****x
发帖数: 61 | 11 我觉得Fibonacci就是保证肯定至少有一个解
任何算法至少是O(2^n)的，这个没有问题
【在 D*******e 的大作中提到】
: where did you make use of the property of Fibonacci?
: For any sorted array, it seems your algorithm works the same way.
|
e***s
发帖数: 799 | 12 Why we need the m array?
【在 g**********y 的大作中提到】
: 就是一个DFS:
: public class FibonacciExpression {
: private int[] f;
: private int[] m;
:
: public void express(int n) {
: f = new int[128];
: f[0] = 1;
: f[1] = 2;
:
|
D*******e
发帖数: 151 | 13 Can you prove no better solution than O(2^n) exists for Fibonacci sequence?
Though I agree with your conclusion.
【在 c****x 的大作中提到】
: 我觉得Fibonacci就是保证肯定至少有一个解
: 任何算法至少是O(2^n)的，这个没有问题
|
c****x
发帖数: 61 | 14 假设你的输入为第n个fibonnaci数a[n]
那么容易证明a[n]<=2^n，所以输入串的长度<=n
假设N(x)为将x表示为<=x的不同finonacci数之和的方法数
那么有
N(a[n]) >= 1 + N(a[n-2]) + (N(a[n-1])-1) = N(a[n-1]) + N(a[n-2])
N(a[n]) 显然至少是 O(2^n)，也就是说至少有O(2^n)种组合，同时你的输入串长度<=n
你现在要把每种组合都输出出来，就算输出每个组合都是O(1)的，总的复杂度也超过O(
2^n)了
?
【在 D*******e 的大作中提到】
: Can you prove no better solution than O(2^n) exists for Fibonacci sequence?
: Though I agree with your conclusion.
|
d*******l
发帖数: 338 | 15 我觉得上面的分析不无道理，一旦要输出所有的解很可能就没有办法降低复杂度，这跟
问题本身的性质有关。上面火鸡的方法应该是非常典型，在面试中的首选方法。
如果只是考虑这个问题本身，或许可以尝试下BFS？如果我们已经有一个解，然后所有
的解应该都能通过这个解propagate得到。对每一个1，都尝试把它替换成低位的两个1
。不过这个应该不会有本质的改善.代价就是更多的空间。
另外有个问题？比如9=5+2+2这种表示是不考虑的是吧？就是某个数出现了两次，这样
就没法在二进制表示中体现出来了。
2
2
【在 D*******e 的大作中提到】
: 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. Got it?? 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
: Any one solves this efficiently?
|
