java求斐波那契數(shù)列的第n個(gè)值
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波那契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(2)=1,F(n)=F(n - 1)+F(n - 2)（n?≥ 3，n?∈ N*）
/**
? ? * 使用遞歸方法求第n個(gè)斐波那契數(shù)列的值
? ? *
? ? * @param n 第幾個(gè)數(shù)
? ? * @return 結(jié)果
? ? */
? ? private Integer calNumberByRecursion(Integer n) {
? ? ? ? if (n == 1 || n == 2) {
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? return calNumberByRecursion(n - 1) + calNumberByRecursion(n - 2);
? ? }
分析: 代碼簡(jiǎn)單,時(shí)間復(fù)雜度O(2^n),空間復(fù)雜度O(n); 非常耗費(fèi)時(shí)間!!!
/**
? ? * 數(shù)組 - 使用窮舉方法求第n個(gè)斐波那契數(shù)列的值
? ? *
? ? * @param n 第幾個(gè)數(shù)
? ? * @return 結(jié)果
? ? */
? ? private Integer calNumberByArray(Integer n) {
? ? ? ? Integer[] array = new Integer[n];
? ? ? ? array[0] = 1;
? ? ? ? array[1] = 1;
? ? ? ? for (int i = 2; i < n; i++) {
? ? ? ? ? ? array[i] = array[i - 1] + array[i - 2];
? ? ? ? }
? ? ? ? log.info("calNumberByArray - 長(zhǎng)度為{}的斐波那契數(shù)列 : {}", n, StringUtils.join(array, ","));
? ? ? ? return array[n - 1];
? ? }
? ? /**
? ? * 集合 - 使用窮舉方法求第n個(gè)斐波那契數(shù)列的值
? ? *
? ? * @param n 第幾個(gè)數(shù)
? ? * @return 結(jié)果
? ? */
? ? private Integer calNumberByList(Integer n) {
? ? ? ? ArrayList<Integer> list = new ArrayList<>(n);
? ? ? ? list.add(1);
? ? ? ? list.add(1);
? ? ? ? for (int i = 0; i < n - 2; i++) {
? ? ? ? ? ? list.add(list.get(i) + list.get(i + 1));
? ? ? ? }
? ? ? ? log.info("calNumberByList - 長(zhǎng)度為{}的斐波那契數(shù)列 : {}", n, JSON.toJSON(list));
? ? ? ? return list.get(n - 1);
? ? }
分析: 時(shí)間復(fù)雜度:O(1),空間復(fù)雜度O(n)
