第八讲+循环结构的经典算法之二.ppt

第八讲第八讲 循环结构的经典算法之二循环结构的经典算法之二程序设计举例程序设计举例 教学重点：教学重点：1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根2.2.用用二分法二分法求一元非线性方程在某区间上的近似实根求一元非线性方程在某区间上的近似实根3.3.用用牛顿切线法（又叫牛顿切线法（又叫NewtonNewton迭代法）迭代法）求方程在某区间求方程在某区间 的近似实根的近似实根4.4.用用矩形法矩形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值5.5.用用梯形法梯形法求一元函数在某区间上的积分近似值求一元函数在某区间上的积分近似值6.6.加密、解密算法加密、解密算法0.迭代法的一般含义迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程也称辗转法，是一种不断用变量的旧值递推新值的过程例如：上一讲的例如：上一讲的【【例例5 5】】：：FibonacciFibonacci（斐波纳契数列）（斐波纳契数列）a0= 0a1= 1a2=a0+a1a3=a1+a2a4+=a2+a3a5+=a3+a4a6+=a4+a5……an=an-2+an-1…… 从前有一对长寿兔子，从出从前有一对长寿兔子，从出生后第生后第3个月起每个月都生一对个月起每个月都生一对兔子。

新生的小兔子长到第兔子新生的小兔子长到第3个个月后每个月又都生一对兔子，月后每个月又都生一对兔子，这样一代一代生下去，假设所这样一代一代生下去，假设所有兔子都不死，求兔子增长数有兔子都不死，求兔子增长数量的数列（即每个月的兔子总量的数列（即每个月的兔子总对数）0112358……an……0.迭代法的一般含义迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程也称辗转法，是一种不断用变量的旧值递推新值的过程再如：猴子吃桃再如：猴子吃桃 猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个第二天猴子又将剩下的桃子吃掉一半，又多吃一个以后每天都吃掉前一第二天猴子又将剩下的桃子吃掉一半，又多吃一个以后每天都吃掉前一天剩下的一半零一个到第天剩下的一半零一个到第10天再想吃时，发现只剩下一个桃子问猴子天再想吃时，发现只剩下一个桃子问猴子第一天共摘了多少桃子第一天共摘了多少桃子a1a2a3a4a5a6a7a8a9a101a9=2(a10+1) 4a8=2(a9+1) 10a7=2(a8+1) 22a6=2(a7+1) 46a5=2(a6+1) 94a4=2(a5+1) 190a3=2(a4+1) 382a2=2(a3+1) 766a1=2(a2+1) 15340.迭代法的一般含义再如：编程求再如：编程求再如：编程求再如：编程求a+aa+aaaa+aa+aaa+ …+ + …+ aaaa……a(na(n个个个个a)a)的值。

其中的值其中的值其中的值其中a a是一个从是一个从是一个从是一个从1 1到到到到9 9之之之之间的一个数字要求间的一个数字要求间的一个数字要求间的一个数字要求a a和和和和n n从键盘输入从键盘输入从键盘输入从键盘输入 提示：累加项为提示：累加项为提示：累加项为提示：累加项为term =term =termterm*10+a, term*10+a, term初值为初值为初值为初值为0 0考虑序列：考虑序列：考虑序列：考虑序列：a a0 0 = 0 = 0a a1 1 = a = = a = a a0 0*10 + a*10 + a a a2 2 = = aaaa = = a a1 1*10 + a*10 + a a a3 3 = = aaaaaa =a*100+ a*10 + a = 10*(a*10 + a) + a = =a*100+ a*10 + a = 10*(a*10 + a) + a = a a2 2*10 + a*10 + aa a4 4 = = aaaaaaaa = = a a3 3*10 + a*10 + a………… a an n = = a an-1n-1*10 + a*10 + a 本题等价于求迭代序列的前本题等价于求迭代序列的前本题等价于求迭代序列的前本题等价于求迭代序列的前n n项和项和项和项和 迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。

