非常全的C语言常用算法.doc

1、C 语言常用算法一、基本算法 1交换（两量交换借助第三者）例 1、任意读入两个整数，将二者的值交换后输出。main()int a,b,t;scanf(“%d%d“,printf(“%d,%dn“,a,b);t=a; a=b; b=t;printf(“%d,%dn“,a,b);【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。假设输入的值分别为 3、7，则第一行输出为 3，7；第二行输出为 7，3。其中 t 为中间变量，起到“空杯子 ”的作用。注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例 2、任意读入三个整数，然后按从小到大的顺序输出。main()i

2、nt a,b,c,t;scanf(“%d%d%d“,/*以下两个 if 语句使得 a 中存放的数最小*/if(ab) t=a; a=b; b=t; if(ac) t=a; a=c; c=t; /*以下 if 语句使得 b 中存放的数次小*/if(bc) t=b; b=c; c=t; printf(“%d,%d,%dn“,a,b,c);2累加累加算法的要领是形如“s= s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。 “A”通常是有规律变化的表达式， s 在进入循环前必须获得合适的初值，通常为0。例 1、求 1+2+3+100 的和。main()int i,s;s=0;

3、i=1;while(iai+1)t=ai;ai=ai+1;ai+1=t;for(i=0;ian-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=i;k-) ak+1=ak;ai=x; /*插入待插数*/for(i=0;i=m main()float x,eps;scanf(“%f%f“,printf(“n%f,%fn“,x,g(x,eps)

4、;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一元非线性方程求根（1）牛顿迭代法牛顿迭代法又称牛顿切线法：先任意设定一个与真实的根接近的值 x0 作为第一次近似根，由x0 求出 f(x0),过 (x0，f(x 0)点做 f(x)的切线，交 x 轴于 x1，把它作为第二次近似根，再由 x1 求出f(x1),过 (x1，f(x 1)点做 f(x)的切线，交

5、 x 轴于 x2，如此继续下去，直到足够接近（比如|x- x0|=1e-5);printf (“%fn“,x); （2）二分法算法要领是：先指定一个区间x 1, x2，如果函数 f(x)在此区间是单调变化的，则可以根据 f(x1)和f(x2)是否同号来确定方程 f(x)=0 在区间x 1, x2内是否有一个实根；如果 f(x1)和 f(x2)同号，则 f(x) 在区间x 1, x2内无实根，要重新改变 x1 和 x2 的值。当确定 f(x) 在区间x 1, x2内有一个实根后，可采取二分法将x 1, x2一分为二，再判断在哪一个小区间中有实根。如此不断进行下去，直到小区间足够小为止。具体算法如

6、下：（1）输入 x1 和 x2 的值。（2）求 f(x1)和 f(x2)。（3）如果 f(x1)和 f(x2)同号说明在 x1, x2 内无实根，返回步骤（1） ，重新输入 x1 和 x2 的值；若f(x1)和 f(x2)不同号，则在区间x 1, x2内必有一个实根，执行步骤（4） 。（4）求 x1 和 x2 的中点：x 0=（x 1+ x2）/2 。（5）求 f(x0)。（6）判断 f(x0)与 f(x1)是否同号。如果同号，则应在x 0, x2中寻找根，此时 x1 已不起作用，用 x0 代替 x1，用 f(x0)代替 f(x1)。如果不同号，则应在x 1, x0中寻找根，此时 x2 已不起

7、作用，用 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.h“main()C 语言常用算法float x1,x2,x0,fx1,fx2,fx0;do printf(“Enter x1scanf(“%f%f“,fx1=2*x1*x1*x1-4*x1*x1+3*x1-6

8、;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);3梯形法计算定积分定积分 的几何意义是求曲线 y=f(x)、x=a、x=b 以及 x 轴所围成的面积。badxf)(可以近似地把面积视为若干小的梯形面积之和。例如，把区间a, b 分成 n 个长度相等的小区间，每个小区间的长度为 h=(b-a)/n，第 i 个小梯形的面积为f(a+(i-1)h)+f(a+ih)h/2，将 n 个小梯形面积加起来

9、就得到定积分的近似值： niba hiafhiafdxf1 2/)()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上述程序的几何意义比较明显，容易理解。但是其中存在重复计算，每次循环都要计算小梯形的上、下底。其实，前一个小梯形的下底就是后一个小梯形的上底，完全不必重复计算。为此做出如下改进： ba ni hiafbfafhdxf 1)(2/)(2/)()(C 语言常用算法矩形法求定积分则更简单，就是将等分出来的图形当作

10、矩形，而不是梯形。例如：求定积分 的值。等分数 n=1000。40)2*3(dxx#include “math.h“float DJF(float a,float b)float t,h; int n,i;float HSZ(float x);n=1000; h=fabs(a-b)/n;t=(HSZ(a)+HSZ(b)/2;for(i=1;i=n-1;i+) t=t+HSZ(a+i*h);t=t*h;return(t);float HSZ(float x)return(x*x+3*x+2); main()float y;y=DJF(0,4);printf(“%fn“,y);四、其他常见算法1迭代法其基本思想是把一个复杂的计算过程转化为简单过程的多次重复。每次重复都从旧值的基础上递推出新值，并由新值代替旧值。例如，猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第 10 天早上想再吃时，就只剩一个桃子了。编程求第一天共摘多少桃子。main()int day,peach;