常用的基础算法

1、第一章 高精度计算 利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍常用的几种高精度计算的方法。 高精度计算中需要处理好以下几个问题：(1)数据的接收方法和存贮方法 数据的接收和存贮：当输入的数很长时，可采用字符串方式输入，这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。另一种方法是直接用循环加数组方法输入数据。void init(int a) /传入一个数组 strin

2、g 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+语言中任何数据类型都有一定的表示范

3、围。而当两个被加数很大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。 这样，我们方便写出两个整数相加的算法。 8 5 6 + 2 5 5 1 1 1 1 图1 A3 A2 A1+ B3 B2 B1 C4 C3 C2 C1 图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都为数组，分别存储被加数、

4、加数、结果 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#includeusing 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,sizeo

5、f(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】高精度减法。输入两个正整数，求它们的差。【算法

6、分析】 类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。高精度减法的参考程序：#include#include#includeusing 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 subtrahen

7、d:); 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=

8、0;i=lenb-1;i+) blenb-i=int(n2i-0); /减数放入b数组 i=1;while (i=lena|i=lenb)if (ai1) lenc-; /最高位的0不输出 for (i=lenc;i=1;i-) coutci; /输出结果coutendl;return 0;【例3】高精度乘法。输入两个正整数，求它们的积。【算法分析】 类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加，如图3、图4。分析c数组下标的变化规律，可以写出如下关系式：ci = ci +c”i +由此可见，c i跟ai*bj乘积有关，跟上次的进位有关

9、，还跟原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 图3A 3 A 2 A 1 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1 图4高精度乘法的参考程序：#include#include#includeusing namespace std;int main() char a1100,b1100; int a100,b100,c100,lena,lenb,lenc,i

10、,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) /删除前导0lenc-;for (i=lenc;i=1;i-)coutci;coutendl;return

11、0;【例4】高精度除法。输入两个正整数，求它们的商（做整除）。【算法分析】 做除法时，每一次上商的值都在，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度除法，用09次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。#include#include#includeusing namespace std;int main()char a1100; int a100,c100,lena,i,x=0,lenc,b; memset(a,0,size

12、of(a); memset(c,0,sizeof(c); gets(a1); cinb; 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; 实质上，在做两个高精度数运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位

13、数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图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第二章 数据排序 信息获取后通常需要进行处理，处理后的信息其目的是便于人们的应用。信息处理方法有多种，通常有数据

14、的排序，查找，插入，删除，归并等操作。读者已经接触了一些这方面的知识，本章重点介绍数据排序的几种方法。1. 选择排序（1） 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在待排序的数列的最前，直到全部待排序的数据元素排完。（2）排序过程：【示例】：初 始 关键字 49 38 65 97 76 13 27 49第一趟排序后 1338 65 97 76 49 27 49第二趟排序后 13 2765 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 76 97 65 49第五趟排序后 13 27 3

15、8 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数组中。 在a1an中选择值最小的元素，与第1位置元素交换，则把最小值元素放入a1中。 在a2an中选择值最小的元素，与第2位置元素交换，则把

16、最小值元素放入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; cinn; for (i=0;iai; /输入n个数 for (i=0;in;i+) /i控制当前序列中最小值存放的数据位置 k=i; for (j=i+1;jn;j+) /在当前无序区ai.n中选最小

17、的元素ak if (ajak) k=j; if (k!=i) /交换ai和ak，将当前最小值放到ai位置 temp=ai;ai=ak;ak=temp; for (i=0;in;i+) coutai ; return 0; 2.冒泡排序 冒泡排序的思想：以n个人站队为例，从第1个开始，依次比较相邻的两个是否逆序对(高在前，矮在后)，若逆序就交换这两人，即第1个和第2个比，若逆序就交换两人，接着第2个和第3个比，若逆序就交换两人，接着第3个和第4个比，若逆序就交换两人，直到n-1和n比较，经过一轮比较后，则把最高的人排到最后，即将最高的人像冒泡一样逐步冒到相应的位置。原n个人的排序问题，转换为n-

18、1个人的排序问题。第二轮从第1个开始，依次比较相邻的两个人是否逆序对，若逆序就交换两人，直到n-2和n-1比较。如此，进行n-1轮后，队列为有序的队列。 从上述分析中可以看出，每进行一轮的比较之后，n个数的排序规模就转化为n-1个数的排序规模。 例如有6个元素需要排序： 6 5 3 4 1 2第一趟排序：第二趟排序：第三趟排序：第四趟排序：第五趟排序： 五趟结束后，6个整数就已经排序完成。排序过程中，大数慢慢的往后，相当于气泡上升，所以叫冒泡排序。 归纳上述排序过程，具体实现步骤如下： 读入数据存放在a数组中。 比较相邻的前后两个数据，如果前面数据大于后面的数据，就将两个数据交换。 对数组的第

19、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

20、-1; i=1; i-) /进行n-1轮冒泡 for(j=0; jaj+1) /相邻两个元素比较，若逆序就交换 swap(aj, aj+1); /交换 for (i=0;in;i+) /输出排序结果 coutai=1; i-) ok=true; /判断是否有交换 for(int j=1; jaj+1) swap(aj,aj+1); ok=false; if(ok=true) break; /没有交换就退出例2.2 车厢重组【问题描述】 在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置

