《c语言常用算法》word版

《《c语言常用算法》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、八、常用算法（一）考核知识要点1．交换、累加、累乘、求最大（小）值2．穷举3．排序（冒泡、插入、选择）4．查找（顺序、折半）5．级数计算（递推法）6．一元方程求解（牛顿迭代法、二分法）7．矩阵（转置）8．定积分计算（矩形法、梯形法）9．辗转相除法求最大公约数、判断素数10．数制转换（二）重点、难点精解教材中给出的算法就不再赘述了。1．基本操作：交换、累加、累乘1）交换交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：inta=7,b=9,t;t=a;a=b;b=t;(不借助第三者，也能交换两个整型变量里的数值，但不

2、通用，只是一个题目而已。例如：inta=7,b=9;a=a+b;b=a-b;a=a-b;)2）累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。3）累乘累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。2．非数值计算常用经典算法1）穷举法也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。例如，

3、用穷举法输出“将1元人民币兑换成1分、2分、5分硬币”的所有方法。main(){inty,e,w;for(y=0;y<=100;y++)for(e=0;e<=50;e++)for(w=0;w<=20;w++)if(1*y+2*e+5*w==100)printf("%d,%d,%d",y,e,w);}2）有序序列的插入算法就是将某数据插入到一个有序序列后，该序列仍然有序。以下给出用数组描述该算法的例子：将x插入一升序数列后，数列仍为升序排列。#definen10main(){inta[n]={-1,3,6,9,13,22,27,32,49},x,j,k;/*注意留一个空间给待

4、插数*/scanf("%d",&x);if(x>a[n-2])a[n-1]=x;/*比最后一个数还大就往最后一个元素中存放*/else{/*查找待插位置*/j=0;while(j<=n-2&&x>a[j])j++;/*从最后一个数开始直到待插位置上的数依次后移一位*/for(k=n-2;k>=j;k--)a[k+1]=a[k];a[j]=x;/*插入待插数*/}for(j=0;j<=n-1;j++)printf("%d",a[j]);}3）折半查找（二分法查找）顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数据必须有序。二分法查找的思路是：要

5、查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值。例如，任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。#definen10main(){inta[n]={2,4,7,9,12,25,36,50,77,90};intx,high,low,mid;/*x为关键值*/scanf("%d",&x);high=n-1;low=0;mid=(high+low)/2;while(a[mid]!=x&&low

6、elselow=mid+1;mid=(high+low)/2;}if(x==a[mid])printf("Found%d,%d",x,mid);elseprintf("Notfound");}3．数值计算常用经典算法1）级数计算级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个通项写出后一个通项。可以用直接法描述通项的级数计算例子有：（1）1+2+3+4+5+……（2）1+1/2+1/3+1/4+1/5+……等等。可以用间接法描述通项的级数计算例子有：（1）1+1/2

7、+2/3+3/5+5/8+8/13+……（2）1+1/2!+1/3!+1/4!+1/5!+……等等。下面举一个通项的一部分用直接法描述，另一部分用递推法描述的级数计算的例子：计算级数的值，当通项的绝对值小于eps时计算停止。#includefloatg(floatx,floateps);main(){floatx,eps;scanf("%f%f",&x,&eps);printf("%f,%f",x,g(x,eps));}floatg(floatx,floateps){