3 Möglichkeiten zur Implementierung der Fibonacci-Sequenz in Java

Lassen Sie mich darüber sprechen, warum ich dies zuerst geschrieben habe. Dies wurde ausschließlich durch einen schrecklichen Mord verursacht, der durch ein Interview bei Alibaba verursacht wurde. Als ich zum Vorstellungsgespräch ging, kam ich am Abend vor dem Vorstellungsgespräch um 11 Uhr an, bis ich ein Hotel fand, in dem ich übernachten konnte Nacht, was direkt zu den schlechten Interviewergebnissen am nächsten Tag führte (denn die großen Garnelen, die einen Job suchen, sollten den kleinen Garnelen nichts von der Tragödie erzählen, es ist immer noch wichtig, sich im Voraus vorzubereiten), dauerte das Interview mehr als eine Stunde (als ich nach dem Interview zurückkam, wäre ich beim Gehen fast eingeschlafen, so traurig!!) Am Ende des Interviews stellte mir der Interviewer eine Frage zur Fibonacci-Folge. Zu diesem Zeitpunkt war ich völlig verwirrt Ich wusste nur, dass ich drei Variablen setzen oder sie mit einer Liste initialisieren sollte, aber ich konnte nicht mehr verwirrt sein und habe sie am Ende nicht ausgeschrieben. Ich konnte die erste Methode nur Schritt für Schritt schreiben. Von nun an hat Ali die gesamte Anwendung nicht mehr verwendet Eine goldene Zeit des Wandels und des Goldabbaus (die fähigen Garnelen sollten schnell verschwinden) Für die Datenanalyse ist Alibaba besser in der Lage, die verschiedenen detaillierten Benutzerdaten zu analysieren, die Vorlieben und Bedürfnisse der Benutzer genauer zu lokalisieren und bessere Lösungen für präzisen Push und präzisen Werbe-Push bereitzustellen. Wenn der Zukunftstraum von Tencent darin besteht, das Leben der Benutzer mit Wasser und Strom zu versorgen, dann besteht der möglicherweise verwirklichte Zukunftstraum von Alibaba darin, die Benutzer mit Grundbedürfnissen, Nahrungsmitteln, Wohnraum und Transportmitteln sowie der Sammlung von Wasser und Strom usw. zu versorgen. O(∩_ ∩)O~ kommen wir zum Punkt.
Für exzellente Algorithmusdesigner gibt es nur zwei Dinge, die sie basierend auf der Hauptimplementierung der Programmfunktion interessieren. Das eine ist die zeitliche Komplexität des Entwurfsalgorithmus und das andere ist die räumliche Komplexität (um es ganz klar auszudrücken). ist die Zeit- und Raumkomplexität, die zum Ausführen eines Programms verwendet wird. Basierend auf verschiedenen Anwendungsszenarien finden intelligente Algorithmusdesigner beispielsweise einen Gleichgewichtspunkt zwischen den beiden relativ widersprüchlichen Ressourcen Zeit und Raum Bei Echtzeitanforderungen werden im Allgemeinen Speicherplatzressourcen gegen Zeit ausgetauscht oder häufig verwendete Objekte werden im Allgemeinen im Speicher gespeichert, um die Antwortzeit zu verbessern (dies gilt für die Caching-Technologie und die meisten In-Memory-Datenbanken in NoSQL, die heute für eingebettete Systeme beliebt sind). Wo Speicherressourcen relativ kostbar sind, ist dies im Allgemeinen der Fall. Tauschen Sie Verzögerungen gegen Zeit aus.
Lassen Sie uns über die drei Implementierungen der Fibonacci-Folge sprechen und wie wir wirklich einen hervorragenden Algorithmus entwerfen können, der das tatsächliche Anwendungsszenario wirklich erfüllt.
Lassen Sie uns zunächst über die Fibonacci-Folge sprechen:
Im wahrsten Sinne des Wortes Die Fibonacci-Folge beginnt mit 0 und 1 und die nachfolgenden Fibonacci-Koeffizienten sind die Summe der beiden vorherigen Zahlen. Das Sequenzformat ist wie folgt:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,…………
In der Mathematik wird es rekursiv definiert:
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}

Implementierungsanforderungen: Geben Sie die Seriennummer n ein und geben Sie die entsprechende Fibonacci-Zahl zurück
Programmimplementierung 1 – Funktion selbst -iteration

/**
  * 函数自迭代
  * @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 ");
  }
 }

Nachteile dieser Methode: Eine große Anzahl von Iterationen verbraucht kontinuierlich Stack-Speicherplatz (jeder, der sich mit Webentwicklung, Debugging und Wartung beschäftigt, sollte den Wert von Server-Stack-Ressourcen kennen. Wenn eine große Anzahl von Gleichzeitige Iterationen werden aufgerufen. Dadurch können die Server-Stack-Ressourcen längere Zeit nicht recycelt werden, was zum Absturz des Webservers führt. Die Effizienz ist gering und die Funktion relativ schwach (eine hervorragende Schnittstelle sollte die möglicherweise auftretenden Fehlerinformationen erfassen). erscheint in der Ein- und Ausgabe und liefert klare Verarbeitungsergebnisse. Diese Methode wird in der Praxis im Allgemeinen nicht empfohlen und die Anzahl der Iterationen darf das Dreifache nicht überschreiten 2 – Zeit für Platz

/**
  * 时间换空间
  * @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;
 }

Diese Methode wird hauptsächlich verwendet in: Verwendungsszenario 1: Szenarien, in denen Objekte oder Variablen selten verwendet werden und nach einmaliger Verwendung nicht mehr verwendet werden; Verwendungsszenario 2: Eingebettete Anwendungen, in denen Die Speicherressourcen sind knapp und die Echtzeitanforderungen sind nicht zu hoch. Diese Methode wird häufig im Systemdesign verwendet.

Programmimplementierung 3 - Raumaustauschzeit

 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;
  }
 }

Diese Methode wird im Allgemeinen verwendet: Objekte oder Variablen Aufrufszenarien existieren oder kommen während des gesamten Lebenszyklus des Programms häufig vor, z. B. der Aufruf einer externen WebService-Schnittstelle, der abstrakten Persistenzschicht, das Laden allgemeiner Konfigurationsdateiparameter usw.

Testfall:

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 fnData=new ArrayList();
 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));
 }
}

Ausgabe Ergebnis:

Type1=1836311903  
Type2=1836311903  
Type3=1836311903

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

更多java实现斐波那契数列的3种方法相关文章请关注PHP中文网！