y***m
发帖数: 7027 | 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***s
发帖数: 3811 | 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***y
发帖数: 2546 | 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***m
发帖数: 7027 | 4 就是这样问-_-,没有问那么多台阶,空间之类..
【在 C***y 的大作中提到】
: 这题如果被问到的话，不会问你这个的
: 问法1：上楼梯，只能上一个台阶或者两个，问你有多少种走法
: 问法2：使用constant的空间，怎么每次调用，返回下个f(n)的值，且复杂度最低
: 问法3：如果使用递归，时间复杂度多少？
: 可能还有其他的问法，大家补充补充
|
a******7
发帖数: 106 | 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***m
发帖数: 7027 | 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***m
发帖数: 7027 | 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*********r
发帖数: 674 | 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){
|
E***n
发帖数: 166 | 9 c99 支持变长度数组
gcc -std=c99 file.cpp
【在 l*********r 的大作中提到】
: a[n+1] C能通过么？要用malloc吧？
|
e***l
发帖数: 710 | 10 这是从1开始的Fibonacci，F(n)可以直接算出来
F(n)=(a^(n+1)-b^(n+1))/sqrt(5)
where a=(1+sqrt(5))/2, b=(1-sqrt(5))/2 |
