C语言-普通算法归纳.doc
《C语言-普通算法归纳.doc》由会员分享,可在线阅读,更多相关《C语言-普通算法归纳.doc(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 C 语言常用算法归纳语言常用算法归纳应当掌握的一般算法应当掌握的一般算法一、基本算法:一、基本算法:交换、累加、累乘二、非数值计算常用经典算法:二、非数值计算常用经典算法:穷举、排序(冒泡,选择)、查找(顺序即线性)三、数值计算常用经典算法:三、数值计算常用经典算法:级数计算(直接、简接即递推)、一元非线性方程求根(牛顿迭代法、二分法)、定积 分计算(矩形法、梯形法)四、其他:四、其他:迭代、进制转换、矩阵转置、字符处理(统计、数字串、字母大小写转换、加密等)、 整数各数位上数字的获取、辗转相除法求最大公约数(最小公倍数)、求最值、判断素数 (各种变形)、数组元素的插入(删除)、二维数组的其
2、他典型问题(方阵的特点、杨辉三 角形)详细讲解详细讲解一、基本算法一、基本算法 1 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 为中间变量,起到“空杯子”的作用。 注意:三句赋值语句赋值号左右的
3、各量之间的关系!【应用】 例 2、任意读入三个整数,然后按从小到大的顺序输出。 main() int 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 2累加累加累加算法的要领是形如“s=s+A”的累加式,此式必须出现在循环中才能被反复执行,从 而实现累加功能。“A”通常是有规律变化的表达式,s 在进入循环前必须
4、获得合适的初值,通 常为 0。 例 1、求 1+2+3+100 的和。main() int i,s;s=0; 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
5、 main() float x,eps;scanf(“%f%f“,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 2一元非线性方程求根一元非线性方程求根(1)牛顿迭代法 牛顿迭代法又称牛顿切线法:先任意设定一个与真实的根接近的值 x0 作为第一次近似 根,由 x0 求出 f(x0),过(x0,
6、f(x0)点做 f(x)的切线,交 x 轴于 x1,把它作为第二次近似根, 再由 x1 求出 f(x1),过(x1,f(x1)点做 f(x)的切线,交 x 轴于 x2,如此继续下去,直到足 够接近(比如|x- x0|=1e-5);printf (“%fn“,x);(2)二分法 算法要领是:先指定一个区间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) 在区间
7、 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
8、中寻找根,此时 x1 已不起作用,用 x0 代替 x1,用 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.h“ main() float x1,x2,x0,fx1,fx
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 普通 算法 归纳
限制150内