语言常用算法

1、八、常用算法（一）考核知识要点1 .交换、累加、累乘、求最大（小）值2 .穷举3 .排序（冒泡、插入、选择）4 .查找（顺序、折半）5 .级数计算（递推法）6 . 一元方程求解（牛顿迭代法、二分法）7 .矩阵（转置）8 .定积分计算（矩形法、梯形法）9 .辗转相除法求最大公约数、判断素数10 .数制转换（二）重点、难点精解教材中给出的算法就不再赘述了。11 基本操作：交换、累加、累乘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。12 非数值计算常用经典算法1）穷举法也称为“枚举法”，即将可能出现的各种情况一一测试，判断是

3、否满足条件，一般 采用循环来实现。例如，用穷举法输出“将 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("%d,%d,%dn",y,e,w);2)有序序列的插入算法就是将某数据插入到一个有序序列后，该序列仍然有序。以下给出用数组描述该 算法的例子：将x插入一升序数列后，数列仍为升序排列。#define n 10main()int an尸-1,3,6,9,13,22,2

4、7,32,49,x,jK /* 注意留一个空间给待插数*/scanf("%d",&x);if(x>an-2) an-1=x ;/*比最后一个数还大就往最后一个元素中存放*/else/*查找待插位置*/j=0；while( j<=n-2 && x>aj)j+;/*从最后一个数开始直到待插位置上的数依次后移一位*/for(k=n-2; k>=j; k-)ak+1=ak;aj=x; /*插入待插数*/for(j=0;j<=n-1;j+) printf("%d ",aj);3)折半查找(二分法查找)顺序查找的

5、效率较低，当数据很多时，用二分法查找可以提高效率。使用二分法查 找的前提是数据必须有序。二分法查找的思路是：要查找的关键值同数组的中间一个元素比较，若相同则查找成功，结束；否则判别关键值落在数组的哪半部分，就在这半部分中按上述方法继续比较，直到找到或数组中没有这样的元素值。例如，任意读入一个整数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=(

6、high+low)/2;while(amid!=x&&low<high)if(x<amid) high=mid-1;else low=mid+1;mid=(high+low)/2;if(x= =amid) printf("Found %d,%dn”,x,mid);else printf("Not found'n");13 数值计算常用经典算法1)级数计算级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法 又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个通项写出后一个通项。可

7、以用直接法描述通项的级数计算例子有：(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!+ ,下面举一个通项的一部分用直接法描述，另一部分用递推法描述的级数计算的例子：2,、2计算级数n 1 x 的值，当通项的绝对值小于eps时计算停止。二 n! 2/#include <math.h>float g(float x,float eps);main()float x,eps;scanf("

8、%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).*t;/*加波浪线的部分为直接法描述部分，t为递推法描述部分*/n+;while(fabs(t)>eps);return s;2)牛顿迭代法牛顿迭代法又称牛顿切线法：先任意设定一个与真实的根接近的值xo作为第一次近似根，由xo求出f(Xo)，过(xo, f(xo)点做f(x)的切线，交x轴于xi,把它

9、作为第二次近似根，再 由xi求出f(xi),过(xi, f(xi)点做f(x)的切线，交x轴于x2,，如此继续下去，直到足够接 近真正的根x*为止。而 f '(x o)=f(x o)/( x 1- xo)所以 xi= xo- f(x o)/ f ' (x o)例如，用牛顿迭代法求下列方程在1.5附近的根：2x3-4x2+3x-6=o。#include "math.h" main()float x,xo,f,f1;x=1.5;dox0=x;f=2*x0*x0*x0-4*x0*x0+3*x0-6;f1=6*x0*x0-8*x0+3;x=x0-f/f1;while

10、(fabs(x-x0)>=1e-5);printf ("%fn",x);3)二分法先指定一个区间Xi, x2,如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和f(x2)是否同号来确定方程 f(x)=o在区间Xi, x2内是否有一个实根；如果f(x1)和f(x2)同号，则f(x) 在区间Xi, x2内无实根，要重新改变 Xi和x2的值。当确定f(x)在区间Xi, x2内有一个实根 后，可采取二分法将X1, X2一分为二，再判断在哪一个小区间中有实根。如此不断进行下去，直到小区间足够小为止。具体算法如下：(1 )输入X1和x2的值。(2)求 f(X1)和 f(

11、x2)。(3)如果f(X1)和f(X2)同号说明在X1, X2内无实根，返回步骤(1),重新输入X1 和X2的值；若f(X1)和f(x2)不同号，则在区间X1, X2内必有一个实根，执行步骤(4)。(4)求X1和X2的中点：Xo= (X1+ X2) /2。(5)求 f(xo)o(6)判断f(xo)与f(x1)是否同号。如果同号，则应在Xo, X2中寻找根，此时X1已不起作用，用Xo代替X1,用 f(xo)代替 f(X1)o如果不同号，则应在X1, xo中寻找根，此时X2已不起作用，用Xo代替X2,用 f(Xo)代替 f(X2)。(7)判断f(X0)的绝对值是否小于某一指定的值(例如10-5)。

12、若不小于10-5,则返回步骤(4)重复执行步骤(4)、(5)、(6);否则执行步骤(8)。(8)输出Xo的值，它就是所求出的近似根。例如，用二分法求方程2x3-4x2+3x-6=0在(-10, 10)之间的根。#include "math.h"main()float x1,x2,x0,fx1fx2,fx0;doprintf("Enter x1&x2");scanf("%f%f",&x1,&x2);仅1=2*x1*x1*x1-4*x1*x1+3*x1-6;fx2=2*x2*x2*x2-4*x2*x2+3*x2-6

13、;while(fx1*仅2>0);dox0=(x1+x2)/2;fx0=2*x0*x0*x0-4*x0*x0+3*x0-6;if(fx0*fx1)<0)x2=x0;fx2=fx0;elsex1=x0;fx1=fx0;while(fabs(fx0)>1e-5);printf("%fn",x0);4)梯形法求定积分b定积分i f (x)dx的几何意义是求曲线y=f(x)、x=a、x=b以及x轴所围成的面积。a可以近似地把面积视为若干小的梯形面积之和。例如，把区间 a, b分成n个长度相等的小区间，每个小区间的长度为h=(b-a)/n,第i个小梯形的面积为f(a

14、+(i-1) h)+f(a+i h) h/2,将n个小梯形面积加起来就得到定积分的近似值：bnf ( x) dx f(a (i-1)*h) f(a i*h)*h/2ai =1根据以上分析，给出“梯形法”求定积分的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例如：求定积分 jsin x 2 dx的值。上述程序的几何意义比较明显，容易理解。但是其中存在重复计算，每次循环都要计算小梯形的上、下底。其实，前一个小梯形的下底就是后一个小梯形的上底，完全不必重复计 算。为此做出如下改进：bn

