Think in Java之斐波那契數(shù)列
斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列。
指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、……這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。
在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*）在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用。
斐波那契數(shù)列的***，是意大利數(shù)學(xué)家列昂納多·斐波那契（Leonardo Fibonacci）。
與黃金分割的關(guān)系
有趣的是：這樣一個(gè)完全是自然數(shù)的數(shù)列，通項(xiàng)公式卻是用無理數(shù)來表達(dá)的。而且當(dāng)n趨向于無窮大時(shí)，后一項(xiàng)與前一項(xiàng)的比值的小數(shù)部分越來越逼近黃金分割0.618. 1÷1=1，2÷1=2，3÷2=1.5，5÷3=1.666...，8÷5=1.6，…………，89÷55=1.6181818…，…………233÷144=1.618055…75025÷46368=1.6180339889…...
越到后面，這些比值越接近黃金比。
證明：
a[n+2]=a[n+1]+a[n]。
兩邊同時(shí)除以a[n+1]得到：
a[n+2]/a[n+1]=1+a[n]/a[n+1]。
若a[n+1]/a[n]的極限存在，設(shè)其極限為x，
則lim[n->；∞](a[n+2]/a[n+1])=lim[n->；∞](a[n+1]/a[n])=x。
所以x=1+1/x。
即x²=x+1。
所以極限是黃金分割比..
如果你看到有這樣一個(gè)題目：
某人把一個(gè)8*8的方格切成四塊，拼成一個(gè)5*13的長(zhǎng)方形，故作驚訝地問你：為什么64=65？
其實(shí)就是利用了斐波那契數(shù)列的這個(gè)性質(zhì)：5、8、13正是數(shù)列中相鄰的三項(xiàng)，事實(shí)上前后兩塊的面積確實(shí)差1，只不過后面那個(gè)圖中有一條細(xì)長(zhǎng)的狹縫，一般人不容易注意到。
在楊輝三角中隱藏著斐波那契數(shù)列
斐波那契數(shù)列的整除性與素?cái)?shù)生成性
每3個(gè)數(shù)有且只有一個(gè)被2整除，
每4個(gè)數(shù)有且只有一個(gè)被3整除，
每5個(gè)數(shù)有且只有一個(gè)被5整除，
每6個(gè)數(shù)有且只有一個(gè)被8整除，
每7個(gè)數(shù)有且只有一個(gè)被13整除，
每8個(gè)數(shù)有且只有一個(gè)被21整除，
每9個(gè)數(shù)有且只有一個(gè)被34整除，
.......
我們看到第5、7、11、13、17、23位分別是素?cái)?shù)：5，13，89，233，1597，28657（第19位不是）
斐波那契數(shù)列的素?cái)?shù)無限多嗎？
斐波那契數(shù)列的個(gè)位數(shù)：一個(gè)60步的循環(huán)
11235,83145,94370,77415,61785.38190, 99875,27965,16730,33695,49325,72910…
斐波那契數(shù)列中是否存在無窮多個(gè)素?cái)?shù)？[維基百科]
在斐波那契數(shù)列中，有素?cái)?shù)：
2,3,5,13,89,233,1597,28657,514229,433494437,2971215073,99194853094755497,1066340417491710595814572169,19134702400093278081449423917……
目前已知***素?cái)?shù)是第81839個(gè)斐波那契數(shù)，一共有17103位數(shù)。
相關(guān)的數(shù)學(xué)問題
1.排列組合
有一段樓梯有10級(jí)臺(tái)階，規(guī)定每一步只能跨一級(jí)或兩級(jí)，要登上第10級(jí)臺(tái)階有幾種不同的走法?
這就是一個(gè)斐波那契數(shù)列：
登上***級(jí)臺(tái)階有一種登法；登上兩級(jí)臺(tái)階，有兩種登法；登上三級(jí)臺(tái)階，有三種登法；登上四級(jí)臺(tái)階，有五種登法……
1，2，3，5，8，13……所以，登上十級(jí)，有89種走法。
類似的，一枚均勻的硬幣擲10次，問不連續(xù)出現(xiàn)正面的可能情形有多少種？
答案是（1/√5)*{[(1+√5)/2]^（10+2） - [(1-√5)/2]^（10+2）}=144種。
2.數(shù)列中相鄰兩項(xiàng)的前項(xiàng)比后項(xiàng)的極限
當(dāng)n趨于無窮大時(shí)，F(xiàn)(n)/F(n+1）的極限是多少？
這個(gè)可由它的通項(xiàng)公式直接得到，極限是（-1+√5)/2，這個(gè)就是黃金分割的數(shù)值，也是代表大自然的和諧的一個(gè)數(shù)字。
3.求遞推數(shù)列a(1)=1，a(n+1)=1+1/a(n）的通項(xiàng)公式
由數(shù)學(xué)歸納法可以得到：a(n)=F(n+1)/F(n），將斐波那契數(shù)列的通項(xiàng)式代入，化簡(jiǎn)就得結(jié)果。
4.兔子繁殖問題（關(guān)于斐波那契數(shù)列的別名）
斐波那契數(shù)列又因數(shù)學(xué)家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”?！ ?/p>
一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來。如果所有兔都不死，那么一年以后可以繁殖多少對(duì)兔子？
我們不妨拿新出生的一對(duì)小兔子分析一下：
***個(gè)月小兔子沒有繁殖能力，所以還是一對(duì)
兩個(gè)月后，生下一對(duì)小兔民數(shù)共有兩對(duì)
三個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是三對(duì)
?。? 依次類推可以列出下表：
|
經(jīng)過月數(shù) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
幼仔對(duì)數(shù) |
1 |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
|
成兔對(duì)數(shù) |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
|
總體對(duì)數(shù) |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
233 |
幼仔對(duì)數(shù)=前月成兔對(duì)數(shù)
成兔對(duì)數(shù)=前月成兔對(duì)數(shù)+前月幼仔對(duì)數(shù)
總體對(duì)數(shù)=本月成兔對(duì)數(shù)+本月幼仔對(duì)數(shù)
可以看出幼仔對(duì)數(shù)、成兔對(duì)數(shù)、總體對(duì)數(shù)都構(gòu)成了一個(gè)數(shù)列。這個(gè)數(shù)列有關(guān)十分明顯的特點(diǎn)，那是：前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng)?！ ?/p>
這個(gè)數(shù)列是意大利中世紀(jì)數(shù)學(xué)家斐波那契在<；算盤全書>；中提出的，這個(gè)級(jí)數(shù)的通項(xiàng)公式，除了具有a(n+2)=an+a(n+1）的性質(zhì)外，還可以證明通項(xiàng)公式為：an=（1/√5）*{[(1+√5)/2]^n-[(1-√5)/2]^n}（n=1,2,3.....） `````
可惜本人是文科生，看不懂也不記得那些所謂的數(shù)學(xué)公式了，以前素材只摘選感興趣的部分。
來源于百度：http://baike.baidu.com/view/816.htm
我只感興趣的是后面這幾段代碼的實(shí)現(xiàn)：
- package com.tudou.t1;
- import java.math.BigInteger;
- import java.util.Scanner;
- /**
- * 斐波那契數(shù)列 1,2,3,5,8,13,21....[]
- *
- * @author lz
- *
- */
- public class Fibonacci {
- public static void main(String[] args) {
- fib();//常規(guī)算法
- System.out.println(compute2(5));//計(jì)算第n個(gè)斐波那契數(shù)列的數(shù)
- fibHign();// Java語言程序（高精度，約一秒鐘計(jì)算第20000個(gè)數(shù)值）
- }
- private static void fib() {
- int x = 1, y = 1;
- System.out.println(x);
- for (int i = 1; i <= 5; i++) {
- System.out.println(y);
- y = x + y;
- x = y - x;
- }
- }
- // n為第n個(gè)斐波那契數(shù)列的數(shù)
- public static BigInteger compute2(int n) {
- if (n == 1 || n == 2) {
- return BigInteger.ONE;
- }
- BigInteger num1 = BigInteger.ONE;
- BigInteger num2 = BigInteger.ONE;
- BigInteger result = BigInteger.ZERO;
- for (int i = 2; i < n; i++) {
- result = num1.add(num2);
- num2 = num1;
- num1 = result;
- }
- return result;
- }
- // Java語言程序（高精度，約一秒鐘計(jì)算第20000個(gè)數(shù)值）
- private static void fibHign() {
- Scanner s = new Scanner(System.in);
- System.out.print("請(qǐng)輸入一個(gè)整數(shù):");
- int n = s.nextInt();
- do {
- cul(n);
- n = s.nextInt();
- } while (n > 0);// 當(dāng)n<=0時(shí)終止
- }
- private static void cul(int n) {
- BigIntT b = new BigIntT();
- BigIntT a = new BigIntT();
- b.formatBigInt("1");
- a.formatBigInt("2");
- if (n == 1 || n == 2) {
- System.out.println(1);
- return;
- }
- int i = 3;
- for (; i <= n; i++) {
- if (i % 2 > 0)
- b.add(a);
- else
- a.add(b);
- }
- BigIntT t = null;
- if (i % 2 > 0)
- t = b;
- else
- t = a;
- for (int j = t.getPos(); j < 100000; j++)
- System.out.print(t.getBase(j));
- System.out.println();
- }
- }
- class BigIntT {
- int max = 100000;
- private byte[] base = new byte[max];
- private int pos = max;
- public void formatBigInt(String arr) {
- int l = arr.length();
- if (l == 0)
- return;
- int tmp = l - 1;
- for (int i = max - 1; i >= max - l; i--) {
- base[i] = (byte) (arr.charAt(tmp--) - '0');
- pos--;
- }
- }
- public void add(BigIntT right) {
- int bigger = this.getPos() > right.getPos() ? right.getPos() : this
- .getPos();
- pos = bigger;
- for (int i = max - 1; i >= pos - 2; i--) {
- int t = this.base[i] + right.getBase(i);
- if (t >= 10) {
- this.base[i] = (byte) (t % 10);
- this.base[i - 1] += t / 10;
- if (i - 1 < pos)
- pos = i - 1;
- } else {
- this.base[i] = (byte) t;
- }
- }
- }
- public int getPos() {
- return pos;
- }
- public byte getBase(int index) {
- return base[index];
- }
- }
控制臺(tái)輸出結(jié)果為：
1 1 2 3 5 8 5
請(qǐng)輸入一個(gè)整數(shù):500
139423224561697880139724382870407283950070256587697307264108962948325571622863290
691557658876222521294125
感興趣的朋友，可以玩一下。偶爾玩玩這些也很過癮呢。
原文鏈接：http://blog.csdn.net/yaerfeng/article/details/7279210
【編輯推薦】