也称辗转法，是一种不断用变量的旧值递推新值的过程 (其中其中其中其中a a0 0=0, =0, a ai i=a=ai-1i-1*10*10 +a)+a)0.迭代法的一般含义再如再如再如再如 求求求求1!+2!+3!+4!+…+10!1!+2!+3!+4!+…+10!考虑序列：考虑序列：考虑序列：考虑序列：a1=1! = 1a1=1! = 1a a2 2 = 2 * a= 2 * a1 1a a3 3 = 3 * a= 3 * a2 2a a4 4 = 4 * a = 4 * a3 3…….…….a an n = n * a= n * an-1n-1迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程也称辗转法，是一种不断用变量的旧值递推新值的过程 ( 其中其中其中其中 a a1 1=1, =1, a ai i=i * a=i * ai-1 i-1 ) )1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根普通迭代法的基本思想：普通迭代法的基本思想：设设 f(x) 是实函数是实函数, , 求方程求方程f(x)=0 的实根u首先将首先将f(x)=0化为它的等价方程化为它的等价方程x=g(x); u再从某一实数再从某一实数 x x0 0 出发，求序列｛出发，求序列｛xn｝｝, ,其中：其中：                     xn-1=g(xn) n=0 n=0，，1 1，，2 2，，……u如果序列｛如果序列｛xn｝有极限，不访设｝有极限，不访设xn→a, ,当当n→∝。

对上式两端取极限，对上式两端取极限，就有就有 a=g(a), 即即 f(a)=0也就是说，也就是说，a是方程是方程f(x)=0的一个实根的一个实根其中，其中，x0 称为初始近似根，称为初始近似根，xn称为称为n n次近似根，次近似根，g (x) 称称为迭代函数误差可用为迭代函数误差可用| |xn-xn-1| |估计注意：g(x)必须满足一定的条件，才能保证序列{xn}在某一区间上的收敛性这个问题已超出本课讨论的范围1.1.用用普通迭代法普通迭代法求方程的近似实根求方程的近似实根例例例例1 1：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程：编写程序，用普通迭代法求方程f(xf(x)=x+sin(1.2x)-2.15=0)=x+sin(1.2x)-2.15=0在区间在区间在区间在区间[0[0，，，，5]5]上的近似实根迭代初值自选，精确到上的近似实根迭代初值自选，精确到上的近似实根迭代初值自选，精确到上的近似实根迭代初值自选，精确到0.00010.0001include #include main(){double x0 , x1;x1=2.5; /* 初始近似根初始近似根 */do{ x0=x1; x1=2.15-sin(1.2*x0); /* 迭代公式迭代公式 */ }while(fabs(x1-x0)>=1e-4);printf(“方程方程x+sin(1.2x)-2.15=0的近似根的近似根:”);printf("%.4f\n",x0);} 以上方程的等价形式以上方程的等价形式：x=2.15-sin(1.2x)迭代函数迭代函数迭代函数迭代函数g(xg(x) )此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近此程序可作为普通迭代法求方程近似实根的通用模板，只需更改：似实根的通用模板，只需更改：似实根的通用模板，只需更改：似实根的通用模板，只需更改：（（（（1 1）迭代初值；）迭代初值；）迭代初值；）迭代初值；（（（（2 2）迭代函数；）迭代函数；）迭代函数；）迭代函数；（（（（3 3）与具体方程相关的提示信息。

与具体方程相关的提示信息与具体方程相关的提示信息与具体方程相关的提示信息2.2.用二分法求方程的近似实根用二分法求方程的近似实根二分法的基本思想：二分法的基本思想： 设设 f(x) 是连续、实函数是连续、实函数, , 求方程求方程f(x)=0 的实根先找到区间先找到区间(a,b)，使得，使得f(a)，，f(b)异号，说明在区间异号，说明在区间(a,b)内一定有实根：内一定有实根：(1) 求求f((a+b)/2)如果f((a+b)/2)=0，则，则(a+b)/2 就是方程的一个实根，任务完成就是方程的一个实根，任务完成2) 如果如果f((a+b)/2)与与f(b)异号异号, 则说明方程在区间则说明方程在区间((a+b)/2，，b)内实根，令内实根，令a=(a+b)/2，转步骤，转步骤(1)继续计算继续计算3) 如果如果f((a+b)/2)与与f(a)异号，则说明方程在区间异号，则说明方程在区间(a,(a+b)/2)内有零点，令内有零点，令b=(a+b)/2，转步骤，转步骤(1)继续计算继续计算u利用这种方法，每次可以把利用这种方法，每次可以把f(x)的零点所在小区间收缩一半，如此下去，区间的的零点所在小区间收缩一半，如此下去，区间的两个端点将逐步逼近函数的零点。