21、交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入文件】 输入文件有两行数据，第一行是车厢总数N（不大于10000），第二行是N个不同的数表示初始的车厢顺序。【输出文件】 一个数据，是最少的旋转次数。【输入样例】 4 4 3 2 1 【输出样例】 6程序如下：#include#includeusing namespace std;long n,i,j,t,s,a10000;int main() cinn; for (i=1;

22、 iai; /输入n个车厢号 for (i=1; i=n-1; i+) /冒泡排序另一种写法 for (j=1; jaj+1) /判断车厢号是否逆序 swap(aj,aj+1); s+; /统计车厢旋转的次数 ; couts; /最少的旋转次数 return 0; 3. 插入排序 插入排序思想：回忆一下打牌时抓牌的情景，为了方便打牌，抓牌时一般一边抓牌一边按花色和大小插入恰当的位置，当抓完所有的牌时，手中的牌便是有序的，这排序方法即插入排序。 当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将将它后面的所有元素后移一

23、位，以保证插入位置的原元素不被覆盖。 例如:设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程序如下

24、：#includeusing 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. 桶排序 桶排序的思想是若待排序的值在一个明显有限范围内(整型)时，可设计有限个有序桶，待排序的值装入对

25、应的桶（当然也可以装入若干个值），桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。例：输入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)【问题描述】

26、 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入文件】 输入文件random.in 有2行， 第1行为1个正整数，表示所生成的随机数的个数：N 第2行有N个用空格隔开的正整数，为所产生的随机数。【输出文件】 输出文件random.out 也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从

27、小到大排好序的不相同的随机数。【输入样例】 10 20 40 32 67 40 20 89 300 400 15【输出样例】 8 15 20 32 40 67 89 300 400【分析】 本题有一个重要的特点就是每一个数都介于0到1000之间的整数,可以开设一个下标为01000的数组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,si

