H**********t
发帖数: 296 | 1 求fibnacci数列 不许用递归 从头到尾只能用三个变量 |
H**********t
发帖数: 296 | 2 这三个变量不包括函数的参数 fib（n）
n不算
【在 H**********t 的大作中提到】
: 求fibnacci数列 不许用递归 从头到尾只能用三个变量
|
s***c
发帖数: 1926 | |
H**********t
发帖数: 296 | 4 根本不需要那么复杂 你已经被我淘汰
【在 s***c 的大作中提到】
: DP加滚动数组啊
|
H**********t
发帖数: 296 | |
s***v
发帖数: 4924 | 6 f(0)=1;
f(1)=1,;
for i=2:n-1
f(i)=f(i-2)+f(i-1);
end |
H**********t
发帖数: 296 | 7 不许用数组
【在 s***v 的大作中提到】
: f(0)=1;
: f(1)=1,;
: for i=2:n-1
: f(i)=f(i-2)+f(i-1);
: end
|
H**********t
发帖数: 296 | |
s***c
发帖数: 1926 | 9 你说的就是DP加滚动数组啊，任何一本面试书里的最基本题。
#include
using namespace std;
int Fib[3];
int fib(int n)
{
Fib[1] = 0;
Fib[2] = 1;
for(int i = 2; i <= n; ++i)
{
Fib[0] = Fib[1];
Fib[1] = Fib[2];
Fib[2] = Fib[0] + Fib[1];
}
return Fib[2];
}
int main()
{
int ncase, n, ans;
scanf("%d", &ncase);
while(ncase--)
{
scanf("%d", &n);
ans = fib(n);
printf("%dn", ans);
}
return 0;
}
【在 H**********t 的大作中提到】
: 根本不需要那么复杂 你已经被我淘汰
|
H**********t
发帖数: 296 | 10 不需用数组
【在 s***c 的大作中提到】
: 你说的就是DP加滚动数组啊，任何一本面试书里的最基本题。
: #include
: using namespace std;
: int Fib[3];
:
: int fib(int n)
: {
: Fib[1] = 0;
: Fib[2] = 1;
: for(int i = 2; i <= n; ++i)
|
|
|
H**********t
发帖数: 296 | |
s***c
发帖数: 1926 | 12 滚动数组就不是数组了
【在 H**********t 的大作中提到】
: 不需用数组
|
H**********t
发帖数: 296 | 13 那就相当于一个数组是三个变量 再加上i 就是四个了 超了
【在 s***c 的大作中提到】
: 滚动数组就不是数组了
|
e*g
发帖数: 4981 | |
H**********t
发帖数: 296 | 15 用不着
【在 e*g 的大作中提到】
: 用通项公式
|
H**********t
发帖数: 296 | |
s***v
发帖数: 4924 | 17 a=(1+sqrt (5))/2;
b=-1/a;
f(n)=(a^n-b^n)/sqrt (5); |
m*****n
发帖数: 4015 | |
H**********t
发帖数: 296 | 19 这个不算 你他妈面试现场能背出这个公式？闭卷考试
a=(1+sqrt (5))/2;
【在 s***v 的大作中提到】
: a=(1+sqrt (5))/2;
: b=-1/a;
: f(n)=(a^n-b^n)/sqrt (5);
|
H**********t
发帖数: 296 | 20 no 三个都是local variable
【在 m*****n 的大作中提到】
: 不就是用两个 static 吗
|
|
|
e*g
发帖数: 4981 | 21 这就是我的
a=(1+sqrt (5))/2;
【在 s***v 的大作中提到】
: a=(1+sqrt (5))/2;
: b=-1/a;
: f(n)=(a^n-b^n)/sqrt (5);
|
H**********t
发帖数: 296 | 22 错
【在 e*g 的大作中提到】
: 这就是我的
:
: a=(1+sqrt (5))/2;
|
s***c
发帖数: 1926 | |
m*****n
发帖数: 4015 | 24 Static can be used for local variables too
[在 HillaryClint (test) 的大作中提到：]
:no 三个都是local variable
:☆ 发自 iPhone 买买提 1.23.01 |
d********8
发帖数: 691 | 25 大哥，cs不学离散数学的吗？这公式现推也就几十秒
【在 H**********t 的大作中提到】
: 这个不算 你他妈面试现场能背出这个公式？闭卷考试
:
: a=(1+sqrt (5))/2;
|
e*g
发帖数: 4981 | |
H**********t
发帖数: 296 | |
s***v
发帖数: 4924 | |
H**********t
发帖数: 296 | 29 这算一种 还可以不用
【在 e*g 的大作中提到】
: 用^=
|
H**********t
发帖数: 296 | 30 我能想出三种方法
【在 s***v 的大作中提到】
: 这也不行那也不行的，老大爷，我不面试了行吗？
|
|
|
m*****n
发帖数: 4015 | 31 这个可以用来做 in place swap.
但是我要面试。有人要是 卖弄这种 coding trick。我肯定让他挂。
[在 elg (二里沟) 的大作中提到：]
:用^= |
H**********t
发帖数: 296 | |
H**********t
发帖数: 296 | 33 我有两种方法都不用xor
【在 m*****n 的大作中提到】
: 这个可以用来做 in place swap.
: 但是我要面试。有人要是 卖弄这种 coding trick。我肯定让他挂。
: [在 elg (二里沟) 的大作中提到：]
: :用^=
|
s***v
发帖数: 4924 | |
s******n
发帖数: 3946 | 35 两个变量就行了啊，再加个循环变量
a[0] = 1
a[1] = 1
a[0] += a[1] ->2
a[1] += a[0] ->3
a[0] += a[1] ->5
a[1] += a[0] ->8
.... |
H**********t
发帖数: 296 | 36 A=1;b=1
For I=3 to n
A<=b ? A+=b : b+=a
End
Return a<=b ? B : a |
H**********t
发帖数: 296 | 37 循环变量他妈的不算变量？
【在 s******n 的大作中提到】
: 两个变量就行了啊，再加个循环变量
: a[0] = 1
: a[1] = 1
: a[0] += a[1] ->2
: a[1] += a[0] ->3
: a[0] += a[1] ->5
: a[1] += a[0] ->8
: ....
|
s******n
发帖数: 3946 | 38 傻逼，a[0], a[1]加一个循环变量总共几个？
【在 H**********t 的大作中提到】
: 循环变量他妈的不算变量？
|
H**********t
发帖数: 296 | 39 三个啊
【在 s******n 的大作中提到】
: 傻逼，a[0], a[1]加一个循环变量总共几个？
|
s******n
发帖数: 3946 | 40 你这不是最优，打回去重写，哪有每个循环还检查a<=b的？
【在 H**********t 的大作中提到】
: A=1;b=1
: For I=3 to n
: A<=b ? A+=b : b+=a
: End
: Return a<=b ? B : a
|
|
|
s******n
发帖数: 3946 | 41 你不就要三个吗？
【在 H**********t 的大作中提到】
: 三个啊
|
s***c
发帖数: 1926 | 42 给你看看科班码农怎么思考问题
dp + 滚动数组
public int fib(int n)
{
int a = 0, b = 1, c;
if( n == 0)
return a;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return b;
}
非要把c去掉的话，简单的数学计算
public int fib2(int n)
{
int a = 0, b = 1;
if( n == 0)
return a;
for (int i = 2; i <= n; i++)
{
b = a + b;
a = b - a;
}
return b;
}
你再要把i省掉就写成不带i的循环啊
所谓省变量，都是编译器可以干的事情。人类不用思考这种问题。
【在 H**********t 的大作中提到】
: A=1;b=1
: For I=3 to n
: A<=b ? A+=b : b+=a
: End
: Return a<=b ? B : a
|
H**********t
发帖数: 296 | 43 那你他妈说什么两个
【在 s******n 的大作中提到】
: 你不就要三个吗？
|
s******n
发帖数: 3946 | 44 for (int a=1, b = 1, i = 3; i <= n; i+=2) {
a+=b;
b+=a;
}
return i==n+2 ? a : b;
【在 H**********t 的大作中提到】
: 那你他妈说什么两个
|
H**********t
发帖数: 296 | 45 你这就是相当于xor
他妈循环怎么省掉i
【在 s***c 的大作中提到】
: 给你看看科班码农怎么思考问题
: dp + 滚动数组
: public int fib(int n)
: {
: int a = 0, b = 1, c;
: if( n == 0)
: return a;
: for (int i = 2; i <= n; i++)
: {
: c = a + b;
|
H**********t
发帖数: 296 | 46 你这跟mod 2一回事
【在 s******n 的大作中提到】
: for (int a=1, b = 1, i = 3; i <= n; i+=2) {
: a+=b;
: b+=a;
: }
: return i==n+2 ? a : b;
|
H**********t
发帖数: 296 | 47 傻逼 考的是你智商
【在 s***c 的大作中提到】
: 给你看看科班码农怎么思考问题
: dp + 滚动数组
: public int fib(int n)
: {
: int a = 0, b = 1, c;
: if( n == 0)
: return a;
: for (int i = 2; i <= n; i++)
: {
: c = a + b;
|
s******n
发帖数: 3946 | 48 别硬凹了，你写代码质量次。
你N循环都要做2*N次比较 i
我这只要N/2次比较。
【在 H**********t 的大作中提到】
: 你这跟mod 2一回事
|
s***c
发帖数: 1926 | 49 public int fib3(int n)
{
int a = 0, b = 1;
if( n == 0)
return a;
while(n >= 2){
b = a + b;
a = b - a;
n--;
}
return b;
}
【在 H**********t 的大作中提到】
: 你这就是相当于xor
: 他妈循环怎么省掉i
|
H**********t
发帖数: 296 | 50 操 算你赢了
【在 s***c 的大作中提到】
: public int fib3(int n)
: {
: int a = 0, b = 1;
: if( n == 0)
: return a;
: while(n >= 2){
: b = a + b;
: a = b - a;
: n--;
: }
|
|
|
H**********t
发帖数: 296 | 51 你是垃圾 我他妈操你妈了个大血逼
【在 s******n 的大作中提到】
: 别硬凹了，你写代码质量次。
: 你N循环都要做2*N次比较 i: 我这只要N/2次比较。
|
M***6
发帖数: 895 | 52 你这没什么高大上啊？骂了这么久。我还以为你的解法多么clever呢
题目马马虎虎。解法普通。当然你可能不这么觉得
[在 HillaryClint (test) 的大作中提到：]
:A=1;b=1
:For I=3 to n
: A<=b ? A+=b : b+=a
:End
:Return a<=b ? B : a
:☆ 发自 iPhone 买买提 1.23.01 |
