java实现斐波那契数列的3种方法_java

先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案。去面试的时候，由于面试前天晚上11点钟才到阿里巴巴指定面试城市，找到旅馆住下基本都1点多，加上晚上完全没有睡好，直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧，提前做好准备还是很重要滴)，面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了，悲催！！)，面试快结束的时候面试官问的我问题就是关于费波那西数列，当时头脑完全浆糊，只知道要设置三个变量或者用List先初始化，当写到for循环的时候，脑袋简直浆糊的不能再浆糊了，没写出来，最后只能在面试官的步步诱导下写出了下面的第一种方式，很不应该呀；从现在来看阿里只是把粗枝大叶的把整个应用的框架搭建起来了，真是变革、挖金的黄金期(有能力的大虾赶紧去)，毕竟阿里巴巴手中99%的数据都是重要数据而向百度这类的主推搜索的巨头99%数据都是垃圾相比，对于数据分析来说，阿里更能通过对手中掌握的多种多样的用户详细数据进行分析，更能精确定位用户的品味及需求，为精确推送和精准广告推送提供更好的服务。如果说腾讯未来的梦想是做用户生活中的水电气的话，那阿里可能实现的未来梦想就是用户的衣食住行外加代收水电气等等，O(∩_∩)O~还是转入正题吧。
   对于优秀的算法设计员来说，在程序功能主体实现的基础上无非关心两个东西，一个设计算法的时间复杂度，一个是空间复杂度(说白了就是执行一个程序所用的时间和占用的内存空间)；在根据不同的应用场景的基础上，一般充满智慧的算法设计师会在时间和空间两个相对矛盾的资源中寻求到平衡点，如实时性要求高的系统一般会以空间资源换取时间或者对于常用到的对象一般会常驻内存以提高响应时间(缓存技术和现在比较流行NoSQL中大多是内存数据库都是如此)，对于内存资源比较宝贵的嵌入式系统而言一般会以时间上的延迟来换取时间。
下面从费波那西数列三个实现上来说说，怎么才能真正设计出真正符合实际应用场景的优秀算法
首先说说费波那西数列：
从文字上说，费波那西数列由0和1开始，之后的费波那西系数就由之前的两数相加，数列形式如下：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
在数学上，是以递归的方法来定义：
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}

实现需求：输入序号n返回得到对应费波那西数
程序实现1——函数自迭代

复制代码 代码如下:

/**
  * 函数自迭代
  * @Title: fnType1
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int
  * @throws Exception
  */
 public int fnType1(int n)throws Exception{
  if(n==0){
   return 0;
  }else if(n==1||n==2){
   return 1;
  }else if(n>2){
   int temp=fnType1(n-1)+fnType1(n-2);
   if(temp<0){
    throw new Exception("Invalid value for int type, too larage");
   }else{
    return temp;
   }
  }else{
   throw new Exception("IllegalArgument value for n,please enter n>=0 ");
  }
 }

此种方式缺点：大量迭代不断消耗栈空间(搞web开发调试维护的都应该知道服务器栈资源的可贵，如果大量并发调用迭代导致服务器栈资源迟迟得不到回收，而导致web服务器崩溃)，效率底，函数自闭性比较弱(优秀的接口应该对输入输出可能出现的错误信息进行捕捉，并提供清楚明了的处理结果)，很容易出现错误，调试困难，实际应用中一般不建议使用这种方式，使用时迭代次数也不能超过3次；
程序实现2——时间换空间

复制代码 代码如下:

/**
  * 时间换空间
  * @Title: fnType2
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int (n<0 return -1,beyond max int size return -2)
  * @throws
  */
 public int fnType2(int n){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=n;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
  }
  return result;
 }

此方法主要使用于:使用场景一：对于对象或变量使用次数比较少，使用一次以后就不会再使用的场景；使用场景二：对于内存资源比较稀缺的实时性要求不是太高的嵌入式系统设计中多会采用此种方式；
程序实现3——空间换取时间

