斐波那契之美

斐波那契數列（Fibonacci sequence），又稱黃金分割數列、因數學家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”。

這個數列就是1、1、2、3、5、8、13、21、34、……

在數學上，斐波那契數列以如下被以遞推的方法定義：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的應用，為此，美國數學會從1963年起出版了以《斐波納契數列季刊》為名的一份數學雜志，用于專門刊載這方面的研究成果。

但是斐波那契的知識不止于此，它還有很多驚艷到我的地方，下面我們就一起了解一下：

1. 隨著數列項數的增加，前一項與后一項之比越來越逼近黃金分割的數值0.6180339887..
2. 從第二項開始，每個奇數項的平方都比前后兩項之積多1，每個偶數項的平方都比前后兩項之積少1。（注：奇數項和偶數項是指項數的奇偶，而并不是指數列的數字本身的奇偶，比如第五項的平方比前后兩項之積多1，第四項的平方比前后兩項之積少1）
3. 斐波那契數列的第n項同時也代表了集合{1,2,…,n}中所有不包含相鄰正整數的子集個數。
4. f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
5. f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
6. f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
7. [f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
8. f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
9. f(m+n)=f(m-1)·f(n-1)+f(m)·f(n) (利用這一點，可以用程序編出時間復雜度僅為O（log n）的程序。)

真的不禁感嘆：真是一個神奇的數列啊

桶排序

我們都知道，基于比較的排序，時間的極限就是O(NlogN)，從來沒有哪個排序可以突破這個界限，如速度最快的快速排序，想法新穎的堆排序，分治的歸并排序。

但是，如果我們的排序根本就不基于比較，那就可能突破這個時間。

桶排序不是基于比較的排序方法，只需對號入座。將相應的數字放進相應編號的桶即可。

當要被排序的數組內的數值是均勻分配的時候，桶排序使用線性時間o（n）

對于海量有范圍數據十分適合，比如全國高考成績排序，公司年齡排序等等。

l=list(map(int,input().split(" ")))
n=max(l)-min(l)
p=[0]*(n+1)#為了省空間
for i in l:p[i-min(l)]=1#去重排序，做標記即可
for i in range(n):if p[i]==1:#判斷是否出現過print(i+min(l),end=" ")

當然，基數排序是桶排序的改良版，也是非常好的排序方法，具體操作是：把數字的每一位都按桶排序排一次，因為桶排序是穩定的排序，因此從個位進行桶排序，然后十位進行桶排序。。。直到最高位，排序結束。

這樣極大的弱化了桶排序范圍有限的弱點，比如范圍1-100000需要準備100000個銅，而基數排序只要10個銅就夠了（因為一共就十個數字。）。

想出這個排序的人也是個天才啊。。。選擇合適的場合使用覺得有很好的效果。

快速排序

快速排序（Quicksort）是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
分三區優化1：

在使用partition-exchange排序算法時，如快速排序算法，我們會遇到一些問題，比如重復元素太多，降低了效率，在每次遞歸中，左邊部分是空的(沒有元素比關鍵元素小)，而右邊部分只能一個一個遞減移動。結果導致耗費了二次方時間來排序相等元素。這時我們可以多分一個區，即，小于區，等于區，大于區。（傳統快排為小于區和大于區）

下面我們通過一個經典例題來練習這種思想。

荷蘭國旗問題

”荷蘭國旗難題“是計算機科學中的一個程序難題，它是由Edsger Dijkstra提出的。荷蘭國旗是由紅、白、藍三色組成的。

現在有若干個紅、白、藍三種顏色的球隨機排列成一條直線。現在我們的任務是把這些球按照紅、白、藍排序。

樣例輸入

3
BBRRWBWRRR
RRRWWRWRB
RBRW
樣例輸出

RRRRRWWBBB
RRRRRWWWB
RRWB
思路：

現在我們的思路就是把未排序時前部和后部分別排在數組的前面和后面，那么中部自然就排好了。

設置兩個標志位head指向數組開頭，tail指向數組末尾，now從頭開始遍歷：

(1)如果遍歷到的位置為1，那么它一定是屬于前部，于是就和head交換值，然后head++，now++；

(2)如果遍歷到的位置為2，說明屬于中部，now++；

(3)如果遍歷到的位置為3，說明屬于后部，于是就和tail交換值，然而，如果此時交換后now指向的值屬于前部，那么就執行(1)，tail--；

廢話不多說，上代碼。

#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 100 + 5;int n;
string str;
int main(){cin>>n;while(n--){cin>>str;int len=str.size();int now=0,ans=0;int head=0,tail=len-1;while(now<=tail){if(str[now]=='R'){swap(str[head],str[now]);head++;now++;}else if(str[now]=='W'){now++;}else{swap(str[now],str[tail]);tail--;}}cout<<str<<endl;}return 0;
}

快排分三區以后降低了遞歸規模，避免了最差情況，性能得到改進。
但是還是存在退化情況：

隨機化快排優化2：
快速排序的最壞情況基于每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。比如1 2 3 4 5，每次取第一個元素，就退化為了O(N^2)。一種比較常見的優化方法是隨機化算法，即隨機選取一個元素作為主元。

這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴于輸入數據，而是由于隨機函數取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對于絕大多數輸入數據達到O(nlogn)的期望時間復雜度。
?

def gg(a,b):global lif a>=b:#注意停止條件，我以前沒加>卡了半小時returnx,y=a,bimport random#為了避免遇到基本有序序列退化，隨機選點g=random.randint(a,b)l[g],l[y]=l[y],l[g]#交換選中元素和末尾元素while a<b:if l[a]>l[y]:#比目標元素大l[a],l[b-1]=l[b-1],l[a]#交換b=b-1#大于區擴大#注意：換過以后a不要加，因為新換過來的元素并沒有判斷過else:a=a+1#小于區擴大l[y],l[a]=l[a],l[y]#這時a=b#現在解釋a和b：a的意義是小于區下一個元素#b是大于區的第一個元素gg(x,a-1)#左右分別遞歸gg(a+1,y)l=list(map(int,input().split(" ")))
gg(0,len(l)-1)
print(l)

BFPRT

我們以前寫過快排的改進求前k大或前k小，但是快排不可避免地存在退化問題，即使我們用了隨機數等優化，最差情況不可避免的退化到了O(N^2），而BFPRT就解決了這個問題，主要的思想精華就是怎么選取劃分值。

我們知道，經典快排是選第一個數進行劃分。而改進快排是隨機選取一個數進行劃分，從概率上避免了基本有序情況的退化。而BFPRT算法選劃分值的規則比較特殊，保證了遞歸最小的縮減規模也會比較大，而不是每次縮小一個數。

這個劃分值如何劃分就是重點。

如何讓選取的點無論如何都不會太差。

1、將n個元素劃分為n/5個組，每組5個元素
2、對每組排序，找到n/5個組中每一組的中位數；?
3、對于找到的所有中位數，調用BFPRT算法求出它們的中位數，作為劃分值。

下面說明為什么這樣找劃分值。

我們先把數每五個分為一組。

同一列為一組。

排序之后，第三行就是各組的中位數。

我們把第三行的數構成一個數列，遞歸找，找到中位數。

這個黑色框為什么找的很好。

因為他一定比A3、B3大，而A3、B3、C3又在自己的組內比兩個數要大。

我們看最差情況：求算其它的數都比c3大，我們也能在25個數中縮小九個數的規模。大約3/10.

我們就做到了最差情況固定遞減規模，而不是可能縮小的很少。

下面代碼實現：

public class BFPRT {
//前k小public static int[] getMinKNumsByBFPRT(int[] arr, int k) {if (k < 1 || k > arr.length) {return arr;}int minKth = getMinKthByBFPRT(arr, k);int[] res = new int[k];int index = 0;for (int i = 0; i != arr.length; i++) {if (arr[i] < minKth) {res[index++] = arr[i];}}for (; index != res.length; index++) {res[index] = minKth;}return res;}
//第k小public static int getMinKthByBFPRT(int[] arr, int K) {int[] copyArr = copyArray(arr);return select(copyArr, 0, copyArr.length - 1, K - 1);}public static int[] copyArray(int[] arr) {int[] res = new int[arr.length];for (int i = 0; i != res.length; i++) {res[i] = arr[i];}return res;}
//給定一個數組和范圍，求第i小的數public static int select(int[] arr, int begin, int end, int i) {if (begin == end) {return arr[begin];}int pivot = medianOfMedians(arr, begin, end);//劃分值int[] pivotRange = partition(arr, begin, end, pivot);if (i >= pivotRange[0] && i <= pivotRange[1]) {return arr[i];} else if (i < pivotRange[0]) {return select(arr, begin, pivotRange[0] - 1, i);} else {return select(arr, pivotRange[1] + 1, end, i);}}
//在begin end范圍內進行操作public static int medianOfMedians(int[] arr, int begin, int end) {int num = end - begin + 1;int offset = num % 5 == 0 ? 0 : 1;//最后一組的情況int[] mArr = new int[num / 5 + offset];//中位數組成的數組for (int i = 0; i < mArr.length; i++) {int beginI = begin + i * 5;int endI = beginI + 4;mArr[i] = getMedian(arr, beginI, Math.min(end, endI));}return select(mArr, 0, mArr.length - 1, mArr.length / 2);//只不過i等于長度一半，用來求中位數}
//經典partition過程public static int[] partition(int[] arr, int begin, int end, int pivotValue) {int small = begin - 1;int cur = begin;int big = end + 1;while (cur != big) {if (arr[cur] < pivotValue) {swap(arr, ++small, cur++);} else if (arr[cur] > pivotValue) {swap(arr, cur, --big);} else {cur++;}}int[] range = new int[2];range[0] = small + 1;range[1] = big - 1;return range;}
//五個數排序，返回中位數public static int getMedian(int[] arr, int begin, int end) {insertionSort(arr, begin, end);int sum = end + begin;int mid = (sum / 2) + (sum % 2);return arr[mid];}
//手寫排序public static void insertionSort(int[] arr, int begin, int end) {for (int i = begin + 1; i != end + 1; i++) {for (int j = i; j != begin; j--) {if (arr[j - 1] > arr[j]) {swap(arr, j - 1, j);} else {break;}}}}
//交換值public static void swap(int[] arr, int index1, int index2) {int tmp = arr[index1];arr[index1] = arr[index2];arr[index2] = tmp;}
//打印public static void printArray(int[] arr) {for (int i = 0; i != arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int[] arr = { 6, 9, 1, 3, 1, 2, 2, 5, 6, 1, 3, 5, 9, 7, 2, 5, 6, 1, 9 };// sorted : { 1, 1, 1, 1, 2, 2, 2, 3, 3, 5, 5, 5, 6, 6, 6, 7, 9, 9, 9 }printArray(getMinKNumsByBFPRT(arr, 10));}
}

這個辦法解決了最差的退化情況，在一大堆數中求其前k大或前k小的問題，簡稱TOP-K問題。目前解決TOP-K問題最有效的算法即是BFPRT算法，其又稱為中位數的中位數算法，該算法由Blum、Floyd、Pratt、Rivest、Tarjan提出?，讓我們永遠記住這群偉大的人。