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

1、實(shí)驗(yàn)五 程序設(shè)計常用算法5.1實(shí)驗(yàn)要求與目的1熟悉和掌握算法以及算法的特性2熟練掌握結(jié)構(gòu)化程序設(shè)計的三種基本結(jié)構(gòu)3. 掌握常用的數(shù)值算法（求最大公約數(shù)，迭代法、牛頓迭代法和二分法等）4. 培養(yǎng)解決實(shí)際問題的能力5.2實(shí)驗(yàn)指導(dǎo)算法（Algorithm）是計算機(jī)解題的基本思想方法和步驟，算法被稱為程序設(shè)計的靈魂，也是學(xué)習(xí)編程的必備知識 。學(xué)習(xí)和掌握算法，必須要十分清楚，輸入什么數(shù)據(jù)，輸出什么結(jié)果，采用什么結(jié)構(gòu)以及如何合理安排語句等。通常使用自然語言、結(jié)構(gòu)化流程圖、偽代碼等來描述算法。利用計算機(jī)解決問題，首先要設(shè)計出適合計算機(jī)執(zhí)行的算法，此算法包含的步驟必須是有限的，每一步都必須是明確的，最終能被計

2、算機(jī)執(zhí)行，而得到結(jié)果。算法可分為兩類：1. 數(shù)值運(yùn)算算法。對問題求數(shù)值解，通過運(yùn)算得出一個具體值，如求方程的根等，此類算法一般有現(xiàn)成的模型，算法較成熟。2. 非數(shù)值運(yùn)算算法。如用于事務(wù)管理領(lǐng)域，圖書檢索等。根據(jù)實(shí)際問題設(shè)計算法時，還要盡量考慮用重復(fù)的步驟去實(shí)現(xiàn)，使算法簡明扼要，通用性強(qiáng)，不僅能減少編寫程序的時間，減少上機(jī)輸入和調(diào)試程序的時間，還能減少程序本身所占用的內(nèi)存空間。算法應(yīng)具有以下的特性：1.有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。 2.確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不能具有二義性。3.有零個或多個輸入：通常，處理的數(shù)據(jù)對象需要從外界通過輸入來獲得數(shù)據(jù)。4.有一個

3、或多個輸出：算法的目的就是得到結(jié)果，將其結(jié)果輸出。沒有輸出的算法是無意義的。5.有效性：算法中每一個步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果?！?.1】編程實(shí)現(xiàn)，求兩個正整數(shù)的最大公約數(shù)和最小公倍數(shù)。程序文件名ex5_1.c。 分析：利用歐幾里德輾轉(zhuǎn)相除法求最大公約數(shù)。算法思想，假定兩個整數(shù)m,n（m>n），用較小的數(shù)n（除數(shù)）除較大的數(shù)m（被除數(shù)），得到余數(shù)r1；若余數(shù)r1不為零，則除數(shù)作為被除數(shù)，余數(shù)r1作為除數(shù)，相除得到余數(shù)r2；若余數(shù)r2還不為零，仍是將除數(shù)作為被除數(shù)，余數(shù)r2作為除數(shù)，相除得到余數(shù)r3，這樣輾轉(zhuǎn)相除，直到余數(shù)是零為止。當(dāng)余數(shù)為零時的除數(shù)，稱為原正整數(shù)m,n的最大公

4、約數(shù)。 求最大公約數(shù)的算法描述。 假定兩正整數(shù)為m，n，使得m>n，余數(shù)為r。 S1：求兩數(shù)的余數(shù)r。r=m%n； S2：判斷余數(shù)r是否為0，若為0，執(zhí)行S5,否則執(zhí)行S3；S3：mn，nr；S4：求兩數(shù)的余數(shù)r。r=m%n；返回S2；S5：輸出最大公約數(shù)n。最小公倍數(shù)利用公式求得。即，最小公倍數(shù)=兩個整數(shù)之積/最大公約數(shù)。#include <stdio.h>void main() int nm,r,n,m,t; printf("please input two numbers:n"); scanf("%d,%d",&m,&am