复制代码 代码如下:

 private static List<Integer> fnData=new ArrayList<Integer>();
 private static final int maxSize=50000;
 /**
  * 初始化器
  * @Title: setFnData
  * @Description: TODO
  * @param    
  * @return void
  * @throws
  */
 private static  void setFnData(){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=maxSize;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
   fnData.add(result);
  }
 }
 /**
  * 对外接口
  * @Title: getFnData
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int <span style="font-family: sans-serif;">(n beyond fnData.size() and n<0 return -1)</span>
  * @throws
  */
 public int getFnData(int n){
  if(fnData.size()==0){
   setFnData();
  }
  if(fnData.size()>n&&n>=0){
   return fnData.get(n);
  }else{
   return -1;
  }
 }

此方法一般用于：对象或变量在程序运行的整个生命周期都存在或频繁调用的场景，如调用外部WebService接口、抽象持续化层、常用配置文件参数加载等等
测试用例：

复制代码 代码如下:

package com.dbc.yangg.swing.test;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入序号n返回得到对应费波那西数
 * @ClassName: Init
 * @Description: TODO
 * @author guoyang2011@gmail.com
 * @date 2014年1月10日 下午7:52:13
 *
 */
public class Init {
 /**
  * 函数自迭代
  * @Title: fnType1
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int
  * @throws Exception
  */
 public int fnType1(int n)throws Exception{
  if(n==0){
   return 0;
  }else if(n==1||n==2){
   return 1;
  }else if(n>2){
   int temp=fnType1(n-1)+fnType1(n-2);
   if(temp<0){
    throw new Exception("Invalid value for int type, too larage");
   }else{
    return temp;
   }
  }else{
   throw new Exception("IllegalArgument value for n,please enter n>=0 ");
  }
 }
 /**
  * 时间换空间
  * @Title: fnType2
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int (n<0 return -1,beyond max int size return -2)
  * @throws
  */
 public int fnType2(int n){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=n;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
  }
  return result;
 }
 private static List<Integer> fnData=new ArrayList<Integer>();
 private static final int maxSize=50000;
 /**
  * 空间换时间
  * @Title: setFnData
  * @Description: TODO
  * @param    
  * @return void
  * @throws
  */
 private static  void setFnData(){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=maxSize;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
   fnData.add(result);
  }
 }
 /**
  *
  * @Title: getFnData
  * @Description: TODO
  * @param @param n
  * @param @return   
  * @return int (n beyond fnData.size() and n<0 return -1)
  * @throws
  */
 public int getFnData(int n){
  if(fnData.size()==0){
   setFnData();
  }
  if(fnData.size()>n&&n>=0){
   return fnData.get(n);
  }else{
   return -1;
  }
 }
 /**
  *
  * @Title: main
  * @Description: TODO
  * @param @param argv   
  * @return void
  * @throws
  */
 public static void main(String[] argv){
  Init init=new Init();
  int n=46;
  try {
   System.out.println("Type1="+init.fnType1(n));
  } catch (Exception e) {
   // TODO Auto-generated catch block
   System.out.println(e.getMessage());
  }
  System.out.println("Type2="+init.fnType2(n));
  System.out.println("Type3="+init.getFnData(n));
 }
}

输出结果：

复制代码 代码如下:

Type1=1836311903 
Type2=1836311903 
Type3=1836311903 

对于算法设计，不要盲目遵循概念，概念是死的，人是活的（在这个需要crazy man的时代，有想法比循规蹈矩更有优势），只用结合具体的应用场景才能设计出优秀的算法和结构。
吐槽一下：个人认为优秀的数据结构设计可以简化算法设计的复杂度提高代码的可读性、程序的扩展性及执行效率；
再吐槽一下：做需求分析的时候应该遵循三点原则：1.从用户角度及其思维方式分析；2.用户说的不一定是他们真正想要的；3.用户说的不一定是对的。做程序开发遵循原则：积极提升自身品味，站在用户使用角度和使用场景分析功能；例如你做后台接口开发，你的用户就是接口调用者，你应该考虑接口功能是什么，使用者在什么情况下会调用，传入参数可能导致哪些异常，你的接口实现中可能出现哪些异常并对可能出现的异常进行捕获，清楚明了的输出，良好的函数自闭性；如果你是搞前台，那你应该在保证业务实现的基础上从用户使用习惯等方面把自己当做使用者来设计UI。很有意思对不，需求、开发多了自然就明白了O(∩_∩)O~。

