자바에서 피보나치 수열을 구현하는 3가지 방법-java지도 시간-php.cn

이 글을 쓴 이유를 먼저 말씀드리자면 이 글은 전적으로 알리바바 인터뷰에서 발생한 끔찍한 살인 사건 때문이었습니다. 면접을 보러 갔을 때 면접 전날 밤 11시에 알리바바가 지정한 면접 도시에 도착했는데, 묵을 호텔을 찾기까지 거의 1시가 되어서야 잠도 잘 못 잤습니다. 밤, 이는 바로 다음날 좋지 않은 면접 결과로 이어졌습니다. (일자리를 구하는 큰 새우들이 작은 새우들에게 비극에 대해 말해서는 안 되지만, 사전 준비가 여전히 중요합니다), 인터뷰는 1년 이상 지속되었습니다. 한 시간 정도 (인터뷰를 마치고 돌아오는데 걷다가 잠이 들 뻔해서 너무 아쉽네요!!) 인터뷰가 끝나갈 무렵 면접관님이 피보나치 수열에 대해 질문을 하셨습니다. 그 때 제 마음은 완전히 혼란스러웠습니다. .. 3개의 변수를 설정하거나 List로 초기화해야 한다는 것만 알고 있었는데, for 루프를 작성할 때 마음이 완전히 혼란스러워서 결국 작성하지 못했습니다. , 면접관의 지시에 따라 아래의 첫 번째 방법 만 작성할 수 있습니다. 이제부터 Ali는 전체 응용 프로그램을 부주의하게 설정했습니다. 그야말로 변화와 금 채굴의 황금기(능력 있는 새우는 빨리 움직여야 한다) 결국 알리바바 손에 있는 데이터의 99%는 중요한 데이터인 반면, 바이두 같은 검색 대기업에 제공되는 데이터는 99%에 불과하다. 쓰레기, 데이터 분석을 위해 Alibaba는 보유하고 있는 다양한 세부 사용자 데이터를 더 잘 분석할 수 있으며 사용자의 취향과 요구 사항을 더 정확하게 찾아 정확한 푸시와 정확한 광고 푸시를 위한 더 나은 솔루션을 제공할 수 있습니다. Tencent의 미래 꿈이 사용자의 삶에 물과 전기를 제공하는 것이라면, Alibaba의 실현 가능한 미래 꿈은 사용자에게 생필품, 음식, 주택, 교통, 물과 전기 수집 등을 제공하는 것입니다. 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 ");
  }
 }

로그인 후 복사

이 방법의 단점: 많은 반복이 지속적으로 스택 공간을 소비합니다(웹 개발, 디버깅 및 유지 관리에 종사하는 사람은 누구나 서버 스택 리소스의 가치를 알아야 합니다. 반복 호출로 인해 서버가 스택 리소스를 오랫동안 재활용하지 않아 웹 서버가 충돌함), 효율성이 낮고 기능이 상대적으로 약함(훌륭한 인터페이스는 입력 및 출력에서 발생할 수 있는 오류 메시지를 캡처하고 제공해야 함) 명확한 처리 결과), 오류가 발생하기 쉽고 디버그하기 어렵습니다. 이 방법은 일반적으로 실제 응용 프로그램에서 권장되지 않으며 반복 횟수는
프로그램 구현 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;
 }

로그인 후 복사

입니다.

이 방법은 주로 다음에서 사용됩니다: 사용 시나리오 1: 개체나 변수가 거의 사용되지 않고 한 번 사용한 후에는 다시 사용되지 않는 시나리오 사용 시나리오 2: 메모리 리소스가 부족하고 실시간인 많은 임베디드 시스템 설계 요구 사항은 그리 높지 않습니다.
프로그램 구현 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;
  }
 }

로그인 후 복사

이 방법은 일반적으로 프로그램의 수명 주기 동안 개체나 변수가 존재하는 시나리오에서 사용됩니다. 외부 웹 서비스 인터페이스 호출, 추상 지속성 레이어, 공통 구성 파일 매개변수 로딩 등 자주 호출됩니다.
테스트 케이스:

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

로그인 후 복사

출력 결과:

Type1=1836311903  
Type2=1836311903  
Type3=1836311903

로그인 후 복사

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

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