28、zeof(b); /初始化 cinn; for (i=1;ix; if (bx=0) m+; /bx为0表示x为新的随机数,m加1 bx+; /将等于x的值全部装入第x桶中 coutmendl; /不相同的随机数的个数 for (i=0;i0) couti ; coutj为止。 快速排序的时间的复杂性是O(nlog2n)，速度快,但它是不稳定的排序方法。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法 由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深

29、度为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 (aimid) 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.归并排序 归并排序是

30、建立在归并操作上的一种有效的排序算法,该算法是采用分治法（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中

31、从下标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 r

32、k=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个。 所谓逆序对的问题，即对给定的数组序列，求其逆序对的数量。 从逆序对定义上分析，逆序对就是数列中任意两个数满足大的在前，小的在后的组合。如果将这些逆序对都调整成顺序（

33、小的在前，大的在后），那么整个数列就变的有序，即排序。因而，容易想到冒泡排序的机制正好是利用消除逆序来实现排序的，也就是说，交换相邻两个逆序数，最终实现整个序列有序，那么交换的次数即为逆序对的数量。 冒泡排序可以解决逆序对问题，但是由于冒泡排序本身效率不高，时间复杂度为O(n2)，对于n比较大的情况就没用武之地了。我们可以这样认为，冒泡排序求逆序对效率之所以低，是因为其在统计逆序对数量的时候是一对一对统计的，而对于范围为n的序列，逆序对数量最大可以是(n+1)*n/2，因此其效率太低。那怎样可以一下子统计多个，而不是一个一个累加呢？这个时候，归并排序就可以帮我们来解决这个问题。 在合并操作中，

34、我们假设左右两个区间元素为: 左边：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对。这样统计的效率就会大大提高，便可较好的解决逆序对问题。 而在算法的实现中，我们只需略微修改原有归并排序，当右边序列的元素为较小值时，就统计其产生的逆

35、序对数量，即可完成逆序对的统计。【程序实现】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+;

36、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)；快速排序、堆排

37、序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为O(n); 若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。 由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。3.辅助空间的比较 桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(log2n)，最坏情况为

38、O(n)，其它排序的辅助空间为O(1);4.其它比较 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。 若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快

39、速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。第三章 递推算法 递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法

40、避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。【例1】数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。 1、 一步可沿左斜线向下或右斜线向下走； 2、 三角形行数小于等于100； 3、 三角形中的数字为0，1，99； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：573 88 1 02 7 4 44 5 2 6 5【算法分析】此题解法有多种，从递推的思想出发，设想，当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择一

41、定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设aij存放从i,j 出发到达n层的最大值，则aij=maxaij+ai+1j，aij+ai+1j+1，a11 即为所求的数字总和的最大值。【参考程序】#includeusing namespace std;int main() int n,i,j,a101101; cinn; for (i=1;i=n;i+) for (j=1;jaij; /输入数字三角形的值 for (i=n-1;i=1;i-) for (j=1;j=ai+1j+1) aij+=ai+1j; /路径选择 else aij+=ai+1j+1; cout

42、a11=3）。即：f1=1 （n=1） f2=1 （n=2） fn=fn-1 + fn-2 （n=3）程序如下：#include#includeusing namespace std;int main() int f0=1,f1=1,f2; int n; cinn; for (int i=3; i0), 输出铺法总数。【算法分析】（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。可以用递推方法归纳出问题解的一般规律。 （2）当n=1时，只能是一种铺法，铺法总数有示为x1=1。（3）当n=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数

43、表示为x2=2； （4）当n=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。如上右图，再无其他排列方法，因此铺法总数表示为x3=3。由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。 （5）推出一般规律：对一般的n，要求xn可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为xn-1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为xn-2。从

44、第一骨牌排列方法考虑，只有这两种可能，所以有： xn=xn-1+xn-2 （n2） x1=1 x2=2 xn=xn-1+xn-2就是问题求解的递推公式。任给n都可以从中获得解答。例如n=5， x3=x2+x1=3 x4=x3+x2=5 x5=x4+x3=8 下面是输入n，输出x1xn的c+程序：#includeusing namespace std;int main() int n,i,j,a101; coutn; a1=1;a2=2; coutx1=a1endl; coutx2=a2endl; for (i=3;i=n;i+) /递推过程 ai=ai-1+ai-2; coutxi=aiend

45、l; 下面是运行程序输入 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【输出样例】 3

46、7【参考程序】#includeusing namespace std;int main() long long a101=0,b101=0,i,j,x,y,z; cinxyz; 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; coutaz+10且j0且gij= 0递推边界有4个：Fij = 0 /gij = 1Fi0 = Fi-10 /i 0且gi0 = 0F0j = F0j-1 /j 0且g0j = 0F00 = 1 考虑到最大情况下：n=20,m=2

47、0，路径条数可能会超过231-1,所以要用高精度。五种典型的递推关系.Fibonacci数列 在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。 问题的提出：有

