常用的基础算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 高精度计算,利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。,高精度计算中需要处理好以下几个问题：,(1)数据的接收方法和存贮方法,数据的接收和存贮：当输入的数很长时，可采用字符串方式输入，这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。另一种方法是直接用循环加数组方法输入数据。,void init(int a)/传入一个数组,string s;,cins;/读入字符串s,len,=s.length();/用,len,计算字符串s的位数,for(i=1;i=10)ci%=10;+ci+1;,减法借位：if(aibi)-ai+1;ai+=10;,ci=ai-bi;,乘法进位：ci+j-1=ai*bj+x+ci+j-1;,x=ci+j-1/10;,ci+j-1%=10;,(4)商和余数的求法,商和余数处理：视被除数和除数的位数情况进行处理.,【例1】高精度加法。输入两个正整数，求它们的和。,【分析】,输入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在C+语言中任何数据类型都有一定的表示范围。而当两个被加数很大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。这样，我们方便写出两个整数相加的算法。,8 5 6,+2 5 5,1 1 1 1,图,1,A,3,A,2,A,1,+B,3,B,2,B,1,C,4,C,3,C,2,C,1,图,2,如果我们用数组,A,、,B,分别存储加数和被加数，用数组,C,存储结果。则上例有,A1=6,，,A2=5,，,A3=8,，,B1=5,，,B2=5,，,B3=2,，,C4=1,，,C3=1,，,C2=1,，,C1=1,，两数相加如图,2,所示。,因此，算法描述如下：,int c100;,void add(int a,int b)/a,b,c都为数组，分别存储被加数、加数、结果,int i=1,x=0;/x是进位,while(i=a数组长度)|(i=b数组的长度),ci=ai+bi+x;/第i位相加并加上次的进位,x=ci/10;/向高位进位,ci%=10;/存储第i位的值,i+;/位置下标变量,通常，读入的两个整数用可用字符串来存储，,程序设计如下：,#include,#include,#include,using namespace std;,int main(),char a1101,b1101;,int,a101,b101,c10001,lena,lenb,lenc,i,j,x;,memset(a,0,sizeof(a);,memset(b,0,sizeof(b);,memset(c,0,sizeof(c);,scanf(%s,a1);/gets,改成,scanf,scanf(%s,b1);,lena=strlen(a1);,lenb=strlen(b1);,for(i=0;i=lena-1;i+)alena-i=a1i-48;/加数放入a数组,for(i=0;i=lenb-1;i+)blenb-i=b1i-48;/加数放入b数组,lenc=1;,x=0;,while(lenc=lena|lenc=1;i-),coutci;/输出结果,coutendl;,return 0;,【例2】高精度减法。输入两个正整数，求它们的差。,【算法分析】,类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。高精度减法的参考程序：#include,#include,#include,using namespace std;,int main(),int a256,b256,c256,lena,lenb,lenc,i;,char n256,n1256,n2256;,memset(a,0,sizeof(a);,memset(b,0,sizeof(b);,memset(c,0,sizeof(c);,printf(Input minuend:);gets(n1);/输入被减数,printf(Input subtrahend:);gets(n2);/输入减数,if(strlen(n1)strlen(n2)|(strlen(n1)=strlen(n2)&strcmp(n1,n2)n2时，返回正整数；n1n2时，返回负整数,/处理被减数和减数，交换被减数和减数,strcpy(n,n1);,/,将n1数组的值完全赋值给n数组,strcpy(n1,n2);,strcpy(n2,n);,cout-;/交换了减数和被减数，结果为负数,lena=strlen(n1);lenb=strlen(n2);,for(i=0;i=lena-1;i+)alena-i=int(n1i-0);/被减数放入a数组,for(i=0;i=lenb-1;i+)blenb-i=int(n2i-0);/减数放入b数组,i=1;,while(i=lena|i=lenb),if(ai=1;i-)coutci;/输出结果,coutendl;,return 0;,【,例,3】,高精度乘法。输入两个正整数，求它们的积,。,【,算法分析,】,类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加，如图,3,、图,4,。,分析,c,数组下标的变化规律，可以写出如下关系式：,c,i,=c,i,+c”,i,+,由此可见，,c,i,跟,ai*bj,乘积有关，跟上次的进位有关，还跟原,c,i,的值有关，分析下标规律，有,ci+j-1=ai*bj+x+ci+j-1;x=ci+j-1/10;ci+j-1%=10;,8 5 6,2 5,4 2 8 0,1 7 1 2,2 1 4 0 0,图,3,A,3,A,2,A,1,B,2,B,1,C,4,C,3,C,2,C,1,C,”,5,C,”,4,C,”,3,C,”,2,C,6,C,5,C,4,C,3,C,2,C,1,图4,高精度乘法的参考程序：,#include,#include,#include,using namespace std;,int main(),char a1100,b1100;,int a100,b100,c100,lena,lenb,lenc,i,j,x;,memset(a,0,sizeof(a);,memset(b,0,sizeof(b);,memset(c,0,sizeof(c);,gets(a1);gets(b1);,lena=strlen(a1);lenb=strlen(b1);,for(i=0;i=lena-1;i+)alena-i=a1i-48;,for(i=0;i=lenb-1;i+)blenb-i=b1i-48;,for(i=1;i=lena;i+),x=0;/用于存放进位,for(j=1;j1)/删除前导0,lenc-;,for(i=lenc;i=1;i-),coutci;,coutb;,lena=strlen(a1);,for(i=0;i=lena-1;i+),ai+1=a1i-48;,for(i=1;i=lena;i+)/按位相除,ci=(x*10+ai)/b;,x=(x*10+ai)%b;,lenc=1;,while(clenc=0&lenclena),lenc+;/删除前导0,for(i=lenc;i=lena;i+),coutci;,coutendl;,return 0;,实质上，在做两个高精度数运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图,5,就是采用,4,位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。,示例：123456789 45=1 2345 6789 45,=274 3484,1/45=0 ，1%45=1,取12345/45=274 12345%45=15,取156789/45=3484,答案为2743484,余数为156789%45=9,图5,第二章 数据排序,信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。,1.,选择排序,（,1,）基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（,2,）排序过程：,【,示例,】,：,初 始 关键字,49 38 65 97 76 13 27 49,第一趟排序后,13,38 65 97 76 49 27 49,第二趟排序后,13 27,65 97 76 49 38 49,第三趟排序后,13 27 38 97 76 49 65 49,第四趟排序后,13 27 38 49 76 97 65 49,第五趟排序后,13 27 38 49,49,97 65 76,第六趟排序后,13 27 38 49,49,65 97 76,第七趟排序后,13 27 38 49,49,65 76 97,最后排序结果,13 27 38 49,49,65 76 97,例,2.1,输入,n,个数，将,n,个数按从小到大的顺序输出,(n=10000),。,输入样例,:,8,49 38 65 97 76 13 27 49,输出样例,:,13 27 38 49,49,65 76 97,归纳上述排序过程，具体实现步骤如下：,读入数据存放在,a,数组中。,在,a1,an,中选择值最小的元素，与第,1,位置元素交换，则把最小值元素放入,a1,中。,在,a2,an,中选择值最小的元素，与第,2,位置元素交换，则把最小值元素放入,a2,中，,直到第,n-1,个元素与第,n,个元素比较排序为止。,程序实现方法：用两层循环完成算法，外层循环,i,控制当前序列最小值存放的数组位置，内层循环,j,控制从,i+1,到,n,序列中选择最小的元素所在位置,k,。,程序如下：,#includeusing namespace std;const,int,MAXN=10001;,int,main(),int,n,k,i,j,;float,temp,aMAXN,;,cin,n;for(i=0;i,ai,;/,输入,n,个数,for(i=0;i,n;i,+)/i,控制当前序列中最小值存放的数据位置,k=i;for(j=i+1;j,n;j,+)/,在当前无序区,ai.n,中选最小的元素,ak,if(,aj,ak,)k=j;if(k!=i)/,交换,ai,和,ak,，将当前最小值放到,ai,位置,temp=,ai;ai,=,ak;ak,=temp;for(i=0;i,n;i,+),cout,ai,;return 0;,2.,冒泡排序,冒泡排序,的思想：以,n,个人站队为例，从第,1,个开始，依次比较相邻的两个是否逆序对,(,高在前，矮在后,),，若逆序就交换这两人，即第,1,个和第,2,个比，若逆序就交换两人，接着第,2,个和第,3,个比，若逆序就交换两人，接着第,3,个和第,4,个比，若逆序就交换两人，,，直到,n-1,和,n,比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原,n,个人的排序问题，转换为,n-1,个人的排序问题。第二轮从第,1,个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到,n-2,和,n-1,比较。如此，进行,n-1,轮后，队列为有序的队列。,从上述分析中可以看出，每进行一轮的比较之后，,n,个数的排序规模就转化为,n-1,个数的排序规模。,例如有,6,个元素需要排序：,6 5 3 4 1 2,第一趟排序：,第二趟排序：,第三趟排序：,第四趟排序：,第五趟排序：,五趟结束后，,6,个整数就已经排序完成。排序过程中，大数慢慢的往后，相当于气泡上升，所以叫冒泡排序。,归纳上述排序过程，具体实现步骤如下：,读入数据存放在,a,数组中。,比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。,对数组的第,0,个数据到,n-1,个数据进行一次遍历后，最大的一个数据就,“,冒,”,到数组第,n-1,个位置。,n=n-1,，如果,n,不为,0,就重复前面二步，否则排序完成。,程序实现方法：用两层循环完成算法，外层循环,i,控制每轮要进行多少次的比较，第,1,轮比较,n-1,次，第,2,轮比较,n-2,次，,，最后一轮比较,1,次。内层循环,j,控制每轮,i,次比较相邻两个元素是否逆序，若逆序就交换这两个元素。,【,程序实现,】,#includeusing namespace std;const,int,MAXN=10001;,int,main(),int,n,i,j,;float,temp,aMAXN,;,cinn;for(i=0;iai;/,输入,n,个数,for(i=n-1;i=1;i-)/,进行,n-1,轮冒泡,for(j=0;jaj+1)/,相邻两个元素比较，若逆序就交换,swap(aj,aj+1);/,交换,for(i=0;in;i+)/,输出排序结果,cout,ai,=1;i-),ok=true;/,判断是否有交换,for(int,j=1;jaj+1)swap(aj,aj+1);,ok=false;,if(ok,=true)break;/,没有交换就退出,例,2.2,车厢重组,【,问题描述,】,在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转,180,度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。,【,输入文件,】,输入文件有两行数据，第一行是车厢总数,N,（不大于,10000,），第二行是,N,个不同的数表示初始的车厢顺序。,【,输出文件,】,一个数据，是最少的旋转次数。,【,输入样例,】,4 4 3 2 1,【,输出样例,】,6,程序如下：,#include#includeusing namespace std;long n,i,j,t,s,a10000;,int,main(),cin,n;for(i=1;i,ai,;/,输入,n,个车厢号,for(i=1;i=n-1;i+)/,冒泡排序另一种写法,for(j=1;jaj+1)/,判断车厢号是否逆序,swap(aj,aj+1);s+;/,统计车厢旋转的次数,;,cout,s;/,最少的旋转次数,return 0;,3.,插入排序,插入排序,思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。,当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。,例如,:,设,n=8,，数组,a,中,8,个元素是,:36,25,48,12,65,43,20,58,，执行插入排序程序后，其数据变动情况：,第,0,步,:36 25 48 12 65 43 20 58,第,1,步,:,25,36 48 12 65 43 20 58,第,2,步,:25 36,48,12 65 43 20 58,第,3,步,:,12,25 36 48 65 43 20 58,第,4,步,:12 25 36 48,65,43 20 58,第,5,步,:12 25 36,43,48 65 20 58,第,6,步,:12,20,25 36 43 48 65 58,第,7,步,:12 20 25 36 43 48,58,65,程序如下：,#include,using namespace std;,const,int,MAXN=10001;,int,main(),int,n,i,j,k,;,float,temp,aMAXN,;,cinn;,for(i=0;iai;/,输入,n,个数,for(i=0;i=0;j-)/,在前面有序区间中为,ai,找合适的插入位置,if(ajj;k-),ak+1=ak;/,将,ai,放在正确位置上,ak+1=temp;,for(i=0;in;i+),coutai;/,输出排序的结果,return 0;,4.,桶排序,桶排序的思想是若待排序的值在一个明显有限范围内,(,整型,),时，可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。,例：输入,n,个,0,到,100,之间的整数，由小到大排序输出。,【,程序实现,】,#include,#include,using namespace std;,int,main(),int,b101,n,i,j,k;,memset(b,0,sizeof(b);/,初始化,cinn;,for(i=1;ik;,bk,+;/,将等于,k,的值全部装入第,k,桶中,for(i=0;i0)/,相同的整数，要重复输出,couti;bi-;/,输出一个整数后，个数减,1,coutendl;,例,2.3,明明的随机数,(Noip2006),【,问题描述,】,明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了,N,个,1,到,1000,之间的随机整数（,N100,），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成,“,去重,”,与,“,排序,”,的工作。,【,输入文件,】,输入文件,random.in,有,2,行，第,1,行为,1,个正整数，表示所生成的随机数的个数：,N,第,2,行有,N,个用空格隔开的正整数，为所产生的随机数。,【,输出文件,】,输出文件,random.out,也是,2,行，第,1,行为,1,个正整数,M,，表示不相同的随机数的个数。第,2,行为,M,个用空格隔开的正整数，为从小到大排好序的不相同的随机数。,【,输入样例,】,10 20 40 32 67 40 20 89 300 400 15,【,输出样例,】,8 15 20 32 40 67 89 300 400,【,分析,】,本题有一个重要的特点就是每一个数都介于,0,到,1000,之间的整数,可以开设一个下标为,0,1000,的数组,b,，,b0,记录值为,0,的个数,b1,记录值为,1,的个数，,，,bx,记录值为,x,的个数，那么从小到大的顺序输出,b,数组值不为,0,的,b,数组下标值。,程序如下：,#include#include#includeusing namespace std;,int,main(),int,b1001,n,i,j,m=0,x;memset(b,0,sizeof(b);/,初始化,cinn;for(i=1;ix;if(bx=0)m+;/bx,为,0,表示,x,为新的随机数,m,加,1 bx+;/,将等于,x,的值全部装入第,x,桶中,coutmendl;/,不相同的随机数的个数,for(i=0;i0),cout,i;,cout,j,为止。,快速排序的时间的复杂性是,O(nlog2n),，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法,由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为,log(n+1),。,快速排序算法,void,qsort(int,l,int,r),int,i,j,mid,p,;,i=l;j=r;,mid=,a(l+r,)/2;/,将当前序列在中间位置的数定义为分隔数,do,while(,ai,mid)j-;/,在右半部分寻找比中间数小的数,if(i=j),/,若找到一组与排序目标不一致的数对则交换它们,p=,ai,;,ai,=,aj,;,aj,=p;,i+;j-;/,继续找,while(i=j);/,注意这里不能少了等号,if(lj),qsort(l,j,);/,若未到两个数的边界，则递归搜索左右区间,if(ir),qsort(i,r,);,6.,归并排序,归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（,Divide and Conquer,）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。,例如有,8,个数据需要排序：,10 4 6 3 8 2 5 7,归并排序主要分两大步：分解、合并。,合并过程为：比较,ai,和,aj,的大小，若,aiaj,，则将第一个有序表中的元素,ai,复制到,rk,中，并令,i,和,k,分别加上,1,；否则将第二个有序表中的元素,aj,复制到,rk,中，并令,j,和,k,分别加上,1,，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到,r,中从下标,k,到下标,t,的单元。归并排序的算法我们通常用递归实现，先把待排序区间,s,t,以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间,s,t,。,【,程序实现,】,void,msort(int,s,int,t),if(s,=t)return;,/,如果只有一个数字则返回，无须排序,int,mid=(s+t)/2;,msort(s,mid,);/,分解左序列,msort(mid+1,t);/,分解右序列,int,i=s,j=mid+1,k=s;/,接下来合并,while(i,=mid&j=t),if(ai,=,aj,),rk,=,ai,;k+;i+;,else,rk,=,aj,;k+;j+;,while(i,=mid)/,复制左边子序列剩余,rk,=,ai,;k+;i+;,while(j,=t)/,复制右边子序列剩余,rk,=,aj,;k+;j+;,for(int,i=s;i1),，其中所有数字各不相同。如果存在正整数,i,j,使得,1 i,Aj,，则,这个有序对称为,A,的一个逆序对，也称作逆序数。,例如，数组（,3,，,1,，,4,，,5,，,2,）的逆序对有,(3,1),(3,2),(4,2),(5,2),，共,4,个。,所谓逆序对的问题，即对给定的数组序列，求其逆序对的数量。,从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前，小的在后的组合。如果将这些逆序对都调整成顺序（小的在前，大的在后），那么整个数列就变的有序，即排序。因而，容易想到,冒泡排序,的机制正好是利用消除逆序来实现排序的，也就是说，交换,相邻,两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。,冒泡排序可以解决逆序对问题，但是由于冒泡排序本身效率不高，时间复杂度为,O(n2),，对于,n,比较大的情况就没用武之地了。我们可以这样认为，冒泡排序求逆序对效率之所以低，是因为其在统计逆序对数量的时候是一对一对统计的，而对于范围为,n,的序列，逆序对数量最大可以是,(n+1)*n/2,，因此其效率太低。那怎样可以一下子统计多个，而不是一个一个累加呢？这个时候，归并排序就可以帮我们来解决这个问题。,在合并操作中，我们假设左右两个区间元素为,:,左边：,3 4 7 9,右边：,1 5 8 10,那么合并操作的第一步就是比较,3,和,1,，然后将,1,取出来，放到辅助数组中，这个时候我们发现，右边的区间如果是当前比较的较小值，那么其会与左边剩余的数字产生逆序关系，也就是说,1,和,3,、,4,、,7,、,9,都产生了逆序关系，我们可以一下子统计出有,4,对逆序对。接下来,3,，,4,取下来放到辅助数组后，,5,与左边剩下的,7,、,9,产生了逆序关系，我们可以统计出,2,对。依此类推，,8,与,9,产生,1,对，那么总共有,4+2+1,对。这样统计的效率就会大大提高，便可较好的解决逆序对问题。,而在算法的实现中，我们只需略微修改原有归并排序，当右边序列的元素为较小值时，就统计其产生的逆序对数量，即可完成逆序对的统计。,【,程序实现,】,void,msort(int,s,int,t),if(s,=t)return;/,如果只有一个数字则返回，无须排序,int,mid=(s+t)/2;,msort(s,mid,);/,分解左序列,msort(mid+1,t);/,分解右序列,int,i=s,j=mid+1,k=s;/,接下来合并,while(i,=mid&j=t),if(ai,=,aj,),rk,=,ai,;k+;i+;,else,rk,=,aj,;k+;j+;,ans,+=mid-i+1;/,统计产生逆序对的数量,while(i,=mid)/,复制左边子序列剩余,rk,=,ai,;k+;i+;,while(j,=t)/,复制右边子序列剩余,rk,=,aj,;k+;j+;,for(int,i=s;i=t;i+),ai,=,ri,;,return 0;,其中,ans,+=mid-i+1,这句代码统计新增逆序对的数量，,ans,作为全局变量，用于统计逆序对的数量，此时,ans,要增加左边区间剩余元素的个数。当归并排序结束后，逆序对问题也得到解决，,ans,即为逆序对的数量。,8.,各种排序算法的比较,1.,稳定性比较,插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。,选择排序、希尔排序、快速排序、堆排序是不稳定的。,2.,时间复杂性比较,插入排序、冒泡排序、选择排序的时间复杂性为,O(n2),；快速排序、堆排序、归并排序的时间复杂性为,O(nlog2n),；桶排序的时间复杂性为,O(n,);,若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为,O(n,),，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为,O(n2),，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。,由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。,3.,辅助空间的比较,桶排序、二路归并排序的辅助空间为,O(n,),，快速排序的辅助空间为,O(log2n),，最坏情况为,O(n,),，其它排序的辅助空间为,O(1);,4.,其它比较,插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。,当,n,较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。,若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。,当,n,较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。,当,n,较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序,快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；,堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。,第三章 递推算法,递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。,递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。,【,例,1】,数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。,1,、一步可沿左斜线向下或右斜线向下走；,2,、三角形行数小于等于,100,；,3,、三角形中的数字为,0,，,1,，,，,99,；,测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：,5,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,【,算法分析,】,此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第,i,层向第,i+1,层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设,aij,存放从,i,j,出发到达,n,层的最大值，则,aij,=maxaij+ai+1j,，,aij+ai+1j+1,，,a11,即为所求的数字总和的最大值。,【,参考程序,】,#include,using namespace std;,int,main(),int,n,i,j,a101101;,cin,n;,for(i=1;i=,n;i,+),for(j=1;j,aij,;/,输入数字三角形的值,for(i=n-1;i=1;i-),for(j=1;j=ai+1j+1),aij,+=ai+1j;/,路径选择,else,aij,+=ai+1j+1;,cout,a11=3,）。,即：,f1=1,（,n=1,）,f2=1,（,n=2,）,f,n,=f,n-1,+f,n-2,（,n=3,）,程序如下：,#include,#include,using namespace std;,int,main(),int f0=1,f1=1,f2;,int n;,cinn;,for(int i=3;i0),输出铺法总数。,【,算法分析,】,（,1,）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。,（,2,）当,n=1,时，只能是一种铺法，铺法总数有示为,x,1,=1,。,（,3,）当,n=2,时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为,x,2,=2,；,（,4,）当,n=3,时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为,x3=3,。,由此可以看出，当,n=3,时的排列骨牌的方法数是,n=1,和,n=2,排列方法数的和。,（,5,）推出一般规律：对一般的,n,，要求,xn,可以这样来考虑，若第一个骨牌是竖排列放置，剩下有,n-1,个骨牌需要排列，这时排列方法数为,x,n-1,；若第一个骨牌是横排列，整个方格至少有,2,个骨牌是横排列（,1*2,骨牌），因此剩下,n-2,个骨牌需要排列，这是骨牌排列方法数为,x,n-2,。从第一骨牌排列方法考虑，只有这两种可能，所以有：,x,n,=x,n-1,+x,n-2,（,n2,）,x,1,=1,x,2,=2,x,n,=x,n-1,+x,n-2,就是问题求解的递推公式。任给,n,都可以从中获得解答。例如,n=5,，,x,3,=x,2,+x,1,=3,x,4,=x,3,+x,2,=5,x,5,=x,4,+x,3,=8,下面是输入,n,，输出,x,1,x,n,的,c+,程序：,#include,using namespace std;,int,main(),int,n,i,j,a101;,cout,n;,a1=1;a2=2;,cout,x1=a1,endl,;,cout,x2=a2,endl,;,for(i=3;i=,n;i,+)/,递推过程,ai,=ai-1+ai-2;,cout,xi=,ai,endl,;,下面是运行程序输入,n=30,，输出的结果：,input n:30,x1=1,x2=2,x3=3,.,x29=832040,x30=1346269,问题的结果就是有名的斐波那契数。,【,例,4】,昆虫繁殖,【,问题描述,】,科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过,x,个月产,y,对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵,(,过,X,个月产卵,),，问过,Z,个月以后，共有成虫多少对？,0=X=20,1=Y=20,X=Z=50,【,输入格式,】,x,y,z,的数值,【,输出格式,】,过,Z,个月以后，共有成虫对数,【,输入样例,】,1 2 8,【,输出样例,】,37,【,参考程序,】,#include,using namespace std;,int,main(),long,long,a101=0,b101=0,i,j,x,y,z;,cin,xyz;,for(i,=1;i=,x;i+)ai,=1;bi=0;,for(i,=x+1;i=z+1;i+)/,因为要统计到第,z,个月后，所以要,for,到,z+1,bi,=y*,ai-x,;,ai,=ai-1+bi-2;,cout,az+10且j0且gij=0,递推边界有4个：,Fij=0 /gij=1,Fi0=Fi-10 /i 0且gi,0,=0,F0j=F0j-1 /j 0且g,0,j=0,F00=1,考虑到最大情况下：n=20,m=20，路径条数可能会超过2,31,-1,所以要用高精度。,五种典型的递推关系,.Fibonacci数列,在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。,Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。,问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？,解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则：,F,x,=N,x,+F,x-1,N,x,=F,x-2,(即第x-2个月的所有兔子到第x个月都有繁殖能力了),F,x,=F,x-1,+F,x-2,边界条件：F0=0，F1=1,由上面的递推关系可依次得到,F,2,=F,1,+F,0,=1，F,3,=F,2,+F,1,=2，F,4,=F,3,+F,2,=3，F,5,=F,4,+F,3,=5，。,Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到了较好的体现。,.Hanoi塔问题,问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次