题解 | #斐波那契数列#
斐波那契数列
https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3
1、初始化两个栈。
2、设置两个栈s1、s2，分别入栈，首先s1入栈，然后s2入栈，下一个再入s1。
3、n=1时s1[0]=1;n=2时s2[0]=1，依次下去s1[1]=s1[0]+s2[0];s2[1]=s1[1]+s2[0]。
4、将n分为奇数和偶数之分，n为奇数时从s1栈出栈（栈顶）；n为偶数时从s2出栈。
/**
*
* @param n int整型
* @return int整型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
static int stack1[100];
static int top1=0;
static int stack2[100];
static int top2=0;
int Fibonacci(int n ) {
// write code here
stack1[top1]=1;
stack2[top2]=1;
if(n == 1)
{
return stack1[top1];
}
if(n == 2)
{
return stack2[top2];
}
for (int count=3;count <= n;count++)
{
if (count%2==1)
{
top1=(count-1)/2;
stack1[top1]=stack1[top1-1]+stack2[top1-1];
}
if (count%2 == 0)
{
top2=(count-2)/2;
stack2[top2]=stack1[top2]+stack2[top2-1];
}
}
if(n%2==0)
return stack2[top2];
return stack1[top1];
}
投递旷视等公司10个岗位 >
