期末考试相关说明.doc

以下说明为考试可能考到的考点（书上没有的内容）请大家一定要看并记住算法。说明1 clrscr函数名: clrscr功 能: 清除文本模式窗口 清屏的意思 就是把之前显示出的文字字符去掉 跟cmd里面的清屏的功能是一样的 实际上是clear screen的简写用 法: void clrscr(void);程序例:#include int main(void) int i; clrscr(); for (i = 0; i 20; i+) cprintf(%drn, i); cprintf(rnPress any key to clear screen); getch(); clrscr(); cprintf(The screen has been cleared!); getch(); return 0; 说明 2 牛顿迭代法编写程序，用牛顿迭代法求方程f(x)=3x3-4x2-5x+13=0的满足精度为10-6的一个近似实根。分 析：这也是教材习题中要求掌握的一类算法题。该题涉及到了牛顿迭代法的计算方法：设一初值x0，然后用牛顿迭代公式 x=x0-f(x0)/f(x0)计算出下一个x，重复不断地用刚计算出的x取代上一个x值，接着再用迭代公式计算新的x,直至两次计算出的x的差额不 超过10-6为止。正确答案：-1.548910程序流程分析： 输入值x0,即迭代初值； 用初值x0代入方程中计算此时的f(x0)及f(x0)，程序中用变量f描述方程的值，用fd描述方程求导之后的值； 计算增量d=f/fd； 计算下一个x，x=x0-d; 把新产生的x替换x0，为下一次迭代做好准备; 若d的绝对值大于1e-5，则重复步。源程序代码：#include main()float x,x0,d,f,fd;scanf(%f,&x0);do f=3*x0*x0*x0-4*x0*x0-5*x0+13;fd=9*x0*x0-8*x0-5;d=f/fd;x=x0-d;x0=x; while(fabs(d)1e-5);printf(x=%fn,x);例6.12 用牛顿迭代法求方程2x3-4x2+3x-6=0在1.5附近的根解：牛顿迭代法又称牛顿切线法。它采用以下的方法求根：先任意设定一个与真实的根接近的值x0作为第一次近似根，由x0求出f(x0)，过(x0,f(x0)点做f(x)的切线，交x轴于x1，把它作为第二次近似根，再由x1求出f(x1)，过(x1,f(x1)点做f(x)的切线,交x轴于x2，求出f(x2)；再作切线如此继续下去，直到足够接近真正的根x*为止。 f(x0)=f(x0)/(x1-x0)因此：x1=x0-f(x0)/f(x0)这就是牛顿迭代公式。可以利用它由x0求出x1，然后再由x2求出x3设f(x)=2x3-4x2+3x-6可以写成以下形式： f(x)=(2x-4)x+3x-6同样,f(x)可写成： f(x)=6x2-8x+3=(6x-8)x+3用这种方法表示的表达式，在运算时可节省时间。例如求f(x)只需要进行3次乘法和3次加法，而原来的表达式要经过多次指数运算、对数运算和乘法、加法运算，花费时间较多。现在由于计算机的运算速度愈来愈快，这点时间开销是微不足道的，这是以前计算机的运算速度较慢时所提出的问题。由于过去编写的程序往往采用这种形式，所以我们在此也顺便介绍一下，以便在阅读别人所写的程序时知道其所以然。程序如下：（xt6-12.c）#include #include main() float x,x0,f,f1;x=1.5;do x0=x;f=(2*x0-4)*x0+3)*x0-6;f1=(6*x0-8)*x0+3;x=x0-f/f1;while(fabs(x-x0)=1e-5);printf(The root of equation is%5.2fn,x);运行结果:The root of equation is 2.OO为了便于循环处理，程序中只设了x0和x，x0代表前一次的近似根，x代表后一次的近似根。求出一个x后，把它的值赋给x0，然后用它求下一个x0由于第一次执行循环体时，需要对x0赋值，故在开始时应先对x赋一个初值(今为1.5，也可以是接近真实根的其他值)。说明3 二分法6.13 用二分法求下面方程在(-10,10)之间的根。2x3-4x2+3x-6=0解：二分法的思路如下：先指定一个区间x1,x2)，如果函数f(x)在此区间是单调变化的，则可以根据f(x1)和f(x2)是否同号来确定方程f(x)=0在区间x1,x2内是否有一个实根。若f(x1)和f(x2)不同号，则f(x)=在区间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) 。(6)判断f(x0)与f(x1)是否同号。如果同号，则应在x0,x2中寻找根，此时x1已不起作用，用x0代替x1，用f(x0)代替f(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的值，它就是所求出的近似根。#include #include main() float x0,x1,x2,fx0,fx1,fx2;do printf(Enter x1 & x2：);scanf(%f,%f,&x1,&x2);fx1=x1*(2*x1-4)*x1+3)-6;fx2=x2*(2*x2-4)*x2+3)-6;while(fx1*fx20);do x0=(x1+x2)/2;fx0=x0*(2*x0-4)*x0+3)-6;if(fx0*fx1)=1e-5);printf(x=%6.2fn,x0);说明4折半查找法折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数a0a4，要查找的数是X，其基本思想是：设查找数据的范围下限为l=1，上限为h=5，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找；否则，若X大于am，替换下限l=m+1，到下半段继续查找；若X小于am，换上限h=m-1，到上半段继续查找；如此重复前面的过程直到找到或者lh为止。如果lh，说明没有此数，打印找不到信息，程序结束。该方法是查找的范围不断缩小一半，所以查找效率较高。比如1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100 要找82 需要找几次4次第一次：1, 3, 9, 12, 32, 41, 【45】, 62, 75, 77, 82, 95, 100 第二次：1, 3, 9, 12, 32, 41, 【45】, 62, 75, 【77】, 82, 95, 100 第三次：1, 3, 9, 12, 32, 41, 【45】, 62, 75, 【77】, 82, 【95】, 100第四次：1, 3, 9, 12, 32, 41, 【45】, 62, 75, 【77】, 【82】, 【95】, 100运用举例1. /折半查找2. int BinSearch1(int r , int n, int k)3. 4. int low=0, high=n; /设置初始查找区间5. while (low=high) 6. 7. int mid=(low+high)/2; /取中间点, 比较k与rmid， 8. if (krmid) 12. low=mid+1; 13. else 14. return mid; /查找成功15. 16. return 0; /查找失败说明5 选择排序（与书上p134 7.3起泡的区别？） 原理 一次选定数组中的每一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，则交换min与i位置上的数。用选择法对10个整数排序（从小到大）。1程序分析：所谓选择法就是先将10个数中最小的数与a0对换；再将a1到a9中最小的数与a1对换每比较一轮，找出一个未经排序的数中最小的一个。共比较9轮。下面以5个数为例说明选择法的步骤。a0 a1 a2 a3 a43 6 1 9 4 未排序时的情况 1 6 3 9 4 将5个数中最小的数1与a0对换 1 3 6 9 4 将余下的4个数中最小的数3与a1对换 1 3 4 9 6 将余下的3个数中最小的数4与a2对换 1 3 4 6 9 将余下的2个数中最小的数6与a3对换，至此完成排序2程序流程图：NNNYYYYYN开 始结 束i=0i10输入aii+调用子程序i=0i10输出aii+N主程序流程图i=0in-1k=i, j=i+1jnarrayjarraykk=j, j+tarrayk；arraykarrayi；arrayit；i+子程序流程图3程序N-S图： for (i=0; in-1; i+) k=i for (j=i+1; jn; j+) arrayjarrayk k=j tarrayk；arraykarrayi；arrayit；主程序N-S图真假子程序N-S图 for (i=0; i10; i+) 输入ai 调用子程序for (i=0; i10; i+) 输出ai4程序源代码： void sort(int array，int n) int i，j，k，t； for(i0；in-1；i+) ki； for(ji+1；jn；j+) if(arrayjarrayk)kj； tarrayk；arraykarrayi；arrayit； main() int a10，i； printf(enter the array：n)； for(i0；i10；i+) scanf(%d，&ai)； sort(a，10)； printf(the sorted array：n)； for(i0；i10；i+) printf(%d，ai)； printf(n)； 5程序运行结果： enter the array： 3 6 1 9 4 the sorted array： 1 3 4 6 9此外还有一些历年来的重点内容，也请记住 p129 6.1 , 6.6, 6.11三道题的解法及原理，具体原理例题如下辗转相除法辗转相除法, 又名欧几里德算法（Euclidean algorithm）乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出现于欧几里德的几何原本（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的九章算术。它并不需要把二数作质因子分解。证明：设两数为a、b(ba)，求它们最大公约数(a、b)的步骤如下：用b除a，得abq.r 1(0r)。若r1=0，则(a，b)b；若r10，则再用r1除b，得br1q.r2 (0r2).若r20，则(a，b)r1，若r20，则继续用r2除r1,如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。编辑 算法辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：1. 若 r 是 a b 的余数, 则gcd(a,b) = gcd(b,r)2. a 和其倍数之最大公因子为 a。另一种写法是：1. a b，令r为所得余数（0rb）若 r = 0，算法结束；b 即为答案。2. 互换：置 ab，br，并返回第一步。P129 6.1输入两个正整数m和n, 求其最大公约数和最小公倍数. 用辗转相除法求最大公约数 算法描述: m对n求余为a, 若a不等于0 则 m - n, n - a, 继续求余 否则 n 为最大公约数 最小公倍数 = 两个数的积 / 最大公约数 #include int main() int m, n; int m_cup, n_cup, res; /*被除数, 除数, 余数*/ printf(Enter two integer:n); scanf(%d %d, &m, &n); if (m 0 & n 0) m_cup = m; n_cup = n; res = m_cup % n_cup; while (res != 0) m_cup = n_cup; n_cup = res; res = m_cup % n_cup; printf(Greatest common divisor: %dn, n_cup); printf(Lease common multiple : %dn, m * n / n_cup); else printf(Error!n); return 0; 水仙花数P129 6.6 找出所有的水仙花数.水仙花数是一个3位数,其各位数字立方和等于该数本身#include void main()int i,j,k,n;printf(水仙花数是:);for(n=100;nEpsilon)； printf(“方程的近似根是%fn”，x0)； 迭代算法也常用于求方程组的根，令 X=（x0，x1，xn-1） 设方程组为： xi=gi(X) (I=0，1，n-1) 则求方程组根的迭代算法可描述如下： 【算法】迭代法求方程组的根 for (i=0;i x=初始近似根; do for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)delta) delta=fabs(y-x)； while (deltaEpsilon)； for (i=0;i printf(“变量x%d的近似根是 %f”，I，x)； printf(“n”)； 具体使用迭代法求根时应注意以下两种可能发生的情况： （1） 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