48、雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则： Fx=Nx+ Fx-1Nx=Fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力了) Fx=Fx-1+Fx-2 边界条件：F0=0，F1=1由上面的递推关系可依次得到F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，。Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到

49、了较好的体现。.Hanoi塔问题 问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图3-11所示。 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱

50、上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动hn-1+1+hn-1个盘次。 hn=2hn-1+1 边界条件：h1=1.平面分割问题 问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。解：设an为n条封闭曲线把平面分割成的区域个数。 由图3-13可以看出：a2-a1=2；a3-a2=4；a4-a3=6。 从这些式子中可以看出an-an-1=

51、2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有an-1+2(n-1)个区域。所以本题的递推关系是an=an-1+2(n-1)，边界条件是a0=1。 平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常感到棘手，下面的【例7】是另一种平

52、面分割问题，有兴趣的读者不妨自己先试着求一下其中的递推关系。.Catalan数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。 问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表示，hn即为Catalan数。例如五边形有如下五种拆分方案(图3-14)，故h5=5。求对于一个任意的凸n边形相应的hn。 Catalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是

53、，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。.第二类Stirling数 在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。【定义2】n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。 下面就让我们根据定义来推导带两个参数的递推关系第二类Stirling数。 解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以下两种： bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方案数为S2(

54、n-1,m-1)； bn与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。 综合以上两种情况，可以得出第二类Stirling数定理： 【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1) (n1,m=1) 边界条件可以由定义2推导出： S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。 第二类Stirling数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。第四章 递归算法 前面已经介绍

55、了关于递归调用这样一种操作，而递归程序设计是C+语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。 【例1】 给定n（n=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。 【算法分析】 本题可以用递归方法求解，其原因在于它符合递归的三个条件： (1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n; (2)给定n,所以是有限次的递归调用； (3)结束条件是当n=1，则s=1。 【参考程序】#

56、includeusing namespace std;int fac(int); /递归函数int main()int t;cint; /输入t的值couts=fac(t)endl; /计算1到t的累加和，输出结果int fac(int n)if (n=1) return 1;return (fac(n-1)+n); /调用下一层递归 运行程序，当T=5时，输出结果：S=15，其递归调用执行过程是：（设T=3） 递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法栈（先进后出）来管理，一旦递归调用结束，计算

57、机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。 【例2】 设有N个数已经按从大到小的顺序排列，现在输入X，判断它是否在这N个数中，如果存在则输出：“YES” 否则输出“NO”。 【算法分析】 该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法： （1） 设有N个数，存放在A数组中，待查找数为X，用L指向数据的高端，用R指向数据的低端，MID指向中间： （2） 若X=AMID 输出 “YES”； （3）若XAMID则到数据前半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找

58、； （5）若LR都没有查找到，则输出“NO”。 该算法符合递归程序设计的基本规律，可以用递归方法设计。 【参考程序】 #include#includeusing namespace std;int a11;void search(int,int,int);int main() /主程序int k,x,L=1,R=10;cout输入10个从大到小顺序的数：endl;for (k=1;kak;cinx;search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找递归过程 int mid; if (top=bot) mi

59、d=(top+bot)/2; /求中间数的位置 if (x=amid) cout“YES”endl; /找到就输出 else if (xamid) search(x,mid+1,bot); /判断在前半段还是后半段查找 else search(x,top,mid-1); else coutNOC; (2)当N=2时，则需要移动三次： A-1 - B, A -2 - C, B -1- C. (3)如果N=3，则具体移动步骤为： 假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）： 所以可按“N=2”的移动步骤设计： 如果N=0，则退出，即结束程序;否则继续往下

60、执行; 用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1, a,b,c); 将A柱上剩下的一片直接移到C柱上; 用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程mov (n-1,b,c,a)。【参考程序】 #includeusing namespace std;int k=0,n;void mov(int n,char a,char c,char b) /用b柱作为协助过渡，将a柱上的（n）移到c柱上if (n=0) return; /如果n=0，则退出，即结束程序mov(n-1,a,b,c ); /用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上k