5、p;n); nm=n*m; if(m<n) t=n; n=m; m=t; r=m%n; while (r!=0) m=n; n=r;r=m%n; printf("最大公約數(shù):%dn",n); printf("最小公倍數(shù):%dn",nm/n);輸入測試數(shù)據(jù)：24,8程序運(yùn)行結(jié)果：最大公約數(shù):8 最小公倍數(shù):24小結(jié)：1. 求最大公約數(shù)和最小公倍數(shù)通常要求在自然數(shù)中求解。如何控制輸入負(fù)數(shù)時，要求重新輸入數(shù)。算法思想，先輸入任意整數(shù)，然后判斷其數(shù)是否符合要求，若符合正常求解，若不符合，重新輸入整數(shù)。因此先輸入再判斷，可采用do-while循環(huán)語句實(shí)現(xiàn)。實(shí)

6、現(xiàn)語句如下。 do printf("input m & n"); scanf("%d%d",&m,&n);while(m<=0|n<=0);該循環(huán)條件是若m和n至少有一個為負(fù)或?yàn)?時，重新輸入兩整數(shù)。 2. 當(dāng)if語句的判斷省略時，程序調(diào)試也是正確的。【5.2】編程實(shí)現(xiàn)，用迭代法求。求平方根的迭代公式為：要求前后兩次求出的x的差的絕對值小于10-5。程序文件名ex5_2.c。迭代算法是用計算機(jī)解決問題的一種基本方法。迭代法是一種不斷用變量的舊值遞推新值的過程。利用迭代算法解決問題，需考慮以下三個方面的問題。1確定迭代變

7、量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量稱為迭代變量。通常情況下，設(shè)定兩個迭代變量一個是迭代舊值，另一個是迭代新值，并且要給定開始迭代的初值。2建立迭代公式。有的問題的迭代公式是給出的，如求非線性方程的根常用的牛頓迭代公式。有的問題需要遞推或倒推的方法來建立迭代公式。3確定迭代終止條件。即在什么時候結(jié)束迭代過程？迭代過程的控制通常可分為兩種情況：一種是規(guī)定了迭代次數(shù)。另一種是迭代次數(shù)無法確定，分析得出結(jié)束迭代過程的條件。分析：根據(jù)題意，迭代公式已給定。設(shè)定兩個迭代變量x，x0，給定初值，利用迭代公式不斷計算下一個x, 直到x與x0的差的絕對

8、值小于10-5為止。采用循環(huán)語句實(shí)現(xiàn)迭代，而此時不能確定循環(huán)次數(shù)，只給出迭代終止的條件，所以首選while循環(huán)語句或do-while循環(huán)語句來實(shí)現(xiàn)。用迭代法求平方根的算法描述：S1：設(shè)定迭代變量x0（舊值）的初值（一般是可設(shè)置為a/2，當(dāng)然也可以設(shè)置另外的值）；S2：用迭代公式求出下一個x（新值）的值；S3：判斷x-x0的絕對值是否小于等于10-5，如條件不成立，就說明x1和x0相差較大，迭代還必須進(jìn)行下去。所以，程序轉(zhuǎn)到S4繼續(xù)執(zhí)行；如條件成立，我們就認(rèn)為x1和x0近似相等了，沒有必要再算下去了，退出循環(huán)體，執(zhí)行S6。S4：x0x。S5：將x0代入迭代公式，求出下一個x的值。返回S3。S6：

9、輸出x的值。因?yàn)榈兞縳與x0的誤差很小，所以也可以輸出x0。#include <stdio.h>#include <math.h> void main() double x0,x; float a; printf("Please input a positive number:n"); scanf("%f",&a); x0=a/2; x=(x0+a/x0)/2; while(fabs(x0-x)>=1e-5) x0=x; x=(x0+a/x0)/2; printf("The square root of

10、 %6.2f is %lf n",a,x);輸入測試數(shù)據(jù)：3程序運(yùn)行結(jié)果：The square root of 3.00 is 1.732051小結(jié)：1. 以上程序，只能輸入正數(shù)，如果不小心輸入了負(fù)數(shù)，程序本身沒有容錯設(shè)置，就會出錯了。由此可以在該程序中增加一個循環(huán)程序段，用來判斷輸入的數(shù)是否正確。修改上述程序，實(shí)現(xiàn)程序的容錯設(shè)置。#include <stdio.h>#include <math.h> int main() double x0,x; float a; printf("Please input a positive number:n&q

