发布时间 : 星期二 文章C语言常用算法精品更新完毕开始阅读7e4248ff03768e9951e79b89680203d8ce2f6a8a
八、常用算法
（一）考核知识要点
1．交换、累加、累乘、求最大（小）值 2．穷举
3．排序（冒泡、插入、选择） 4．查找（顺序、折半） 5．级数计算（递推法）
6．一元方程求解（牛顿迭代法、二分法） 7．矩阵（转置）
8．定积分计算（矩形法、梯形法） 9．辗转相除法求最大公约数、判断素数 10．数制转换
（二）重点、难点精解
教材中给出的算法就不再赘述了。 1．基本操作：交换、累加、累乘
1）交换
交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t;
t=a; a=b; b=t;
(不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。 例如：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分、5分硬币”的所有方法。 main() {int y,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(\}
2）有序序列的插入算法
就是将某数据插入到一个有序序列后，该序列仍然有序。以下给出用数组描述该算法的例子：
将x插入一升序数列后，数列仍为升序排列。
#define n 10 main() {
int a[n]={-1,3,6,9,13,22,27,32,49},x,j,k; /*注意留一个空间给待插数*/ scanf(\
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(\ \}
3）折半查找（二分法查找）
顺序查找的效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查找的前提是数据必须有序。
二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值。
例如，任意读入一个整数x，在升序数组a中查找是否有与x等值的元素。 #define n 10 main()
{int a[n]={2,4,7,9,12,25,36,50,77,90}; int x,high,low,mid;/*x为关键值*/ scanf(\ high=n-1; low=0;
mid=(high+low)/2;
while(a[mid]!=x&&low if(x= =a[mid]) printf(\ else printf(\} 3．数值计算常用经典算法 1）级数计算 级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法又称递推法。 直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个通项写出后一个通项。 可以用直接法描述通项的级数计算例子有： （1）1+2+3+4+5+…… （2）1+1/2+1/3+1/4+1/5+…… 等等。 可以用间接法描述通项的级数计算例子有： （1）1+1/2+2/3+3/5+5/8+8/13+…… （2）1+1/2!+1/3!+1/4! +1/5!+…… 等等。 下面举一个通项的一部分用直接法描述，另一部分用递推法描述的级数计算的例子： 计算级数 ?n?n?02?1?n!x????2?2的值，当通项的绝对值小于eps时计算停止。 #include float g(float x,float eps); main() {float x,eps; scanf(\ printf(\} 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)*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+3x-6=0。 #include \main() {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 (\} 3）二分法 先指定一个区间[x1, x2]，如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和 f(x2)是否同号来确定方程f(x)=0在区间[x1, x2]内是否有一个实根；如果f(x1)和 f(x2)同号，则f(x) 在区间[x1, x2]内无实根，要重新改变x1和x2的值。当确定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)。