大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=1,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)
在C++中可以有多种方法求斐波那契数列
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数k,要求菲波那契数列中第k个数是多少。
题目链接:
OpenJudge NOI 1.5 17:菲波那契数列
t = n1 + n2;
n2 = n1;
n1 = t;
时间内复杂度: O ( n ) O(n) O(n),空间复杂度: O ( 1 ) O(1) O(1)
#includeusing namespace std;
int main()
{int k, n2 = 1, n1 = 1, t;//n2,n1是当前求出的倒数第二项,和最后一项
cin >>k;
for(int i = 3; i<= k; ++i)
{t = n1 + n2;
n2 = n1;
n1 = t;
}
cout<< n1;
return 0;
}
2. 递推法a[i]
为斐波那契数列第i项a[i] = a[i-1]+a[i-2]
时间内复杂度: O ( n ) O(n) O(n),空间复杂度: O ( n ) O(n) O(n)
#includeusing namespace std;
int main()
{int k, a[50];//a[i]为斐波那契数列第i项
a[1] = a[2] = 1;
cin >>k;
for(int i = 3; i<= k; ++i)
a[i] = a[i-1] + a[i-2];
cout<< a[k];
return 0;
}
3. 递归法(一般)时间内复杂度: O ( 2 n ) O(2^n) O(2n),空间复杂度: O ( n ) O(n) O(n)
#includeusing namespace std;
int fib(int k)//求斐波那契数列第k项
{if(k == 1 || k == 2)
return 1;
else
return fib(k - 1) + fib(k - 2);
}
int main()
{int k;
cin >>k;
cout<< fib(k);
return 0;
}
同一种思路,用栈将递归转为非递归写法
#includeusing namespace std;
int main()
{stackstk;
int n, r = 0, m;
cin >>n;
stk.push(n);
while(stk.empty() == false)
{m = stk.top();//出栈
stk.pop();
if(m == 2 || m == 1)//如果遇到第二项或第一项,直接把值加到结果res中
r += 1;
else
{//把后两项入栈
stk.push(m-1);
stk.push(m-2);
}
}
cout<< r;
return 0;
}
用以上两段代码提交【OpenJudge NOI 1.5 17:菲波那契数列】会超时。该算法时间复杂度过高了,输入40时,基本要1秒后才能得到结果。
4. 记忆化递归法在递归算法的基础上增加记忆状态:a[i]表示斐波那契数列的第i项
在递归时,如果要求斐波那契数列第i项,先看这一项是否已经求出来过。如果已经求出过,那么直接取值。在求出一项后,将其存入记忆状态数组中。
时间内复杂度:
O
(
n
)
O(n)
O(n),空间复杂度:
O
(
n
)
O(n)
O(n)
#includeusing namespace std;
int a[50];//a[i]:斐波那契数列第i项
int fib(int k)//求斐波那契数列第k项
{if(a[k] >0)
return a[k];
else
return a[k] = fib(k-1) + fib(k-2);
}
int main()
{int k;
cin >>k;
a[1] = a[2] = 1;
cout<< fib(k);
return 0;
}
5. 尾递归法当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。
尾递归调用结束,上一次调用也就结束了,所以没有必要存储上一次调用中用到的临时变量。现代编译器都会针对这一特性对尾递归进行优化,减少算法的空间复杂度。
用g++编译时,加上-O2选项,即可开启尾递归优化。
时间内复杂度:
O
(
n
)
O(n)
O(n),空间复杂度:
O
(
1
)
O(1)
O(1)
#includeusing namespace std;
int fib(int n1, int n2, int k)//倒数第1项是n1,倒数第2项是n2,计算k-1次
{if(k == 1)
return n2;
else
return fib(n1+n2, n1, k-1);
}
int main()
{int k;
cin >>k;
cout<< fib(1, 1, k);
return 0;
}
6. 公式法已知求斐波那契数列的通项公式
F
n
=
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
5
F_n = \frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}
Fn=5
(21+5
)n−(21−5
)n
输入n,代入公式,即可求值
时间内复杂度:
O
(
1
)
O(1)
O(1),空间复杂度:
O
(
1
)
O(1)
O(1)
#includeusing namespace std;
int main()
{int n;
cin >>n;
cout<< int((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