3 façons d'implémenter la séquence de Fibonacci en Java

Laissez-moi vous expliquer pourquoi j'ai écrit ceci en premier. Cela a été entièrement causé par un horrible meurtre provoqué par une interview à Alibaba. Lorsque je suis allé à l'entretien, je suis arrivé à la ville d'entretien désignée par Alibaba à 23 heures la veille de l'entretien. Il m'a fallu presque 13 heures pour trouver un hôtel. De plus, je n'ai pas bien dormi la nuit. , ce qui a directement conduit aux mauvais résultats de l'entretien le lendemain (car Ces grosses crevettes qui recherchent un emploi ne devraient pas parler de la tragédie aux petites crevettes. Il est quand même important de se préparer à l'avance.) L'entretien a duré plus d'un an. heure (quand je suis rentré après l'interview, j'ai failli m'endormir en marchant, c'est tellement triste !!) À la fin de l'interview, l'intervieweur m'a posé une question sur la séquence de Fibonacci. À ce moment-là, mon esprit était complètement confus. Je savais seulement que je devais définir trois variables ou les initialiser avec une liste. Lorsque j'ai écrit la boucle for, mon esprit était complètement confus et je ne l'ai finalement pas écrite. Je n'ai pu écrire la première méthode ci-dessous que sous la direction de l'intervieweur, étape par étape. À partir de maintenant, Ali a simplement utilisé l'ensemble de l'application de manière imprudente. période dorée pour le changement et l'extraction de l'or (les crevettes capables devraient disparaître rapidement). Après tout, 99 % des données entre les mains d'Alibaba sont des données importantes, tandis que 99 % des données sont fournies aux géants de la recherche tels que Baidu. pour l'analyse des données, Alibaba est mieux à même d'analyser les diverses données utilisateur détaillées dont il dispose, de localiser plus précisément les goûts et les besoins des utilisateurs et de fournir de meilleures solutions pour une diffusion précise et une diffusion publicitaire précise. Si le rêve futur de Tencent est de fournir de l'eau et de l'électricité dans la vie des utilisateurs, alors le rêve futur d'Alibaba qui pourrait se réaliser est de fournir aux utilisateurs les produits de première nécessité, la nourriture, le logement et le transport, ainsi que la collecte d'eau et d'électricité, etc. O(∩_ ∩)O~ venons-en au fait.
Pour les excellents concepteurs d'algorithmes, il n'y a que deux choses qui les intéressent en fonction de l'implémentation principale de la fonction du programme. L'une est la complexité temporelle de l'algorithme de conception et l'autre est la complexité spatiale (pour le dire franchement, elle). est la complexité temporelle et spatiale utilisée pour exécuter un programme) ; en fonction de différents scénarios d'application, les concepteurs d'algorithmes généralement intelligents trouveront un point d'équilibre entre les deux ressources relativement contradictoires de temps et d'espace. les exigences en temps réel utiliseront généralement les ressources spatiales sont échangées contre du temps ou les objets couramment utilisés résident généralement en mémoire pour améliorer le temps de réponse (cela est vrai pour la technologie de mise en cache et la plupart des bases de données en mémoire dans NoSQL qui sont désormais populaires pour les systèmes embarqués). là où les ressources mémoire sont relativement précieuses, c’est généralement le cas du délai d’échange en échange de temps.
Parlons des trois implémentations de la séquence de Fibonacci et de la manière dont nous pouvons véritablement concevoir un excellent algorithme qui répond réellement aux scénarios d'application pratiques.
Parlons d'abord de la séquence de Fibonacci :
Littéralement parlant, la séquence de Fibonacci commence avec 0 et 1, et les coefficients de Fibonacci suivants sont la somme des deux nombres précédents. Le format de séquence est le suivant :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. , 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,…………
En mathématiques, il est défini de manière récursive :
F_0=0
F_1=1
F_n = F_{n-1} F_{n-2>

Exigences d'implémentation : entrez le numéro de série n et renvoyez le numéro de Fibonacci correspondant
Implémentation du programme 1 - Auto-itération de la fonction

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

Inconvénients de cette méthode : un grand nombre d'itérations consomment continuellement de l'espace de pile (toute personne engagée dans le développement, le débogage et la maintenance Web doit connaître la valeur des ressources de la pile du serveur. Si un grand nombre d'itérations simultanées sont appelées, cela entraînera que les ressources de la pile du serveur ne soient pas recyclées pendant une longue période, provoquant le crash du serveur Web), l'efficacité est faible et la fonction est relativement faible (une excellente interface doit capturer les messages d'erreur possibles en entrée et en sortie et fournir des informations claires résultats du traitement), il est sujet aux erreurs et difficile à déboguer. Il n'est généralement pas recommandé d'utiliser cette méthode dans les applications pratiques, et le nombre d'itérations ne doit pas dépasser 3 fois
Mise en œuvre du programme 2 - temps pour l'espace<🎜 ; >

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

Cette méthode est principalement utilisée dans : Scénario d'utilisation 1 : Scénarios dans lesquels des objets ou des variables sont rarement utilisés et ne seront plus utilisés après avoir été utilisés une fois ; exigences de temps lorsque les ressources mémoire sont rares Cette méthode est souvent utilisée en conception

Mise en œuvre du programme 3 - Temps d'échange spatial

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

Cette méthode est généralement utilisée : l'objet ou la variable existe ou est appelé fréquemment pendant tout le cycle de vie du programme, tels que l'appel d'une interface WebService externe, une couche de persistance abstraite, le chargement de paramètres communs du fichier de configuration, etc.

Cas de test :

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

Résultat de sortie :

Type1=1836311903  
Type2=1836311903  
Type3=1836311903

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

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