實驗五-綜合算法應(yīng)用-教師版

實驗五-綜合算法應(yīng)用-教師版實驗五-綜合算法應(yīng)用-教師版/NUM，在2附近的根。程序文件名ex5_3.c。牛頓迭代法（Newton'smethod），又稱為牛頓切線法，是牛頓在17世紀提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法，是求非線性方程根的重要方法之一。圖5.1牛頓迭代法求根設(shè)f(x)=0是非線性方程，f(x)在某一區(qū)間內(nèi)為單調(diào)函數(shù)，則方程f(x)=0在某一區(qū)間只有一個實根。牛頓迭代法的幾何意義，如圖5.1所示，f(x)=0的解就是y=f(x)與x軸的交點的橫坐標，也就是給定一個初值x1，不斷通過切線方程的迭代求解而逼近解x*的過程。先設(shè)定一個與真實根接近的x1作為第一個近似根，過點（x1,f(x1)）作f(x)的切線，與x軸相交于x2，這時，我們把x2作為第二個近似根；即，過點（x2,f(x2)）作f(x)的切線，與x軸相交于x3，這時，我們把x2作為第三個近似根；即，過點（x3,f(x3)）作f(x)的切線，與x軸相交于x4，依次類推，直到接近真正的根x*為止。由此得到牛頓迭代公式，牛頓迭代法求非線性方程的根的基本算法：確定迭代變量，舊值：x1；新值x；以及相對應(yīng)的函數(shù)值變量f1，即代表f(x1)；導(dǎo)數(shù)值變量f2，即代表f’(x1)。牛頓迭代公式：x=x1-f1/f2確定迭代終止條件，當fabs(x-x0)<1e-5時，迭代終止。牛頓迭代法求非線性方程的根的算法描述：S1：先任意確定一個與真實的根接近的初始值x；S2：將x1作為舊值，x1=x；S3：求x1的函數(shù)值f1與在這點的導(dǎo)數(shù)值f2；S4：由牛頓迭代公式求新x；S5：判斷前后兩值是否小于給定的一個值精度，若是轉(zhuǎn)到S6，否則返回S2；S6：輸出x為方程的近似根。#include<stdio.h>#include<math.h>voidmain(){doublex,x1,f,f1;x=2;do{x1=x;f=3*x1*x1*x1-9*x1*x1+4*x1-12;f1=9*x1*x1-18*x1+4;x=x1-f/f1;}while(fabs(x1-x)>=1e-5);printf("Therootis%6.2lf\n",x);}程序運行結(jié)果：Therootis3.00【5.4】編程實現(xiàn)，用二分法求方程2x3-4x2+3x-6=0在（-10,10）之間的根。程序文件名ex5_4.c。二分法，也稱為對分法。是求非線性方程f(x)=0在區(qū)間[a,b]的實根的一種簡單高效的求解方法。二分法求方程的根是將給定的區(qū)間一分為二為兩個區(qū)間，確定存在根的區(qū)間，再對該區(qū)間一分為二為兩個區(qū)間，再次確定存在根的區(qū)間。依次類推，直到分的區(qū)間足夠小為止。也可以說逐次把有根區(qū)間對分，直到找到根或有根區(qū)間的長度小于給定精度為止。因此二分法求方程的根的關(guān)鍵問題，是如何確定存在根的區(qū)間？若函數(shù)f(x)在閉區(qū)間[a,b]上為單調(diào)函數(shù)，且f(a)與f(b)異號(即f(a)*f(b)<0)，則在該區(qū)間內(nèi)f(x)有一個實根。設(shè)定f(x)=2x3-4x2+3x-6，區(qū)間為[x1,x2]，區(qū)間端點的函數(shù)值變量為f1和f2。中點變量為x,對應(yīng)的函數(shù)值變量為f。如圖5.2所示。圖5.2二分法求根二分法求非線性方程的根的算法描述：S1．輸入x1和x2的區(qū)間值；S2。求區(qū)間端點的函數(shù)值f1和f2；S3．確定在該區(qū)間內(nèi)函數(shù)有根。若f1*f2>0，在該區(qū)間內(nèi)無根，返回S1。否則繼續(xù)S4；S4．計算x1，x2的中點，x=（x1+x2）/2；S5．計算中點的函數(shù)值f；S6．判斷根存在的區(qū)間。若f*f1>0，則根存在于區(qū)間[x,x2]，更改存在根的區(qū)間，即，x1=x，f1=f。否則根存在于區(qū)間[x1,x]，更改存在根的區(qū)間，即，x2=x，f2=f。S7．判斷|x1-x2|<10-5或|f(x0)|<10-5。若成立執(zhí)行S8，否則返回S4；S8．輸出方程的近似根x的值。#include<stdio.h>#include<math.h>voidmain(){doublex1,x2,x,f1,f2,f;do{printf("Enterx1,x2:\n");scanf("%lf,%lf",&x1,&x2);f1=2*x1*x1*x1-4*x1*x1+3*x1-6;f2=2*x2*x2*x2-4*x2*x2+3*x2-6;}while(f1*f2>0);do{x=(x1+x2)/2;f=2*x*x*x-4*x*x+3*x-6;if(f*f1<0) { x2=x;f2=f; } else{ x1=x;f1=f; }}while(fabs(x1-x2)>=1e-5);printf("root=%6.3f\n",x);}5.3實驗內(nèi)容【5.5】編寫實現(xiàn)，程序功能是，利用簡單迭代公式，求方程：cos(x)-x=0的一個實根。程序文件名：ex5_5.c。程序運行結(jié)果：Root=0.739086【參考源程序】#include<math.h>#include<stdio.h>voidmain(){doublex0,x1=0.0;do{x0=x1;x1=cos(x0);}while(fabs(x0-x1)>0.000001);printf("Root=%lf\n",x1);}小結(jié)：迭代步驟如下：（1）取x1初值為0.0；（2）x0=x1，把x1的值賦給x0；（3）x1=cos(x0)，求出一個新的x1；（4）若x0-x1的絕對值小于0.000001，執(zhí)行步驟（5），否則執(zhí)行步驟（2）；（5）所求x1就是方程cos(x)-x=0的一個實根，作為函數(shù)值返回。【5.6】編程實現(xiàn)，有一只猴子第一天摘下了若干個桃子，當即吃掉一半，還覺得不過癮，又多吃了一個。第二天接著吃了剩下的桃子中的一半，仍不過癮，又多吃了一個。以后每天都是吃前一天剩下的桃子的一半零一個。到第n天（n>1）早上猴子再去吃桃子時，只剩下一個桃子了。問猴子第一天共摘下了多少個桃子。程序文件名：ex5_6.c。輸入測試數(shù)據(jù)：10程序運行結(jié)果：1534【參考源程序】#include"stdio.h"voidmain(){intday,sum;scanf("%d",&day);sum=1;do{sum=2*sum+2;day--;}while(day>1);printf("%d",sum);}小結(jié)：1.假設(shè)第1天有sum個桃子，根據(jù)題意可知第2天應(yīng)有桃子sum/2-1。將問題倒過來考慮，若第n天有sum個桃子，則第n-1天就應(yīng)該有2*sum+2個桃子。所以可以看成簡單的迭代，將天數(shù)看成迭代次數(shù)。2.注意最后一天是不算的?！?.7】編程實現(xiàn)，驗證谷角猜想。日本數(shù)學(xué)家谷角靜夫在研究自然數(shù)時發(fā)現(xiàn)了一個奇怪現(xiàn)象：對于任意一個自然數(shù)n，若n為偶數(shù)，則將其除以2；若n為奇數(shù)，則將其乘以3，然后再加1。如此經(jīng)過有限次運算后，總可以得到自然數(shù)1。人們把谷角靜夫的這一發(fā)現(xiàn)叫做“谷角猜想”。程序文件名：ex5_7.c。輸入測試數(shù)據(jù)：26程序運行結(jié)果：134020105168421#include<stdio.h>voidmain(){intn;scanf("%d",&n);while(n!=1){if(n%2==0)n=n/2;elsen=n*3+1;printf("%5d",n);}}小結(jié)：1.定義迭代變量為n，從鍵盤輸入任意驗證整數(shù)為初值。2.按照谷角的猜想，得到迭代關(guān)系式：當n為偶數(shù)時，n=n/2；當n為奇數(shù)時，n=n*3+1。3.當n=1時，迭代終止。由問題可知，對任意給定的一個自然數(shù)n，只要經(jīng)過有限次運算后，能夠得到自然數(shù)1，就已經(jīng)完成了驗證工作。5.4應(yīng)用與提高【5.8】編程實現(xiàn)，求的值。程序文件名：ex5_8.c。提示：利用定積分的幾何意義求定積分。定積分的幾何意義：曲線，直線y=0、x=4和x=5所圍成的曲邊梯形的面積。算法思想：將積分區(qū)間n等分后，若將陰影部分看成矩形，則n個矩形的面積之和就為定積分的值，此算法稱為矩形法求定積分。若將陰影部分看成梯形，則n個梯形的面積之和就為定積分的值，此算法稱為梯形法求定積分。如圖5.3所示。圖5.3定積分的幾何意義用矩形法求定積分的表達式可描述為：第一次運行程序輸入測試數(shù)據(jù)：1000045程序運行結(jié)果：128.412767第二次運行程序輸入測試數(shù)據(jù)：10000045程序運行結(jié)果：128.416277第三次運行程序輸入測試數(shù)據(jù)：10000045程序運行結(jié)果：128.416628【參考源程序】#include<stdio.h>voidmain(){intn,i;doublea,b,x,h,f,sum=0;printf("inputn:");scanf("%d",&n);/*區(qū)間個數(shù)*/printf("inputa&b");scanf("%lf%lf",&a,&b);/*積分上下限*/h=(b-a)/n;/*矩形寬度*/for(i=0;i<n;i++){x=a+i*h;f=x*x*x+2*x*x-x;/*矩形高度*/sum=sum+f*h;}printf("%lf\n",sum);}小結(jié)：從運行結(jié)果可以看出，積分區(qū)間n等分值越大，越能夠接近正確結(jié)果。利用梯形法求定積分。#include<stdio.h>voidmain(){longn,i;doublea,b,x,h,f,fh,sum=0;printf("inputn:");scanf("%ld",&n);/*區(qū)間個數(shù)*/printf("inputa&b");scanf("%lf%lf",&a,&b);/*積分上下限*/h=(b-a)/n;/*梯形高度*/f=a*a*a+2*a*a-a;for(i=1;i<=n;i++){x=a+i*h; fh=x*x*x+2*x*x-x;sum=sum+(f+fh)*h/2;f=fh;}printf("%lf\n",sum);}輸入測試數(shù)據(jù)：10000045程序運行結(jié)果：128.416667從程序運行結(jié)果可以看出，梯形法比矩形法求定積分更逼近結(jié)果?！?.9】程序填空題。求兩個正整數(shù)的最大公約數(shù)和最小公倍數(shù)。請?zhí)羁眨羁諘r不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_9.c。#include<stdio.h>voidmain(){intnm,r,a,b,t;printf("pleaseinputtwonumbers:\n");scanf("%d,%d",&a,&b);nm=a*b;if(a<b){t=a;a=b;b=t;}while(______【1】______){a=b;____【2】_____;}nm=nm/b;printf("最大公約數(shù):%d\n",b);printf("最小公倍數(shù):%d\n",____【3】_____);}輸入測試數(shù)據(jù)：24,8程序運行結(jié)果：最大公約數(shù):8最小公倍數(shù):24參考答案：【1】(r=a%b)!=0或r=a%b由輾轉(zhuǎn)相除求最大公約數(shù)算法可知，余數(shù)不為零是循環(huán)繼續(xù)的條件?！?】b=r在循環(huán)體內(nèi)，需將a=b;b=r;從而施行輾轉(zhuǎn)相除的算法。【3】nm因兩正整數(shù)的最小公倍數(shù)等于兩數(shù)的乘積除以最大公約數(shù)，程序中有語句nm=m*n;為兩數(shù)乘積，還有語句nm=nm/b(此時b已經(jīng)是最大公約數(shù))，所以，此時nm就是最小公倍數(shù)。【5.10】程序填空題。用二分法求方程x2＝2在區(qū)間[1．4，1．5]的正實根的近似解(精確度0.00001)。請?zhí)羁眨羁諘r不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_10.c。#include<stdio.h>#include<math.h>voidmain(){doublex1,x2,x,f1,f2,f;do{printf("Enterx1,x2:\n");scanf("%lf,%lf",&x1,&x2);f1=x1*x1-2;f2=x2*x2-2;}while(f1*f2>0);while(_____【1】_______){x=(x1+x2)/2;______【2】______;if(f*f2<0) { ___【3】____;f1=f; } else{ ____【4】____;f2=f; }}printf("root=%lf\n",x);}輸入測試數(shù)據(jù)：1.4,1.5程序運行結(jié)果：root=1.414215參考答案：fabs(x1-x2)>=1e-5由于精度問題，判斷兩實數(shù)是否相等，不能采用x1==x2或x1-x2==0的形式。而是采用fabs(x1-x2)<=10-5的形式，其含義是當兩個實數(shù)的差逼近一個較小的精度值時，視這兩個實數(shù)近似相等。在本題中，采用二分法直到分的區(qū)間足夠小為止，否則繼續(xù)，所以填寫fabs(x1-x2)>=1e-5。f=x*x-2由前條語句可知，x為x1,x2的中點，此時計算出中點x所對應(yīng)的函數(shù)值f。x1=x在f*f2<0時，也就是f和f2異號時，說明在x和x2之間有方程的根，所以將x1=x，實現(xiàn)[x1,x2]區(qū)間的縮小。x2=x在f*f2>=0時，也就是f和f2同號時，說明在x和x2之間沒有方程的根，那么方程的根就是在[x1,x]之間，所以將x2=x，實現(xiàn)[x1,x2]區(qū)間的縮小。5.5實驗思考【思考1】對于題目【5.1】，我們是利用了輾轉(zhuǎn)相除法求兩個任意正整數(shù)的最大公約數(shù)，除此之外，還是其它方法。如輾轉(zhuǎn)相減法，也稱為尼考曼徹斯法，求任意兩個正整數(shù)的最大公約數(shù)。其方法是不斷用較大的數(shù)減較小數(shù)，直到差為零，此時被減數(shù)或減數(shù)就為兩正整數(shù)的最大公約數(shù)。用輾轉(zhuǎn)相減法編程，求任意兩正整數(shù)的最大公約數(shù)。輸入測試數(shù)據(jù)：24,8程序運行結(jié)果：最大公約數(shù):8最小公倍數(shù):24【參考源程序】#include<stdio.h>voidmain(){intnm,r,n,m,t;printf("pleaseinputtwonumbers:\n");scanf("%d,%d",&m,&n);nm=n*m;if(m<n){t=n;n=m;m=t;}r=m-n;/*r用來表示兩數(shù)的差*/while(r!=0){if(n>r){m=n;n=r;}/*為了保證m總是最大的，需要判斷*/elsem=r; r=m-n;}