g*********s
发帖数: 1782 | 1 最近的面经。
3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
我用了两个static variables. 程序写好念给他听。他运行了一下说pass. |
M7
发帖数: 219 | 2
2)
复杂度上差远了。static variable的方法其实就是loop的方法。而用递归的方法的复
杂度
就恐怖了。
30
是这样。这里复杂度没有区别。所以考的是技巧。
【在 g*********s 的大作中提到】
: 最近的面经。
: 3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
: 归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
: 我用了两个static variables. 程序写好念给他听。他运行了一下说pass.
|
g*********s
发帖数: 1782 | 3
那用全局变量也一样吧。线程安全性有问题。
这个技巧有什么用呢？针对某些不方便提供辅助数据结构的语言如Scheme和Haskell？
觉得Amazon这种题都挺偏的。
【在 M7 的大作中提到】
:
: 2)
: 复杂度上差远了。static variable的方法其实就是loop的方法。而用递归的方法的复
: 杂度
: 就恐怖了。
: 30
: 是这样。这里复杂度没有区别。所以考的是技巧。
|
j********x
发帖数: 2330 | 4 啥意思，不用loop 用递归，但是又不许递归？。。。 |
M7
发帖数: 219 | 5 I don't know. You may ask your interviewer about that. :)
For most positions, interviewers are not interested in Lisp/Prolog kind of
languages at all. One of the interviewers told me "Use any language, but no
lisp...."
【在 g*********s 的大作中提到】
:
: 那用全局变量也一样吧。线程安全性有问题。
: 这个技巧有什么用呢？针对某些不方便提供辅助数据结构的语言如Scheme和Haskell？
: 觉得Amazon这种题都挺偏的。
|
j*****u
发帖数: 1133 | 6 说实话这个题太没意思了，比用stack写queue还无聊。。
不知道这样写满不满足他的要求(不用全局变量)
int Fib(int n, int a, int b)
{
return n <= 1 ? b : Fib(n - 1, b, a + b);
}
wrapper function call的时候Fib(n, 1, 1);
2)
30
【在 g*********s 的大作中提到】
: 最近的面经。
: 3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
: 归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
: 我用了两个static variables. 程序写好念给他听。他运行了一下说pass.
|
g*********s
发帖数: 1782 | 7 我在想栈模拟队列那个大概也有背景？比如远古时代的机器硬件底层只有栈……
【在 j*****u 的大作中提到】
: 说实话这个题太没意思了，比用stack写queue还无聊。。
: 不知道这样写满不满足他的要求(不用全局变量)
: int Fib(int n, int a, int b)
: {
: return n <= 1 ? b : Fib(n - 1, b, a + b);
: }
: wrapper function call的时候Fib(n, 1, 1);
:
: 2)
: 30
|
w*z
发帖数: 75 | 8 第一个就是用递归实现循环的意思吧
#include
int a = 1;
int b = 1;
bool first = true;
void f(n) { // print all fib nums <= n in normal order, n >= 1
if (first){
cout<
first = false;
}
int c = a + b;
if (c > n)
return;
cout<
a = b;
b = c;
f(n);
}
2)
30
【在 g*********s 的大作中提到】
: 最近的面经。
: 3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
: 归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
: 我用了两个static variables. 程序写好念给他听。他运行了一下说pass.
|
o****u
发帖数: 714 | 9 python code
a = 1
b = 1
def f(a,b,i):
if i == 10:
return
a = a + b
print a
f(b,a,i+1)
print a
print b
f(a,b,1)
def f2(a,b,i):
if i == 10:
return
a = a + b
f2(b, a, i+1)
print a
print ' '
f2(a,b,1)
print a
print b
2)
30
【在 g*********s 的大作中提到】
: 最近的面经。
: 3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
: 归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
: 我用了两个static variables. 程序写好念给他听。他运行了一下说pass.
|
P********l
发帖数: 452 | 10 1. Reverse print the sequence
Because f(n)=f(n-1)+fn(-2), we have f(n-2)=f(n)-f(n-1). We just needs two
numbers and back trace to f(0). In the process, no new variables are needed.
2. top down dynamic programming
f(n)=f(n-1)+f(n-2) is not allowed, but f(n)=f[n-1]+f[n-2] is allowed.
check
http://www.sureinterview.com/shwqst/123005
Also try a search there to see if the question has an answer. |
E**h
发帖数: 6 | 11 void Print_Fibonacci_Reverse(uint32_t n)
{
static uint32_t n0 = 0;
static uint32_t n1 = 1;
if (0 == n)
{
cout << n0 << endl;
return;
}
if (1 == n)
{
cout << n1 << endl;
cout << n0 << endl;
return;
}
uint32_t result = n1 + n0;
n0 = n1;
n1 = result;
Print_Fibonacci_Reverse(n - 1);
result = n1 - n0;
n1 = n0;
n0 = result;
cout << result << endl;
return;
} |
c******n
发帖数: 4965 | 12 rather simple ah
first get
Fn. Fn-1.
then while I > 0
temp = fn-1
fn-1 = fn - fn-1
fn = temp
I --
【在 g*********s 的大作中提到】
: 最近的面经。
: 3. 写函数 输出Fibonacci numbers in normal sequence (no loop allowed, use 递
: 归, cannot compute Fibonacci number using F(X) = F(X-1) + F(X-2))
: 我用了两个static variables. 程序写好念给他听。他运行了一下说pass.
|
