Javaでフィボナッチ数列を実装する3つの方法

最初にこれを書いた理由について話させてください。これは完全にアリババでのインタビューによって引き起こされた恐ろしい殺人事件が原因でした。面接に行ったとき、面接の前夜11時にアリババ指定の面接都市に到着しましたが、宿泊するホテルを探すのに1時近くかかりました。また、夜はよく眠れませんでした。 、それは翌日の悪い面接結果に直接つながりました（仕事を探している大きなエビは、小さなエビに悲劇について話すべきではありません。それでも事前に準備することが重要です。）面接は1時間以上続きました。 1時間（面接が終わって帰ったら、歩きながら眠ってしまいました、悲しかったです!!） 面接の最後に、面接官がフィボナッチ数列について質問しました。その時、私の心は完全に混乱していました。 for ループを作成するときは、3 つの変数を設定するか、List で初期化する必要があることしかわかっていませんでした。結局、それを書き出すことはできませんでした。インタビュアーの指導の下で、以下の最初のメソッドを段階的に作成することしかできませんでした。これ以降、Ali は、アプリケーション全体を不用意に使用するだけで済みました。変化と金の採掘の黄金期（有能なエビはすぐに終わるはずだ）結局のところ、アリババの手元にあるデータの99％は重要なデータであり、データの99％は主に検索を促進するバイドゥのような巨大企業に提供されている。アリババはゴミと比べて、データ分析において、保有するさまざまな詳細なユーザーデータをより正確に分析することができ、ユーザーの好みやニーズをより正確に特定し、正確なプッシュと正確な広告プッシュのためのより良いソリューションを提供できます。テンセントの将来の夢がユーザーの生活に水と電気を提供することであるなら、アリババの実現するかもしれない将来の夢は、ユーザーに基本的な必需品、食料、住居、交通手段を提供し、さらに水と電気の集金などを提供することです。O(∩_ ∩)お～本題に入りましょう。
優れたアルゴリズム設計者にとって、プログラム関数の主な実装に基づいて気にすることは 2 つだけです。1 つは設計アルゴリズムの時間計算量、もう 1 つは空間計算量です (端的に言えば、一般に、インテリジェントなアルゴリズム設計者は、さまざまなアプリケーション シナリオに基づいて、時間と空間という 2 つの相反するリソースの間のバランス ポイントを見つけます。たとえば、高いリアルタイム要件を持つシステムです。一般に、時間と引き換えに、一般的に使用されるオブジェクトはメモリ内に常駐して応答時間を短縮します (これは、メモリ リソースが比較的少ない組み込みシステムの場合、キャッシュ テクノロジと、現在普及している NoSQL のほとんどのメモリ内データベースに当てはまります)。貴重な時間は、通常、時間と引き換えに使用されます。
フィボナッチ数列の 3 つの実装と、実際のアプリケーション シナリオに真に適合する優れたアルゴリズムを真に設計する方法について話しましょう
まずフィボナッチ数列について話しましょう:
文字通りに言うと、フィボナッチ数列は 0 から開始し、 1、後続のフィボナッチ係数は前の 2 つの数値の合計です。シーケンスの形式は次のとおりです:
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;
 }

このメソッドは主に次の用途で使用されます。 使用頻度が低く、一度使用した後は再度使用されないオブジェクトまたは変数の場合。 2: この方法は、メモリ リソースが不足し、リアルタイム要件がそれほど高くない組み込みシステムの設計でよく使用されます。外部 WebService インターフェイス、抽象永続層の呼び出し、共通構成ファイル パラメーターの読み込みなど、ライフ サイクル内で存在するシナリオ、または頻繁に呼び出されるシナリオを実行するプログラム全体で使用されます。
テスト ケース:

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

出力結果:

Type1=1836311903  
Type2=1836311903  
Type3=1836311903

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

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