java實(shí)現(xiàn)斐波那契數(shù)列的3種方法
先說說為什么寫這個(gè)吧,去面試的時(shí)候，由于面試前天晚上11點(diǎn)鐘才到阿里巴巴指定面試城市，找到旅館住下基本都1點(diǎn)多，加上晚上完全沒有睡好，直接導(dǎo)致第二天面試效果很不好(對(duì)于那些正在找工作的大蝦們不要向小蝦一下悲劇，提前做好準(zhǔn)備還是很重要滴)，面試大概進(jìn)行了一個(gè)多小時(shí)(面試結(jié)束回去的時(shí)候基本走路都快睡著了，悲催??！)，面試快結(jié)束的時(shí)候面試官問的我問題就是關(guān)于費(fèi)波那西數(shù)列，當(dāng)時(shí)頭腦完全漿糊，只知道要設(shè)置三個(gè)變量或者用List先初始化，當(dāng)寫到for循環(huán)的時(shí)候，腦袋簡(jiǎn)直漿糊的不能再漿糊了，沒寫出來，最后只能在面試官的步步誘導(dǎo)下寫出了下面的第一種方式，很不應(yīng)該呀；從現(xiàn)在來看阿里只是把粗枝大葉的把整個(gè)應(yīng)用的框架搭建起來了，真是變革、挖金的黃金期(有能力的大蝦趕緊去)，畢竟阿里巴巴手中99%的數(shù)據(jù)都是重要數(shù)據(jù)而向百度這類的主推搜索的巨頭99%數(shù)據(jù)都是垃圾相比，對(duì)于數(shù)據(jù)分析來說，阿里更能通過對(duì)手中掌握的多種多樣的用戶詳細(xì)數(shù)據(jù)進(jìn)行分析，更能精確定位用戶的品味及需求，為精確推送和精準(zhǔn)廣告推送提供更好的服務(wù)。如果說騰訊未來的夢(mèng)想是做用戶生活中的水電氣的話，那阿里可能實(shí)現(xiàn)的未來夢(mèng)想就是用戶的衣食住行外加代收水電氣等等，O(∩_∩)O~還是轉(zhuǎn)入正題吧。
對(duì)于優(yōu)秀的算法設(shè)計(jì)員來說，在程序功能主體實(shí)現(xiàn)的基礎(chǔ)上無非關(guān)心兩個(gè)東西，一個(gè)設(shè)計(jì)算法的時(shí)間復(fù)雜度，一個(gè)是空間復(fù)雜度(說白了就是執(zhí)行一個(gè)程序所用的時(shí)間和占用的內(nèi)存空間)；在根據(jù)不同的應(yīng)用場(chǎng)景的基礎(chǔ)上，一般充滿智慧的算法設(shè)計(jì)師會(huì)在時(shí)間和空間兩個(gè)相對(duì)矛盾的資源中尋求到平衡點(diǎn)，如實(shí)時(shí)性要求高的系統(tǒng)一般會(huì)以空間資源換取時(shí)間或者對(duì)于常用到的對(duì)象一般會(huì)常駐內(nèi)存以提高響應(yīng)時(shí)間(緩存技術(shù)和現(xiàn)在比較流行NoSQL中大多是內(nèi)存數(shù)據(jù)庫都是如此)，對(duì)于內(nèi)存資源比較寶貴的嵌入式系統(tǒng)而言一般會(huì)以時(shí)間上的延遲來換取時(shí)間。
下面從費(fèi)波那西數(shù)列三個(gè)實(shí)現(xiàn)上來說說，怎么才能真正設(shè)計(jì)出真正符合實(shí)際應(yīng)用場(chǎng)景的優(yōu)秀算法
首先說說費(fèi)波那西數(shù)列：
從文字上說，費(fèi)波那西數(shù)列由0和1開始，之后的費(fèi)波那西系數(shù)就由之前的兩數(shù)相加，數(shù)列形式如下：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
在數(shù)學(xué)上，是以遞歸的方法來定義：
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}
實(shí)現(xiàn)需求：輸入序號(hào)n返回得到對(duì)應(yīng)費(fèi)波那西數(shù)
程序?qū)崿F(xiàn)1——函數(shù)自迭代
/**
* 函數(shù)自迭代
* @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 ");
}
}
此種方式缺點(diǎn)：大量迭代不斷消耗棧空間(搞web開發(fā)調(diào)試維護(hù)的都應(yīng)該知道服務(wù)器棧資源的可貴，如果大量并發(fā)調(diào)用迭代導(dǎo)致服務(wù)器棧資源遲遲得不到回收，而導(dǎo)致web服務(wù)器崩潰)，效率底，函數(shù)自閉性比較弱(優(yōu)秀的接口應(yīng)該對(duì)輸入輸出可能出現(xiàn)的錯(cuò)誤信息進(jìn)行捕捉，并提供清楚明了的處理結(jié)果)，很容易出現(xiàn)錯(cuò)誤，調(diào)試?yán)щy，實(shí)際應(yīng)用中一般不建議使用這種方式，使用時(shí)迭代次數(shù)也不能超過3次；
程序?qū)崿F(xiàn)2——時(shí)間換空間
/**
* 時(shí)間換空間
* @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;
}
此方法主要使用于:使用場(chǎng)景一：對(duì)于對(duì)象或變量使用次數(shù)比較少，使用一次以后就不會(huì)再使用的場(chǎng)景；使用場(chǎng)景二：對(duì)于內(nèi)存資源比較稀缺的實(shí)時(shí)性要求不是太高的嵌入式系統(tǒng)設(shè)計(jì)中多會(huì)采用此種方式；
程序?qū)崿F(xiàn)3——空間換取時(shí)間
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);
}
}
/**
* 對(duì)外接口
* @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;
}
}
此方法一般用于：對(duì)象或變量在程序運(yùn)行的整個(gè)生命周期都存在或頻繁調(diào)用的場(chǎng)景，如調(diào)用外部WebService接口、抽象持續(xù)化層、常用配置文件參數(shù)加載等等
測(cè)試用例：
package com.dbc.yangg.swing.test;
import java.util.ArrayList;
import java.util.List;
/**
* 輸入序號(hào)n返回得到對(duì)應(yīng)費(fèi)波那西數(shù)
* @ClassName: Init
* @Description: TODO
* @author guoyang2011@gmail.com
* @date 2014年1月10日 下午7:52:13
*
*/
public class Init {
/**
* 函數(shù)自迭代
* @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 ");
}
}
/**
* 時(shí)間換空間
* @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;
/**
* 空間換時(shí)間
* @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));
}
}
輸出結(jié)果：
Type1=1836311903
Type2=1836311903
Type3=1836311903
對(duì)于算法設(shè)計(jì)，不要盲目遵循概念，概念是死的，人是活的（在這個(gè)需要crazy man的時(shí)代，有想法比循規(guī)蹈矩更有優(yōu)勢(shì)），只用結(jié)合具體的應(yīng)用場(chǎng)景才能設(shè)計(jì)出優(yōu)秀的算法和結(jié)構(gòu)。
吐槽一下：個(gè)人認(rèn)為優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)可以簡(jiǎn)化算法設(shè)計(jì)的復(fù)雜度提高代碼的可讀性、程序的擴(kuò)展性及執(zhí)行效率；
再吐槽一下：做需求分析的時(shí)候應(yīng)該遵循三點(diǎn)原則：1.從用戶角度及其思維方式分析；2.用戶說的不一定是他們真正想要的；3.用戶說的不一定是對(duì)的。做程序開發(fā)遵循原則：積極提升自身品味，站在用戶使用角度和使用場(chǎng)景分析功能；例如你做后臺(tái)接口開發(fā)，你的用戶就是接口調(diào)用者，你應(yīng)該考慮接口功能是什么，使用者在什么情況下會(huì)調(diào)用，傳入?yún)?shù)可能導(dǎo)致哪些異常，你的接口實(shí)現(xiàn)中可能出現(xiàn)哪些異常并對(duì)可能出現(xiàn)的異常進(jìn)行捕獲，清楚明了的輸出，良好的函數(shù)自閉性；如果你是搞前臺(tái)，那你應(yīng)該在保證業(yè)務(wù)實(shí)現(xiàn)的基礎(chǔ)上從用戶使用習(xí)慣等方面把自己當(dāng)做使用者來設(shè)計(jì)UI。很有意思對(duì)不，需求、開發(fā)多了自然就明白了O(∩_∩)O~。
相關(guān)文章
SpringBoot全局配置long轉(zhuǎn)String丟失精度的問題解決
web項(xiàng)目中，Java后端傳過來的Long/long類型，前端JS接收會(huì)丟失精度。那么應(yīng)該如何解決，本文就來介紹一下幾種方法，感興趣的可以了解一下2021-08-08
IntelliJ IDEA下SpringBoot如何指定某一個(gè)配置文件啟動(dòng)項(xiàng)目
這篇文章主要介紹了IntelliJ IDEA下SpringBoot如何指定某一個(gè)配置文件啟動(dòng)項(xiàng)目問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-09-09
Eclipse+Java+Swing實(shí)現(xiàn)斗地主游戲(代碼)
這篇文章主要介紹了Eclipse+Java+Swing實(shí)現(xiàn)斗地主游戲并附上詳細(xì)的代碼實(shí)現(xiàn)，正在學(xué)習(xí)的你可以當(dāng)小練習(xí)練練，希望對(duì)你有所幫助2022-01-01
這篇文章主要介紹了Java 如何使用JDBC連接數(shù)據(jù)庫，幫助大家更好的理解和學(xué)習(xí)使用Java，感興趣的朋友可以了解下2021-02-02
這篇文章主要介紹了Spring中如何獲取Bean方法上的自定義注解,基本的思路就是通過Spring提供的ApplicationContext#getBeansWithAnnotation+反射來實(shí)現(xiàn)，需要的朋友可以參考下2023-06-06
Java圖形界面之JFrame,JLabel,JButton詳解
這篇文章主要介紹了Java圖形界面之JFrame、JLabel、JButton詳解,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04
ZooKeeper是一個(gè)樹形目錄服務(wù)，其數(shù)據(jù)模型和Uiix的文件目錄樹很類似，擁有一個(gè)層次化結(jié)構(gòu)，這篇文章主要介紹了ZooKeeper命令及JavaAPI操作代碼,需要的朋友可以參考下2023-03-03
Java實(shí)現(xiàn)HTTP請(qǐng)求的4種方式總結(jié)
這篇文章主要給大家介紹了關(guān)于Java實(shí)現(xiàn)HTTP請(qǐng)求的4種方式,在java開發(fā)中,經(jīng)常遇到需要調(diào)用第三方提供的接口服務(wù)的需求,文中給出了詳細(xì)的代碼示例,需要的朋友可以參考下2023-08-08
最近更新了idea2022.2版本，這是一個(gè)比較大的軟件版本更迭，下面小編給大家介紹下idea2022.2?閃退的問題及解決方法,需要的朋友可以參考下2022-08-08
MybatisPlus搭建項(xiàng)目環(huán)境及分頁插件
Mybatis-Plus(簡(jiǎn)稱MP)是一個(gè)Mybatis的增強(qiáng)工具,在Mybatis的基礎(chǔ)上只做增強(qiáng)不做改變,為簡(jiǎn)化開發(fā)、提高效率而生,下面這篇文章主要給大家介紹了關(guān)于MybatisPlus搭建項(xiàng)目環(huán)境及分頁插件的相關(guān)資料,需要的朋友可以參考下2022-11-11