此法称为两个端点将逐步逼近函数的零点此法称为““二分法二分法””u实际操作时，当实际操作时，当f((a+b)/2)小于要求的误差时，则停止计算，此时小于要求的误差时，则停止计算，此时(a+b)/2称方程称方程的一个近似实根的一个近似实根xyaby=f(x)a+bf(b)f(a)f((a+b)/2)例例2：编写程序，用二分法求一元非线性方程：编写程序，用二分法求一元非线性方程f(x)=2x+sinx-2.15=0 在区间在区间 (0，，5)上的近似实根上的近似实根r，精确到，精确到0.0001include #include main(){ float a=0,b=5,ab, fa, fb, fab; fa=2*a+sin(a)-2.15; fb=2*a+sin(b)-2.15; if( fa * fb > 0 ) printf(“方程可能无实数根！方程可能无实数根！”); else { /* 求近似实根求近似实根 */ } }/* 求近似实根求近似实根 */do { ab=(a+b)/2 fab=2*ab+sin(ab)-2.15 ; if (fa * fab < 0) { b=ab; fb=fab; } else { a=ab; fa=fab; } } while(fabs(fab)>=1e-4) ; printf(“方程的近似实根为方程的近似实根为:%.4f\n",ab);2.2.用二分法求方程的近似实根用二分法求方程的近似实根xyy=f(x)r3. 3. 用用牛顿切线法牛顿切线法求求方程的近似实根方程的近似实根又称又称NewtonNewton迭代法。

迭代法其基本思路：其基本思路：假设假设f(x)是连续、光滑、实函数，求是连续、光滑、实函数，求f(x)=0的实根u设设r是是f(x) = 0的根，选取的根，选取x0作为作为r初始近似值，过点（初始近似值，过点（x0,f(x0)）做曲）做曲线线y = f(x)的切线的切线L，，L的方程为的方程为y = f(x0)+f‘(x0)(x-x0)，求出，求出L与与x轴轴交点的横坐标交点的横坐标 x1 = x0-f(x0)/f’(x0)，称，称x1为为r的一次近似值的一次近似值u过点（过点（x1,f(x1)）做曲线）做曲线y = f(x)的切线，并求该切线与的切线，并求该切线与x轴交点的横轴交点的横坐标坐标 x2 = x1-f(x1)/f‘(x1)，称，称x2为为r的二次近似值重复以上过程，的二次近似值重复以上过程，得得r的近似值序列的近似值序列其中其中xn+1=xn－f(xn)/f‘(xn)，是，是r r的的n+1n+1次近似值，又称为牛顿迭代公式次近似值，又称为牛顿迭代公式x0,f(x0))x0x1(x1,f(x1))x23. 3. 用用牛顿切线法牛顿切线法求求方程的近似实根方程的近似实根例例3：编写程序，用：编写程序，用Newton迭代法求方程迭代法求方程f(x)=2x+cosx-2.6=0在区间在区间[0，，4]上的近似实根上的近似实根r，迭代初值自选，精确到，迭代初值自选，精确到0.0001。

提示提示: :牛顿切线法的迭代公式为牛顿切线法的迭代公式为 x = x – f (x) / f ’ (x)#include #include main(){float x,x0;x=2;do{x0 = x;x=x0 - (2 * x0 + cos(x0) - 2.6 ) / ( 2 - sin(x0) );}while(fabs(x-x0)>=1e-4);printf("%.4f\n",x);}定积分概念回顾定积分概念回顾求定积分求定积分值，等价于求曲线值，等价于求曲线y=f(x)、直线、直线x=a、直线、直线x=b与与x轴围成的区域的面积轴围成的区域的面积(图中阴形部分图中阴形部分)y=f(x)xyx=ax=bba4.4.用用矩形法矩形法求定积分近似值求定积分近似值矩形法的基本思想：矩形法的基本思想：求定积分求定积分l把区间把区间[a,b]平均分成平均分成n个小区间，以每个小区间左端点的函数值为宽、个小区间，以每个小区间左端点的函数值为宽、小区间长度为高作矩形，然后把这小区间长度为高作矩形，然后把这n个小矩形的面积相加，即为所求的个小矩形的面积相加，即为所求的定积分的近似值。

定积分的近似值l显然，小区间数显然，小区间数n越大，求得的定积分的近似求值的精度也越高越大，求得的定积分的近似求值的精度也越高的近似值yxaby=y=f(xf(x) )hh=(b-a)/nai=a+(i-1)*h( ai, f(ai) ) 例例4：编写程序，用矩形法求一元函数：编写程序，用矩形法求一元函数f(x)=(4-(sinx)^2)^(1/2) 在区间在区间[0，，3.1416/6]上的积分近似值上的积分近似值S，保留，保留4位小数（小区间数位小数（小区间数n=15，此参数不，此参数不能改动，否则影响答案，能改动，否则影响答案， 其中其中^表示幂运算表示幂运算 ） #include #include main(){double x, h, a=0, b=3.1416/6, s=0;int i, n=15;h= ( b - a )/n;for(i = 1; i <= n; i++){ x = a + (i - 1) * h; s = s + sqrt(4 - sin(x) * sin(x) );}s = s * h;printf(“定积的近似值为定积的近似值为%.4f\n" ,s);}4.4.用用矩形法矩形法求定积分近似值求定积分近似值5.5.用用梯形法梯形法求定积分近似值求定积分近似值梯形法的基本思想：梯形法的基本思想：求定积分求定积分l把区间把区间[a,b]平均分成平均分成n个小区间，以每个小区间左端点的函数值为上个小区间，以每个小区间左端点的函数值为上底、右端点的函数值为下底、小区间长度为高作梯形，然后把这底、右端点的函数值为下底、小区间长度为高作梯形，然后把这n个小个小梯形的面积相加，即为所求的定积分的近似值。