时间： 2024-09-08 19:48:54

java实现斐波那契数列的3种方法_java的相关文章

打印菱形以及斐波纳契数列的几种解法介绍

1.编写程序,打印*菱形推出第i行要打印的空白个数及*号个数,用for循环依次打印各行 复制代码 代码如下: #include<stdio.h> //总共要打印2*n-1行,逐行打印 void print1(int n) { int i,j; for(i=1;i<=n;i++){//打印1至n行 for(j=1;j<=n-i;j++)//打印n-i个空格 printf(" "); for(j=1;j<=2*i-1;j++)//打印2*i-1个*号 prin

C++输出斐波那契数列的两种实现方法_C 语言

定义: 斐波那契数列指的是这样一个数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...这个数列从第三项开始,每一项都等于前两项之和. 以输出斐波那契数列的前20项为例: 方法一:比较标准的做法,是借助第三个变量实现的. 复制代码 代码如下: #include<iostream>  using namespace std;int main(){    int f1=0,f2=1,t,n=1;    cout<<"数列第1个

打印菱形以及斐波纳契数列的几种解法介绍_C 语言

1.编写程序,打印*菱形推出第i行要打印的空白个数及*号个数,用for循环依次打印各行 复制代码 代码如下: #include<stdio.h>//总共要打印2*n-1行,逐行打印void print1(int n){ int i,j; for(i=1;i<=n;i++){//打印1至n行  for(j=1;j<=n-i;j++)//打印n-i个空格      printf(" ");  for(j=1;j<=2*i-1;j++)//打印2*i-1个*号 

java数学归纳法非递归求斐波那契数列的方法_java

本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege

用PHP迭代器来实现一个斐波纳契数列

斐波纳契数列通常做法是用递归实现,当然还有其它的方法.这里现学现卖,用PHP的迭代器来实现一个斐波纳契数列,几乎没有什么难度,只是把类里的next()方法重写了一次.注释已经写到代码中,也是相当好理解的. <?php /* *@author nicesunboy@gmail.com */ class Fibonacci implements Iterator { private $previous = 1; private $current = 0; private $key = 0; publ

输出斐波那契数列的算法

斐波那契数列(Fibonacci polynomial),又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.-- 要求编程输出这样的一组数,比如输出10个数的序列 /** * @param i 第n个数 * @param j 第n+1个数 * @param n 输出个数 */ public static void ff( int i,int j,int n){ int m=1; System.out.print(i+","); while(m++<n)

java-关于斐波那契数列的求和问题的解答

问题描述 关于斐波那契数列的求和问题的解答 .有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一 对兔子,假如兔子都不死,问每个月的兔子总数为多少? 1.程序分析: 兔子的规律为数列1,1,2,3,5,8,....;求Java程序代码 解决方案 斐波那契数列及其求和 解决方案二: a[i]=a[i-1]+a[i-2]就行了呗,java难道难写吗 解决方案三: public class Test { public static void main(String[]

猆波那契数列-斐波那契数列求和～～～～～

问题描述 斐波那契数列求和----- 如何用C语言程序求斐波那契数列的前10项和,哪位大牛帮帮忙.还有什么水仙花问题 解决方案 用c++随便写的#include#include #include using namespace std;int main(){ int sum=1; int *a = new int[10]; vectorv; a[0] = 0; a[1] = 1; for (int i = 2; i < 10; i++) { a[i] = a[i - 1] + a[i - 2];

斐波那契数列(Fabonacci)兔子练习题

Java练习题:兔子问题       此问题又叫斐波那契数列(Fabonacci),是最先研究这个数列的人是比萨的列奥那多(又名费波那契),他描述兔子生长的数目时用上了这数列. 第一个月有一对刚诞生的兔子 第二个月之后它们可以生育 每月每对可生育的兔子会诞生下一对新兔子 兔子永不死去        假设在 n 月有新生及可生育的兔子总共 a 对,n+1 月就总共有 b 对.在 n+2 月必定总共有 a+b 对: 因为在 n+2 月的时候,所有在 n 月就已存在的 a 对兔子皆已可以生育并诞下 a