《C语言常用算法word版》由会员分享，可在线阅读，更多相关《C语言常用算法word版（8页珍藏版）》请在金锄头文库上搜索。
1、八、常用算法（一）考核知识要点1交换、累加、累乘、求最大（小）值2穷举3排序（冒泡、插入、选择）4查找（顺序、折半）5级数计算（递推法）6一元方程求解（牛顿迭代法、二分法）7矩阵（转置）8定积分计算（矩形法、梯形法）9辗转相除法求最大公约数、判断素数10数制转换（二）重点、难点精解教材中给出的算法就不再赘述了。1基本操作：交换、累加、累乘1）交换交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t; t=a; a=b; b=t;(不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。例如：
2、int a=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）穷举法也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。例如，用穷举法输出“将1元人民币兑换成1分、2
3、分、5分硬币”的所有方法。main()int y,e,w; for(y=0;y=100;y+) for(e=0;e=50;e+) for(w=0;wan-2) an-1=x ; /*比最后一个数还大就往最后一个元素中存放*/ else /*查找待插位置*/ j=0; while( jaj) j+; /*从最后一个数开始直到待插位置上的数依次后移一位*/ for(k=n-2; k=j; k- -) ak+1=ak; aj=x; /*插入待插数*/ for(j=0;j=n-1;j+) printf(%d ,aj);3）折半查找（二分法查找）顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率
4、。使用二分法查找的前提是数据必须有序。二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值。例如，任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。#define n 10main()int an=2,4,7,9,12,25,36,50,77,90; int x,high,low,mid;/*x为关键值*/ scanf(%d,&x); high=n-1; low=0; mid=(high+low)/2; while(amid!=x&lowhigh) if
5、(xamid) high=mid-1; else low=mid+1; mid=(high+low)/2; if(x= =amid) printf(Found %d,%dn,x,mid); else printf(Not foundn);3数值计算常用经典算法1）级数计算级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个通项写出后一个通项。可以用直接法描述通项的级数计算例子有：（1）1+2+3+4+5+（2）1+1/2+1/3+1/4+1/5+等等。可以用间接法描述通项的级数计算例子有：（1
6、）1+1/2+2/3+3/5+5/8+8/13+（2）1+1/2!+1/3!+1/4! +1/5!+等等。下面举一个通项的一部分用直接法描述，另一部分用递推法描述的级数计算的例子：计算级数的值，当通项的绝对值小于eps时计算停止。#include float g(float x,float eps);main()float x,eps; scanf(%f%f,&x,&eps); printf(n%f,%fn,x,g(x,eps);float g(float x,float eps)int n=1;float s,t; s=1; t=1; do t=t*x/(2*n); s=s+(n*n+1)*
7、t; /*加波浪线的部分为直接法描述部分，t为递推法描述部分*/ n+; while(fabs(t)eps); return s;2）牛顿迭代法牛顿迭代法又称牛顿切线法：先任意设定一个与真实的根接近的值x0作为第一次近似根，由x0求出f(x0),过(x0，f(x0)点做f(x)的切线，交x轴于x1，把它作为第二次近似根，再由x1求出f(x1),过(x1，f(x1)点做f(x)的切线，交x轴于x2，如此继续下去，直到足够接近真正的根x*为止。而f (x0)=f(x0)/( x1- x0) 所以 x1= x0- f(x0)/ f (x0)例如，用牛顿迭代法求下列方程在1.5附近的根：2x3-4x2
8、+3x-6=0。#include math.hmain()float x,x0,f,f1; x=1.5; do x0=x; f=2*x0*x0*x0-4*x0*x0+3*x0-6; f1=6*x0*x0-8*x0+3; x=x0-f/f1; while(fabs(x-x0)=1e-5); printf (%fn,x);3）二分法先指定一个区间x1, x2，如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和 f(x2)是否同号来确定方程f(x)=0在区间x1, x2内是否有一个实根；如果f(x1)和 f(x2)同号，则f(x) 在区间x1, x2内无实根，要重新改变x1和x2的值。当确
9、定f(x) 在区间x1, x2内有一个实根后，可采取二分法将x1, x2一分为二，再判断在哪一个小区间中有实根。如此不断进行下去，直到小区间足够小为止。具体算法如下：（1）输入x1和x2的值。（2）求f(x1)和f(x2)。（3）如果f(x1)和f(x2)同号说明在x1, x2 内无实根，返回步骤（1），重新输入x1和x2的值；若f(x1)和f(x2)不同号，则在区间x1, x2内必有一个实根，执行步骤（4）。（4）求x1和x2的中点：x0=（x1+ x2）/2。（5）求f(x0)。（6）判断f(x0)与f(x1)是否同号。如果同号，则应在x0, x2中寻找根，此时x1已不起作用，用x0代替x
10、1，用f(x0)代替f(x1)。如果不同号，则应在x1, x0中寻找根，此时x2已不起作用，用x0代替x2，用f(x0)代替f(x2)。（7）判断f(x0)的绝对值是否小于某一指定的值（例如10-5）。若不小于10-5，则返回步骤（4）重复执行步骤（4）、（5）、（6）；否则执行步骤（8）。（8）输出x0的值，它就是所求出的近似根。例如，用二分法求方程2x3-4x2+3x-6=0在(-10，10)之间的根。#include math.hmain()float x1,x2,x0,fx1,fx2,fx0; do printf(Enter x1&x2); scanf(%f%f,&x1,&x2); f
11、x1=2*x1*x1*x1-4*x1*x1+3*x1-6; fx2=2*x2*x2*x2-4*x2*x2+3*x2-6; while(fx1*fx20);do x0=(x1+x2)/2; fx0=2*x0*x0*x0-4*x0*x0+3*x0-6; if(fx0*fx1)1e-5); printf(%fn,x0);4）梯形法求定积分定积分的几何意义是求曲线y=f(x)、x=a、x=b以及x轴所围成的面积。可以近似地把面积视为若干小的梯形面积之和。例如，把区间a, b分成n个长度相等的小区间，每个小区间的长度为h=(b-a)/n，第i个小梯形的面积为f(a+(i-1)h)+f(a+ih)h/2，
12、将n个小梯形面积加起来就得到定积分的近似值：根据以上分析，给出“梯形法”求定积分的N-S结构图：输入区间端点：a，b输入等分数nh=(b-a)/2, s=0i从1到nsi=(f(a+(i-1)*h)+f(a+i*h)*h/2s=s+si输出s例如：求定积分的值。上述程序的几何意义比较明显，容易理解。但是其中存在重复计算，每次循环都要计算小梯形的上、下底。其实，前一个小梯形的下底就是后一个小梯形的上底，完全不必重复计算。为此做出如下改进：矩形法求定积分则更简单，就是将等分出来的图形当作矩形，而不是梯形。4其他常见算法1）求最大值或最小值在若干个数中求最大值，一般先假设一个较小的数为存放最大值变量
13、的初值，若无法估计较小的值，则取第一个数为存放最大值变量的初值；然后将存放最大值变量的值与其余每一个数比较，若某数大于存放最大值变量的值，将该数赋值给存放最大值的变量；再依次逐一比较。求最小值的方法同样，仅先假设一个较大的数或第一个数为最小值。例如，任意读入10个整数，输出其中的最大值、最小值以及分别是第几个被读入的。main（） int a10, k, x1, x2; int max, min; for(k=0;k10;k+) scanf(“%d”, &ak); max=min=a0; x1=x2=0; for(k=1;kmax) max=ak;x1=k; else if(akmin) min=ak;x2=k; printf(“MAX:%d, XB:%dn”
