第5章江苏省二级C语言等级考试算法考点精解(初稿)

第5章算法考点精解前面两章讨论了C语言的基本概念、基本语句、程序结构、各种数据类型、函数、指针、链表、文件等与语法相关的内容，本章主要针对江苏省二级C等级考试中经常出现的算法进行归纳总结，包括基本操作、非数值计算常用经典算法、数值计算常用经典算法、解决各类问题的一般算法。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。形成解题思路是推理实现的算法，编写程序是操作实现的算法。在计算机的等级考试题目中，程序填空及上机编程题一般都与算法有关，所以要了解等级考试大纲中规定的算法并掌握常考算法。5.1基本操作一、知识点综述1．交换(*****)变量交换算法是一种很简单的算法，也是最为基础的一个算法，各种其他的算法往往都要运用到这一基本算法，如各种排序算法就会使用到交换变量的算法。实现变量的值的交换最常用的方法是借助一个临时变量来实现将两个数的值进行交换。下面的函数实现了两个数的交换。voidswap(intx,inty){inttemp;temp=x;x=y;y=temp;}因为函数参数的传递是值传递，是单向的，如果主函数调用了此函数，尽管形式参数x和y的值交换了，而主函数中的实际参数是不会改变的。要想实现地址传递，应该用指针实现。voidswap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}函数调用时将实参的地址传递给指针x和y，例如：swap(&a,&b);实现x和y指向的地址单元的值的交换，即a和b的值的交换。2．累加(*****)累加就是对若干个数求和，其最基本的思想就是“反复做加法”。一般来说，计算机每次只处理两个数的相加运算，所以多个数相加必须通过多次的两两相加来实现，用循环就很容易实现数的累加。使用循环时，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示最后结果的初值。用c语言实现1+2+3+4+5+……+n的累加。【方法1】for循环实现intadd(intn){inti,sum=0;for(i=1;i=n;i++)sum=sum+i;returnsum;}【方法2】while循环实现intadd(intn){inti,sum;sum=0;i=1;while(i=n){sum=sum+i;i=i+1;}returnsum;}do-while循环也可以实现累加。请读者自己完成。3．累乘(*****)累乘就是对若干个数求积，其最基本的思想就是“反复做乘法”，实际上就是求一个数的阶乘,实现方法与累加类似。在累乘之前，一定要将用于存放乘积的变量的值初始化为1。用c语言求n的阶乘：n!=1234…n(n=0)intproduct(intn){inti,p=1;for(i=2;i=n;i++)p=p*i;returnp;}如果n的值比较大，考虑累乘的结果可能会超过32767，函数返回值应定义为长整型，确保程序运行的正确。longfunc(intn){inti;longp=1;for(i=2;i=n;i++)p*=i;returnp;}5.2非数值计算常用经典算法一、知识点综述1．穷举(***)穷举法的基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解。这是一种在“没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。【例题】有1、2、3、4四个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。main(){inti,j,k;for(i=1;i5;i++)／*以下为三重循环*/for(j=1;j5;j++)for(k=1;k5;k++)if(i!=k&&i!=j&&j!=k)/*确保i、j、k三位互不相同*/printf(%d,%d,%d\n,i,j,k);}2．排序(*****)排序就是将数组中的元素按从大到小的顺序或者从小到大的顺序重新排列。排序方法有很多，C语言中最常用的排序方法有冒泡排序、选择排序、插入排序。1)冒泡排序(*****)算法思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。排序步骤如下：①将数组中相临的两个数两两比较，如果第一个数大于（小于）第二个数，两者交换位置，即将小的排前面，大的排后面。②第一趟比较，小的调到前头，经n-1次两两相邻比较，最大的数已沉底，放在最后一个位置，小的数浮起。③第二趟对余下的n-1个数比较，比较n-2次，得次大的数在最后第二个位置。④重复上述过程，n个数比较n-1趟，在第i趟中进行n-1-i次两两比较。下面的函数是按升序从前往后排。voidBubbleSort(inta[],intn){inti,j,tmp;for(i=0;in-1;i++)/*排序趟次*/{for(j=0;jn-1-i;j++)/*从前往后比*/if(a[j]a[j+1])/*从小到大*/{tmp=a[j];a[j]=a[j+1];a[j+1]=tmp;}/*交换a[j]与a[j+1],大数后移*/}}2)选择排序(*****)算法思想：从待排序的序列中，选择最小的一个记录，与第一个数据交换；然后从不包括第一个记录的序列中选择最小一个与第二个交换；如此重复，直至只剩一个数据为止。排序步骤如下：①对n个数，从中选出最小的数，与第1个数交换。②除第1个数外，从剩余的n-1个数中选出最小的数与第2个数交换。③依次类推，交换了n-1次，数组已按升序排列。若按降序，则选最大的数。voidSelectSort(inta[],intn){inti,j,min_i,tmp;for(i=0;in-1;i++){min=i;/*假设第一个数最小，记录其下标*/for(j=i+1;jn;j++)if(a[j]a[min])min=j;/*找最小的，将最小数的下标记录下来*/if(i!=min){tmp=a[i];a[i]=a[min];a[min]=tmp;}/*将最小的数与第一个数进行交换*/}}3)插入排序(***)算法思想：插入排序的基本操作就是将一个数据插入到已经排好序的有序数组中，从而得到一个新的、个数加1的有序数组。插入排序包括很多种，有直接插入排序，折半插入排序，链表插入排序。下面的函数是直接插入排序。voidInsertSort(inta[],intn){inti,j,tmp;for(i=1;in;i++){tmp=a[i];/*空出a[i]单元*/for(j=i-1;j=0&&a[j]tmp;j--)a[j+1]=a[j];/*大于tmp的数向后移位*/a[j+1]=tmp;/*tmp归位*/}}3．归并(或合并)(****)归并就是将两个有序数组A、B合并成另一个有序的数组C（升序或降序）。算法步骤：①先在A、B数组中各取第一个元素进行比较，将小的元素放入C中。②取小的元素所在数组的下一个元素与另一个数组中上次比较后较大的元素比较。③重复上述比较过程，直到某个数组被先排完。④将另一个数组剩余元素抄入C中，合并排序完成。voidmerge(inta[m],intb[n],intc[]){ia=0;ib=0;ic=0;while(iam&&ibn){if(a[ia]b[ib]){c[ic]=a[ia];ia++;}else{c[ic]=b[ib];ib++;}ic++;}while(iam){c[ic]=a[ia];ia++;ic++;}/*a中剩余元素抄入c中*/while(ibn){c[ic]=b[ib];ib++;ic++;}}4．查找(****)查找，就是判断一个数是否是数组中的某个元素。最常见最简单的查找方法为线性法查找，对于已经排过序的数组，可以采用折半法查找。1)线性法查找线性法查找也叫顺序查找，对于没有排序的数组，只能采用线性法查找，有序数组既可以采用线性法查找，也可以采用折半法查找。基本思想：将x与数组中的各个元素从头到尾进行比较，找到返回数组下标，找不到，返回-1。#defineN10intfind(inta[N],intkey){for(i=0;iN;i++)if(a[i]==key){return(i);break;}/*返回数组元素下标*/if(i==N)return(-1);}2)折半法查找折半查找法也称为二分查找法，只能对有序数组进行查找。它充分利用了元素间的次序关系，采用分治策略。折半查找的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的左半部分继续搜索x（这里假设数组元素呈升序排列）。如果xa[n/2]，则我们只要在数组a的右半部分继续搜索x。用C语言函数描述如下：#defineN10intfind(inta[N],intkey){intm;p=0;q=N-1;/*p为第1个元素的下标，q为最后一个元素的下标*/while(p=q){m=(p+q)/2;/*m为中间元素的下标*/if(a[m]==key){return(m);break;}elseif(keya[m])q=m-1;elsep=m+1;}if(pq)return(-1);}二、真题解析1.下列程序的功能是对a数组a[0]～a[n-1]中存储的n个整数从小到大排序。排序算法是：第一趟通过比较将n个整数中的最小值放在a[0]中，最大值放在a[n-1]中；第二趟通过比较将n个整数中的次小值放在a[1]中,次大值放在a[n-2]中；……，依次类推，直到待排序序列为递增序列。试完喜程序以达到要求的功能。(2010年春完善程序的第15题)#includestdio.h#defineN7voidsort(inta[],intn){inti,j,min,max,t;for(i=0;i__________;i++){______________;for(j=i+l;jn-i;j++)if(a[j]a[min])min=j;elseif(a[j]a[max])max=j;if(min!=i){t=a[min];a[min]=a[i];a[i]=t;}if(max!=n-i-1)if(max==i){t=a[min];a[min]=a[n-i-1];a[n-i-1]=t;}else{t=a[max];a[max]=a[n-i-1];a[n-i-1]=t;}}}voidmain(){inta[N]={8,4,9,3,2,1,5},i;sort(a,N);printf(sorted:\n);for(i=0;iN;i++)printf(%d\t,a[i]);printf(\n);}【解析】本题是简单选择法排序的变形。第一趟通过比较将n个整数中的最小值放在a[0]中，最大值放在a[n-1]中，就是比较一趟排了2个：一个最小数、一个最大数，所以比较的趟次是经典排序算法的一半，即n/2次。第一空填n/2，是外循环次数。本题用的是选择法排序，第i趟排序要先假定第i个元素最小，也是最大的，其它的元素与之比较，找出最小的元素下标和最大的元素下标，再进行交换，将最小元素放在剩余于元素的最前面，最大元素放在剩余元素的最后面。min存放最小元素的下标，max存放最大元素的下标，第二空将下标i次赋给min和max。【答案】第一空n/2，第二空min=max=i2.以下程序中函数sort的功能是：把a、b数组中的数据按从大到小的顺序归并到c数组中，m保存a数组中数据的个数，n保存b数组中数据的个数，函数返回归并到c数组的数据个数。算法提示：首先将b数组中数据倒序，再将a、b数组有序合并到c数组中。(2006年秋完善程序第15题