斐波那契数列—Java
2024-09-30 19:17:53
斐波那契数列想必大家都知道吧,如果不知道的话,我就再啰嗦一遍,
斐波那契数列为:1 2 3 5 8 13 ...,也就是除了第一项和第二项为1以外,对于第N项,有f(N)=f(N-1)+f(N-2)。
下面我用三种方法实现这个函数,分别是:递归,循环,矩阵。
递归方法:
public class Feibo {
//递归方法
public static int recFeiBo(int n) {
if(n<=0) {
return 0;
} if(n==1 || n==2) {
return 1;
} return recFeiBo(n-1) + recFeiBo(n-2);
} public static void main(String[] args) {
System.out.println(recFeiBo(6));
}
}
循环方法:
public class Feibo{
public static int recFeiBo(int n) {
if(n<=0) {
return 0;
} if(n==1 || n==2) {
return 1;
} int pre =1;
int temp =0;
int res =1; for(int i=1; i<=n-2; i++) {
temp = res;
res+=pre;
pre = temp;
} return res;
} public static void main(String[] args) {
System.out.println(recFeiBo(6));
}
}
矩阵的方法:
不知道你们有没有发现:
所以,最终求第N项数,就转化为求矩阵的n-2次方。
public class Feibo{
public static int recFeiBo(int n) {
if(n<=0) {
return 0;
}
if(n==1 || n==2) {
return 1;
} int[][] baseMatrix = {{1,1},{1,0}};
int[][] res = matrixPower(baseMatrix, n-2);
return res[0][0] + res[1][0];
} public static int[][] matrixPower(int[][] m, int n) {
int[][] temp = m;
int[][] res = new int[m.length][m[0].length]; for(int i=0; i<m.length; i++) {
res[i][i] = 1;
}
//n左移一位,并赋值给n
//下面的for循环是用来快速的求解矩阵的n次方的。可以参考我下一篇关于如何快求解高次方
for(;n!=0; n>>=1) {
//判断第0位是不是1
if((n&1)!=0) {
res = multiMtrix(res,temp);
}
temp= multiMtrix(temp, temp);
} return res;
} private static int[][] multiMtrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for(int i=0; i<m1.length; i++) {
for(int j=0; j<m2[0].length; j++) {
for(int k=0; k<m2.length; k++) {
res[i][j] += m1[i][k]*m2[k][j];
}
}
}
return res;
} public static void main(String[] args) {
System.out.println(recFeiBo(6));
}
}
其实斐波那契额数列问题就是可以总结为一类问题,就是让你求的当前值可以用函数表示的,f(n)=f(n-1)+f(n-2),这类问题你都可以用矩阵的方式去实现,比如爬楼梯问题,有n阶楼梯,每次只能跨1阶或2阶,归结出来就是s(n)=s(n-1)+s(n-2),初始值s(1)=1,s(2)=2.
最新文章
- matlab初学之textread
- 经典Linq实例语句
- 如何在win上搭建SVN服务器
- WCF android调用
- 去除NSString里面的空格
- (转)女生应该找一个玩ACM的男生
- C++之路进阶——hdu2222(Keywords Search)
- TWinControl与TControl的覆盖函数(TWinControl对TControl的10个消息覆盖函数,17个覆盖函数,私有虚函数仍可多态)
- 学而精计算机公共基础学习之路TEST2(程序设计基础)
- mysql 性能监控
- Cpython解释器下实现并发编程
- 51NOD1174 区间最大数 &;&; RMQ问题(ST算法)
- 【python】控制台输出颜色
- mysql 计算两点经纬度之间的距离含具体sql语句
- argparse - 命令行选项与参数解析
- 代理神器allproxy
- bzoj2564 集合的面积
- 组合测试(Combinatorial Test)/配对测试 (pairwise)
- http介绍
- /proc/sys 子目录的作用
热门文章
- 各种demo:css实现三角形,css大小梯形,svg使用
- useradd新建用户和权限分配
- swift 3.0 基础练习 面向对象 类的扩展
- 动态rem与1px边框问题的理解
- JARVIS 手机监控局域网内PC
- Swift 细节
- 推荐60个jQuery插件(转)
- Windows下搭建Git 服务器: BONOBO GIT SERVER + TortoiseGit
- /etc/shadow,/etc/passwd,/etc/shadow,/etc/passwd文件的内容解释
- UNIX 高手的 10 个习惯