A Google Problem - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

A Google Problem

A Google Problem# JobHunting - 待字闺中

D*e2011-10-17 07:10

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*y2011-10-17 07:10

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*e2011-10-17 07:10

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*e2011-10-17 07:10

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*y2011-10-17 07:10

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*e2011-10-17 07:10

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*e2011-10-17 07:10

7 楼

I mean your solution is trivial.
Or did I miss sth?

【在 g**********y 的大作中提到】

: 请读程序，或者运行验证一下。

g*y2011-10-17 07:10

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*e2011-10-17 07:10

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*e2011-10-17 07:10

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*x2011-10-17 07:10

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*s2011-10-17 07:10

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*e2011-10-17 07:10

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*x2011-10-17 07:10

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*l2011-10-17 07:10

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?