11、uot;); scanf("%f",&a); while(a<0) /*判斷輸入是否有錯誤*/ printf("a>0,a>0,a>0:n"); /*該提示信息提示要求輸入的數(shù)必須是大于0的數(shù)*/ scanf("%f",&a); x0=a/2; x=(x0+a/x0)/2; while(fabs(x0-x)>=1e-5) x0=x; x=(x0+a/x0)/2; printf("The square root of %6.2f is %lf n",a,x); 2. 由于

12、精度問題，實(shí)數(shù)在計算機(jī)中實(shí)際表示時存在誤差。因此，在程序設(shè)計中，判斷兩實(shí)數(shù)是否相等，不能采用x=x0或x-x0=0的形式。而是采用fabs(x-x0)<=10-5的形式，其含義是當(dāng)兩個實(shí)數(shù)的差逼近一個較小的精度值時，視這兩個實(shí)數(shù)近似相等。3. 迭代初值的給定可以是任意的，但初值的選取會直接影響到迭代的次數(shù)，有時也會影響迭代的收斂性。通常選取迭代初值時，估計一個與解接近的值?！?.3】編程實(shí)現(xiàn)，用牛頓迭代法求方程，在2附近的根。程序文件名ex5_3.c。牛頓迭代法（Newton's method），又稱為牛頓切線法，是牛頓在17世紀(jì)提出的一種在實(shí)數(shù)域和復(fù)數(shù)域上近似求解方程的方法，是

13、求非線性方程根的重要方法之一。圖5.1 牛頓迭代法求根設(shè)f(x)=0是非線性方程，f(x)在某一區(qū)間內(nèi)為單調(diào)函數(shù)，則方程f(x)=0在某一區(qū)間只有一個實(shí)根。牛頓迭代法的幾何意義，如圖5.1所示，f(x)=0的解就是y=f(x)與x軸的交點(diǎn)的橫坐標(biāo)，也就是給定一個初值x1，不斷通過切線方程的迭代求解而逼近解x*的過程。先設(shè)定一個與真實(shí)根接近的x1作為第一個近似根，過點(diǎn)（x1,f(x1)）作f(x)的切線，與x軸相交于x2，這時，我們把x2作為第二個近似根；即，過點(diǎn)（x2,f(x2)）作f(x)的切線，與x軸相交于x3，這時，我們把x2作為第三個近似根；即，過點(diǎn)（x3,f(x3)）作f(x)的切線

14、，與x軸相交于x4，依次類推，直到接近真正的根x*為止。由此得到牛頓迭代公式，牛頓迭代法求非線性方程的根的基本算法：1. 確定迭代變量，舊值：x1 ； 新值 x ；以及相對應(yīng)的函數(shù)值變量f1，即代表f(x1)；導(dǎo)數(shù)值變量f2，即代表f(x1)。 2. 牛頓迭代公式：x=x1-f1/f23. 確定迭代終止條件，當(dāng)fabs(x-x0)<1e-5時，迭代終止。牛頓迭代法求非線性方程的根的算法描述：S1：先任意確定一個與真實(shí)的根接近的初始值x；S2：將x1作為舊值，x1=x；S3：求x1的函數(shù)值f1與在這點(diǎn)的導(dǎo)數(shù)值f2；S4：由牛頓迭代公式求新x；S5：判斷前后兩值是否小于給定的一個值精度，若是

15、轉(zhuǎn)到S6，否則返回S2；S6：輸出x為方程的近似根。#include <stdio.h>#include <math.h>void main() double x,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("The root is%6.2lfn",x);程序運(yùn)行結(jié)果：The root is 3.00【5.4】編程實(shí)現(xiàn)，用二分法求方程2x3-4x2+3x-6=

16、0在（-10,10）之間的根。程序文件名ex5_4.c。二分法，也稱為對分法。是求非線性方程f(x)=0在區(qū)間a,b的實(shí)根的一種簡單高效的求解方法。二分法求方程的根是將給定的區(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í)根。 設(shè)定f(x)= 2x3-4