15、 -1f ( x ) dx : h f ( a ) / 2 f ( b ) / 2 -q f ( a ' i h ) ai =i矩形法求定积分则更简单，就是将等分出来的图形当作矩形，而不是梯形。4.其他常见算法1)求最大值或最小值在若干个数中求最大值，一般先假设一个较小的数为存放最大值变量的初值，若无法估计较小的值，则取第一个数为存放最大值变量的初值；然后将存放最大值变量的值与其余每一个数比较，若某数大于存放最大值变量的值，将该数赋值给存放最大值的变量；再依次逐一比较。求最小值的方法同样，仅先假设一个较大的数或第一个数为最小值。例如，任意读入10个整数，输出其中的最大值、最小值以及分别

16、是第几个被读入的。main () int a10, k, x1, x2;int max, min;for(k=0;k<10;k+)scanf( %d”, &ak);max=min=a0;x1=x2=0;for(k=1;k<10;k+)if(ak>max) max=ak;x1=k;else if(ak<min) min=ak;x2=k;printf( MAX:%d, XB:%dn ”, max, x1+1);printf( MIN:%d, XB:%dn ”, min, x2+1); 2)迭代法其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。每次重复都从旧

17、值的基础上递推出新值，并由新值代替旧值。例如，猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃 了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10天早上想再吃时，就只剩一个桃子了。编程求第一天共摘多少 桃子。main()int day,peach;peach=1;for(day=9;day>=1;day-)peach=(peach+1)*2;printf("The first day:%dn",peach); 又如，用迭代法求x= ja的根。求平方根的迭代公式是：Xn+i=0.5 X (x

18、n+a/ Xn )算法(1)设定一个初值X0O(2)用上述公式求出下一个值Xi。(3)再将X1代入上述公式，求出下一个值 x2o(4)如此继续下去，直到前后两次求出的X值(Xn+1和Xn)满足以下关系：-5 | Xn+1- Xn|<10#include "math.h" main()float a,X0,X1; scanf("%f",&a);*0=2以X1=(X0+a/X0)/2; do x0=x1;X1=(X0+a/X0)/2;while(fabs(x0-x1)>=1e-5); printf("%fn",x1);3)辗转相除法求最大公约数求任意两个正整数(m和n)的最大公约数，可采用辗转相除法：(1)先算出m除以n的余数r; r=m%n;(2)判断r是否为0,若为0,则n即为所求；否则，将 m的值修改为n, n的值修改 为r;(3)再算出新m除以新n的余数r,重复(2), main() int m,n,r;scanf("%d%d",&m,