网站dns解析,医疗企业vi设计公司,物流运输 有哪些网站可以做推广,WordPress链接点击次数统计斐波那契之美
斐波那契数列#xff08;Fibonacci sequence#xff09;#xff0c;又称黄金分割数列、因数学家列昂纳多斐波那契#xff08;Leonardoda Fibonacci#xff09;以兔子繁殖为例子而引入#xff0c;故又称为“兔子数列”。
这个数列就是1、1、2、3、5、8、13…斐波那契之美
斐波那契数列Fibonacci sequence又称黄金分割数列、因数学家列昂纳多·斐波那契Leonardoda Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”。
这个数列就是1、1、2、3、5、8、13、21、34、……
在数学上斐波那契数列以如下被以递推的方法定义F(1)1F(2)1, F(n)F(n-1)F(n-2)n3n∈N*在现代物理、准晶体结构、化学等领域斐波纳契数列都有直接的应用为此美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志用于专门刊载这方面的研究成果。
但是斐波那契的知识不止于此它还有很多惊艳到我的地方下面我们就一起了解一下
随着数列项数的增加前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..从第二项开始每个奇数项的平方都比前后两项之积多1每个偶数项的平方都比前后两项之积少1。注奇数项和偶数项是指项数的奇偶而并不是指数列的数字本身的奇偶比如第五项的平方比前后两项之积多1第四项的平方比前后两项之积少1斐波那契数列的第n项同时也代表了集合{1,2,…,n}中所有不包含相邻正整数的子集个数。f(0)f(1)f(2)…f(n)f(n2)-1f(1)f(3)f(5)…f(2n-1)f(2n)f(2)f(4)f(6)…f(2n) f(2n1)-1[f(0)]^2[f(1)]^2…[f(n)]^2f(n)·f(n1)f(0)-f(1)f(2)-…(-1)^n·f(n)(-1)^n·[f(n1)-f(n)]1f(mn)f(m-1)·f(n-1)f(m)·f(n) (利用这一点可以用程序编出时间复杂度仅为Olog n的程序。)
真的不禁感叹真是一个神奇的数列啊
桶排序
我们都知道基于比较的排序时间的极限就是O(NlogN)从来没有哪个排序可以突破这个界限如速度最快的快速排序想法新颖的堆排序分治的归并排序。
但是如果我们的排序根本就不基于比较那就可能突破这个时间。
桶排序不是基于比较的排序方法只需对号入座。将相应的数字放进相应编号的桶即可。
当要被排序的数组内的数值是均匀分配的时候桶排序使用线性时间on
对于海量有范围数据十分适合比如全国高考成绩排序公司年龄排序等等。
llist(map(int,input().split( )))
nmax(l)-min(l)
p[0]*(n1)#为了省空间
for i in l:p[i-min(l)]1#去重排序做标记即可
for i in range(n):if p[i]1:#判断是否出现过print(imin(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交换值然后headnow
(2)如果遍历到的位置为2说明属于中部now
(3)如果遍历到的位置为3说明属于后部于是就和tail交换值然而如果此时交换后now指向的值属于前部那么就执行(1)tail--
废话不多说上代码。
#includeiostream
#includealgorithm
using namespace std;const int maxn 100 5;int n;
string str;
int main(){cinn;while(n--){cinstr;int lenstr.size();int now0,ans0;int head0,taillen-1;while(nowtail){if(str[now]R){swap(str[head],str[now]);head;now;}else if(str[now]W){now;}else{swap(str[now],str[tail]);tail--;}}coutstrendl;}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 ab:#注意停止条件我以前没加卡了半小时returnx,ya,bimport random#为了避免遇到基本有序序列退化随机选点grandom.randint(a,b)l[g],l[y]l[y],l[g]#交换选中元素和末尾元素while ab:if l[a]l[y]:#比目标元素大l[a],l[b-1]l[b-1],l[a]#交换bb-1#大于区扩大#注意换过以后a不要加因为新换过来的元素并没有判断过else:aa1#小于区扩大l[y],l[a]l[a],l[y]#这时ab#现在解释a和ba的意义是小于区下一个元素#b是大于区的第一个元素gg(x,a-1)#左右分别递归gg(a1,y)llist(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提出 让我们永远记住这群伟大的人。