17、x2+3x-6，區(qū)間為x1,x2，區(qū)間端點(diǎn)的函數(shù)值變量為f1和f2。中點(diǎn)變量為x,對應(yīng)的函數(shù)值變量為f。如圖5.2所示。圖5.2二分法求根二分法求非線性方程的根的算法描述：S1輸入x1和x2的區(qū)間值；S2。求區(qū)間端點(diǎn)的函數(shù)值f1和f2；S3確定在該區(qū)間內(nèi)函數(shù)有根。若f1*f2>0，在該區(qū)間內(nèi)無根，返回S1。否則繼續(xù)S4；S4計算x1，x2的中點(diǎn)，x=（x1+ x2）/2；S5計算中點(diǎn)的函數(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-x

18、2|<10-5 或|f(x0)|< 10-5。若成立執(zhí)行S8，否則返回S4；S8輸出方程的近似根x的值。#include <stdio.h>#include <math.h>void main( ) double x1,x2,x,f1,f2,f; do printf("Enter x1,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>

19、;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.3fn",x);5.3實(shí)驗(yàn)內(nèi)容【5.5】編寫實(shí)現(xiàn)，程序功能是，利用簡單迭代公式，求方程：cos(x)-x=0的一個實(shí)根。程序文件名：ex5_5.c。程序運(yùn)行結(jié)果：Root =0.739086【參考源程序】#include <math.h>#include <stdio.h>void main

20、() double x0, x1=0.0; do x0=x1; x1=cos(x0); while(fabs(x0-x1)>0.000001); printf("Root =%lfn", 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í)根，作為函數(shù)值返回?！?.6】編程實(shí)現(xiàn)，有一只猴子第一天摘下了若干個桃子，當(dāng)即吃掉一半，還覺得不過癮，又多吃了一

21、個。第二天接著吃了剩下的桃子中的一半，仍不過癮，又多吃了一個。以后每天都是吃前一天剩下的桃子的一半零一個。到第n天（n>1）早上猴子再去吃桃子時，只剩下一個桃子了。問猴子第一天共摘下了多少個桃子。程序文件名：ex5_6.c。輸入測試數(shù)據(jù)：10程序運(yùn)行結(jié)果：1534【參考源程序】#include "stdio.h"void main() int day,sum; scanf("%d",&day); sum=1; do sum=2*sum+2; day-; while(day>1); printf("%d",sum);

22、小結(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】編程實(shí)現(xiàn)，驗(yàn)證谷角猜想。日本數(shù)學(xué)家谷角靜夫在研究自然數(shù)時發(fā)現(xiàn)了一個奇怪現(xiàn)象：對于任意一個自然數(shù) n ，若 n 為偶數(shù)，則將其除以 2 ；若 n 為奇數(shù)，則將其乘以 3 ，然后再加 1 。如此經(jīng)過有限次運(yùn)算后，總可以得到自然數(shù) 1 。人們把谷角靜夫的這一發(fā)現(xiàn)叫做“谷角猜想”。程序文件名：ex5_7.c。輸入測試數(shù)據(jù)：26程序運(yùn)行結(jié)果：13 40 20

23、10 5 16 8 4 2 1#include <stdio.h>void main() int n; scanf("%d",&n); while(n!=1) if(n%2=0) n=n/2; else n=n*3+1; printf("%5d",n); 小結(jié)：1. 定義迭代變量為 n ，從鍵盤輸入任意驗(yàn)證整數(shù)為初值。2. 按照谷角的猜想，得到迭代關(guān)系式：當(dāng)n為偶數(shù)時，n=n/2 ；當(dāng)n為奇數(shù)時，n=n*3+1。3. 當(dāng)n=1時，迭代終止。由問題可知，對任意給定的一個自然數(shù) n ，只要經(jīng)過有限次運(yùn)算后，能夠得到自然數(shù)1，就已經(jīng)完成了驗(yàn)

24、證工作。5.4應(yīng)用與提高【5.8】編程實(shí)現(xiàn)，求 的值。程序文件名：ex5_8.c。提示：利用定積分的幾何意義求定積分。定積分的幾何意義：曲線，直線y=0、x=4和x=5所圍成的曲邊梯形的面積。算法思想：將積分區(qū)間n等分后，若將陰影部分看成矩形，則n個矩形的面積之和就為定積分的值，此算法稱為矩形法求定積分。若將陰影部分看成梯形，則n個梯形的面積之和就為定積分的值，此算法稱為梯形法求定積分。如圖5.3所示。圖5.3 定積分的幾何意義用矩形法求定積分的表達(dá)式可描述為：第一次運(yùn)行程序輸入測試數(shù)據(jù)：10000 4 5程序運(yùn)行結(jié)果：128.412767第二次運(yùn)行程序輸入測試數(shù)據(jù)：100000 4 5程序運(yùn)

25、行結(jié)果：128.416277第三次運(yùn)行程序輸入測試數(shù)據(jù)：100000 4 5程序運(yùn)行結(jié)果：128.416628【參考源程序】#include <stdio.h>void main() int n,i; double a,b,x,h,f,sum=0; printf("input n:"); scanf("%d",&n); /* 區(qū)間個數(shù) */ printf("input a & b"); scanf("%lf%lf",&a,&b); /* 積分上下限 */ h=(b-a)/

26、n; /* 矩形寬度 */ for(i=0;i<n;i+) x=a+i*h; f=x*x*x+2*x*x-x; /* 矩形高度 */ sum=sum+f*h; printf("%lfn",sum);小結(jié)：1. 從運(yùn)行結(jié)果可以看出，積分區(qū)間n等分值越大，越能夠接近正確結(jié)果。2. 利用梯形法求定積分。#include <stdio.h>void main() long n,i; double a,b,x,h,f,fh,sum=0; printf("input n:"); scanf("%ld",&n); /* 區(qū)

27、間個數(shù) */ printf("input a & 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("%lfn",sum);輸入測試數(shù)據(jù)：100000 4 5程序運(yùn)行結(jié)果：128.416667從程序運(yùn)行結(jié)果可以看出，梯形法比矩形法求定積分更逼近結(jié)果

28、。【5.9】程序填空題。求兩個正整數(shù)的最大公約數(shù)和最小公倍數(shù)。請?zhí)羁?，填空時不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_9.c。#include <stdio.h>void main() int nm,r,a,b,t; printf("please input two numbers: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(

29、"最大公約數(shù):%dn",b); printf("最小公倍數(shù):%dn",_【3】_);輸入測試數(shù)據(jù)：24,8程序運(yùn)行結(jié)果：最大公約數(shù):8 最小公倍數(shù):24參考答案：【1】(r=a%b)!=0 或 r=a%b 由輾轉(zhuǎn)相除求最大公約數(shù)算法可知，余數(shù)不為零是循環(huán)繼續(xù)的條件。 【2】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ù)?！?.10】程序填空題。用二分法求方程