梯形的面积相加，即为所求的定积分的近似值l显然，小区间数显然，小区间数n越大，求得的定积分的近似求值的精度也越高并且越大，求得的定积分的近似求值的精度也越高并且可以看出，对于同样的小区间数，梯形法的精度比矩形法高可以看出，对于同样的小区间数，梯形法的精度比矩形法高的近似值h=(b-a)/nai=a+(i-1)*hyxaby=y=f(xf(x) )h( ai, f(ai) )例例5：用矩形法和梯形法求一元函数：用矩形法和梯形法求一元函数f(x)=e^(-x^2) 在区间在区间[0,1]上的积分近似值上的积分近似值S，保留，保留4位小数区间数区间数n=10，此参数不能改动否则影响答案，其中，此参数不能改动否则影响答案，其中e为自然对数的为自然对数的底，底，^表示幂运算表示幂运算) 5.5.用用梯形法梯形法求定积分近似值求定积分近似值即，求定积分即，求定积分的近似值的近似值C语言库函数中求语言库函数中求ex的函数是的函数是double exp(double x)有关有关C语言更多的库函数，请参考书后附录语言更多的库函数，请参考书后附录#include#includemain(){ int i,n=10; double a=0, b=1, h, f1, f2, s1 , s2 , x; h = ( b-a ) / n; for( s1=0, s2=0, i=1; i<=n; i++) { x = a + ( i-1 ) * h; f1 = exp( - x * x ); f2 = exp( - (x + h) * (x + h) ); s1 = s1 + f1 * h; /*矩形面积累加矩形面积累加*/ s2 = s2 + ( f1 + f2 ) * h / 2; /*梯形面积累加梯形面积累加*/ } printf("矩形法算得积分值：矩形法算得积分值：%.4lf\n", s1); printf("梯形法算得积分值：梯形法算得积分值：%.4lf\n", s2);}5.5.用用梯形法梯形法求定积分近似值求定积分近似值求 的近似值6.6.加密、解密算法加密、解密算法(P103)(P103)例例5_33:译密文。

规律是将字母变成其后的第译密文规律是将字母变成其后的第4个字母，非字母字符不变，如个字母，非字母字符不变，如“China!”转换为转换为“Gmlre！！”编写程序，从键盘输入一行字符，然后输编写程序，从键盘输入一行字符，然后输出其相应的密文出其相应的密文为使电文保密，往往按一定规律将其转换成密文，收报人再按约定的规为使电文保密，往往按一定规律将其转换成密文，收报人再按约定的规律将其译回原文律将其译回原文a bcdefghijklm nopqrstuvwxyza bcdefghijklm nopqrstuvwxyzA B C D E F G HIJKL M N O P Q R S T U V W X Y ZA B C DE F G HIJKL M N O P Q R S T U V W X Y Z6.6.加密、解密算法加密、解密算法(P103)(P103)例例5_33:译密码规律是将字母变成其后的第译密码规律是将字母变成其后的第4个字母，非字母字符不变，如个字母，非字母字符不变，如“China!”转换为转换为“Gmlre！！”编写程序，从键盘输入一行字符，然后输编写程序，从键盘输入一行字符，然后输出其相应的密文。

出其相应的密文includemain(){ char c; while( (c = getchar() ) != '\n‘ ) { if( (c>=‘a‘ && c<=’z‘ ) || ( c >= ’A‘ && c <= ’Z‘ ) ) /*如果是字母如果是字母 */ { c = c + 4；； if( c>'Z‘ && c <= ‘Z’+4 || c > 'z‘ ) c = c - 26; printf("%c",c); } else printf(“%c”,c); /* 如果不是字母如果不是字母 */ }}课堂小结课堂小结熟练掌握本节所讲的所有算法，熟练掌握本节所讲的所有算法，能够举一反三能够举一反三。