问一题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一题

问一题# JobHunting - 待字闺中

y*m2011-03-01 08:03

1 楼

f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)
求所有大于0的整数f(n)值
弄了个数组从1..n挨个计算后把值存进去:
function Array getArray(n){
array a[n+1];
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++)
a[n]=a[n-1]+a[n-2];
return a;
}
function getN(n){
getArray(n)[n];
}
有更好的办法么
thx!

g*s2011-03-01 08:03

2 楼

if it is asked to get all f(k) k = 1..n, it(DP) is the best way.
if it is asked to get the value : f(n), you can use the closed-form solution
to get directly.

C*y2011-03-01 08:03

3 楼

这题如果被问到的话，不会问你这个的
问法1：上楼梯，只能上一个台阶或者两个，问你有多少种走法
问法2：使用constant的空间，怎么每次调用，返回下个f(n)的值，且复杂度最低
问法3：如果使用递归，时间复杂度多少？
可能还有其他的问法，大家补充补充

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

: f(1)=1
: f(2)=2
: f(n)=f(n-1)+f(n-2)
: 求所有大于0的整数f(n)值
: 弄了个数组从1..n挨个计算后把值存进去:
: function Array getArray(n){
: array a[n+1];
: a[1]=1;
: a[2]=2;
: for(int i=3;i<=n;i++)

y*m2011-03-01 08:03

4 楼

就是这样问-_-,没有问那么多台阶,空间之类..

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

: 这题如果被问到的话，不会问你这个的
: 问法1：上楼梯，只能上一个台阶或者两个，问你有多少种走法
: 问法2：使用constant的空间，怎么每次调用，返回下个f(n)的值，且复杂度最低
: 问法3：如果使用递归，时间复杂度多少？
: 可能还有其他的问法，大家补充补充

a*72011-03-01 08:03

5 楼

there is a lg(n) solution, but very complicated. I think it's overkilled for
interview.
http://zhedahht.blog.163.com/blog/static/2541117420072299193344

y*m2011-03-01 08:03

6 楼

应该是第一种，问各个n,不懂dp-_-

solution

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

: if it is asked to get all f(k) k = 1..n, it(DP) is the best way.
: if it is asked to get the value : f(n), you can use the closed-form solution
: to get directly.

y*m2011-03-01 08:03

7 楼

数组解:
function Array getArray(n){
array a[n+1];
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++)
a[n]=a[n-1]+a[n-2];
return a;
}
function getN(n){
getArray(n)[n];
}

for

【在 a******7 的大作中提到】

: there is a lg(n) solution, but very complicated. I think it's overkilled for
: interview.
: http://zhedahht.blog.163.com/blog/static/2541117420072299193344

l*r2011-03-01 08:03

8 楼

a[n+1] C能通过么？要用malloc吧？

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

: 数组解:
: function Array getArray(n){
: array a[n+1];
: a[1]=1;
: a[2]=2;
: for(int i=3;i<=n;i++)
: a[n]=a[n-1]+a[n-2];
: return a;
: }
: function getN(n){