30、x22在區(qū)間14，15的正實(shí)根的近似解(精確度0.00001)。請?zhí)羁?，填空時不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_10.c。#include <stdio.h>#include <math.h>void main( ) double x1,x2,x,f1,f2,f; do printf("Enter x1,x2 : n"); scanf("%lf,%lf",&x1,&x2); f1=x1*x1-2; f2=x2*x2-2; while(f1*f2>0); whi

31、le(_【1】_) x=(x1+x2)/2; _【2】_; if(f*f2<0) _【3】_; f1=f; else _【4】_;f2=f; printf("root = %lfn",x);輸入測試數(shù)據(jù)：1.4,1.5程序運(yùn)行結(jié)果：root = 1.414215參考答案：【1】 fabs(x1-x2)>=1e-5 由于精度問題，判斷兩實(shí)數(shù)是否相等，不能采用x1=x2或x1-x2=0的形式。而是采用fabs(x1-x2)<=10-5的形式，其含義是當(dāng)兩個實(shí)數(shù)的差逼近一個較小的精度值時，視這兩個實(shí)數(shù)近似相等。在本題中，采用二分法直到分的區(qū)間足夠小為止，否則繼續(xù)

32、，所以填寫fabs(x1-x2)>=1e-5?！?】 f=x*x-2 由前條語句可知，x為x1,x2的中點(diǎn)，此時計算出中點(diǎn)x所對應(yīng)的函數(shù)值f。 【3】 x1=x 在f*f2<0時，也就是f和f2異號時，說明在x和x2之間有方程的根，所以將x1=x，實(shí)現(xiàn)x1,x2區(qū)間的縮小。【4】 x2=x 在f*f2>=0時，也就是f和f2同號時，說明在x和x2之間沒有方程的根，那么方程的根就是在x1,x之間，所以將x2=x，實(shí)現(xiàn)x1,x2區(qū)間的縮小。5.5實(shí)驗(yàn)思考【思考1】對于題目【5.1】，我們是利用了輾轉(zhuǎn)相除法求兩個任意正整數(shù)的最大公約數(shù)，除此之外，還是其它方法。如輾轉(zhuǎn)相減法，也稱為尼考曼徹斯法