c#网站开发需要的技术,青岛软件制作,网页界面设计首页,电商如何推广自己的产品题目描述
斐波那契数列#xff08;Fibonacci sequence#xff09;#xff0c;又称黄金分割数列#xff0c;因数学家莱昂纳多斐波那契#xff08;Leonardo Fibonacci#xff09;以兔子繁殖为例子而引入#xff0c;故又称为“兔子数列”#xff0c;指的是这样一个数列Fibonacci sequence又称黄金分割数列因数学家莱昂纳多·斐波那契Leonardo Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列0、1、1、2、3、5、8、13、21、34、……在数学上斐波那契数列以如下被以递推的方法定义F(0)0F(1)1, F(n)F(n - 1)F(n - 2)n ≥ 2n ∈ N*在现代物理、准晶体结构、化学等领域斐波纳契数列都有直接的应用为此美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志用于专门刊载这方面的研究成果。
解法一通项公式(O(1)) 代码表示
int ferbo(int n){return (sqrt(5)/5)*(pow((1sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
}
解法二递归求解O(1.618^n)
#includeiostream
using namespace std;int fac(int x){if(x1 || x2){return 1;}if(x2){return fac(x-1)fac(x-2);}return 0;
}
int main()
{for(int i 1; i20;i){coutfac(i) ;}coutendl;return 0;
}//1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765解法三动态规划On
#includeiostream
using namespace std;
int fac[20];
int main()
{fac[1]fac[2]1;for(int i 3;i20;i){//此处使用变量a,b,c也可。 fac[i] fac[i-1]fac[i-2];}for(int i 1;i 20;i){coutfac[i] ;}coutendl;return 0;
}
//1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765解法四矩阵快速幂(O(logn)
矩阵公式 F(n1)1*F(n)1*F(n-1)F(n)1*F(n)0*F(n-1)F(n)1*F(n-1)1*F(n-2)F(n-1)1*F(n-1)0*F(n-2)推导: 结论:只需要求出 ,输出a[0][1] 或a[1] [0]都是F(n)的解.
快速幂
mod c只是为了防止数过大,不利于计算. 当数很小 时,加不加没啥区别. 例如求a^n, (a2)初始时,ans1;
如果n4,则计算步骤如下:
aa*aa^2 nn/22
aa*aa^2 * a^2 a^4 nn/21
ansans*aa^4如果n5,则计算步骤如下
因为n为奇数ansans*a aa*aa^2 nn/22
aa*aa^2 * a^2 a^4 nn/21
ansans^aa^5如果n9,则计算步骤如下
因为n为奇数ansans*a aa*aa^2 nn/24
aa*aa^4 nn/22
aa*aa^8 nn/21
ansans^aa^9这样就把8次运算减少到了四次.而且也放置了数值过大的问题.
总结:当n为奇数时,ansans*a,这样相等于n-1变成了偶数.
快速幂代码
#includeiostream
using namespace std;
int main() {int n,p,ans1,a2;cinnp;while(n) {if(n1) {ans ans * a %p;}a * a % p;n/2;}coutansendl;return 0;
}
//16 1000000
//65536矩阵快速幂 矩阵乘法:
原理矩阵相乘最重要的方法是一般矩阵乘积。它只有在第一个矩阵的栏数column和第二个矩阵的列数row相同时才有定义。一般单指矩阵乘积时指的便是一般矩阵乘积。若A为m×n矩阵B为n×p矩阵则他们的乘积AB会是一个m×p矩阵。其乘积矩阵的元素如下面式子得出 实现代码:
struct mat{int n, m;double data[MAXN][MAXN];
};int mul(mat c, const mat a, const mat b){int i, j, k;if (a.m ! b.n)return 0;c.n a.n;c.m b.m;for (i 0; i c.n; i)for (j 0; j c.m; j)for (c.data[i][j] k 0; k a.m; k)c.data[i][j] a.data[i][k] * b.data[k][j];return 1;
}例题:POJ3070
以上内容参考自 陈小玉老师的数据结构与算法 365天特训营
