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

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

2、算機執(zhí)行，而得到結(jié)果。算法可分為兩類：1. 數(shù)值運算算法。對問題求數(shù)值解，通過運算得出一個具體值，如求方程的根等，此類算法一般有現(xiàn)成的模型，算法較成熟。2. 非數(shù)值運算算法。如用于事務(wù)管理領(lǐng)域，圖書檢索等。根據(jù)實際問題設(shè)計算法時，還要盡量考慮用重復(fù)的步驟去實現(xiàn)，使算法簡明扼要，通用性強，不僅能減少編寫程序的時間，減少上機輸入和調(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é)果。【5.1】編程實現(xiàn)，求兩個正整數(shù)的最大公約數(shù)和最小公倍數(shù)。程序文件名ex5_1.c。 分析：利用歐幾里德輾轉(zhuǎn)相除法求最大公約數(shù)。算法思想，假定兩個整數(shù)m,n（mn），用較小的數(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的最大公約數(shù)。

4、求最大公約數(shù)的算法描述。 假定兩正整數(shù)為m，n，使得mn，余數(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 void main() int nm,r,n,m,t; printf(please input two numbers:n); scanf(%d,%d,&m,&n); nm=n*m; if(mn) t=n; n=m; m=t; r=m%n; while (r!=0)

5、 m=n; n=r;r=m%n; printf(最大公約數(shù):%dn,n); printf(最小公倍數(shù):%dn,nm/n);輸入測試數(shù)據(jù)：24,8程序運行結(jié)果：最大公約數(shù):8 最小公倍數(shù):24小結(jié)：1. 求最大公約數(shù)和最小公倍數(shù)通常要求在自然數(shù)中求解。如何控制輸入負數(shù)時，要求重新輸入數(shù)。算法思想，先輸入任意整數(shù)，然后判斷其數(shù)是否符合要求，若符合正常求解，若不符合，重新輸入整數(shù)。因此先輸入再判斷，可采用do-while循環(huán)語句實現(xiàn)。實現(xiàn)語句如下。 do printf(input m & n); scanf(%d%d,&m,&n);while(m=0|n=0);該循環(huán)條件是若m和n至少有一個為負或為

6、0時，重新輸入兩整數(shù)。 2. 當(dāng)if語句的判斷省略時，程序調(diào)試也是正確的。【5.2】編程實現(xiàn)，用迭代法求。求平方根的迭代公式為：要求前后兩次求出的x的差的絕對值小于10-5。程序文件名ex5_2.c。迭代算法是用計算機解決問題的一種基本方法。迭代法是一種不斷用變量的舊值遞推新值的過程。利用迭代算法解決問題，需考慮以下三個方面的問題。1確定迭代變量。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量稱為迭代變量。通常情況下，設(shè)定兩個迭代變量一個是迭代舊值，另一個是迭代新值，并且要給定開始迭代的初值。2建立迭代公式。有的問題的迭代公式是給出的，如求非線性方程

7、的根常用的牛頓迭代公式。有的問題需要遞推或倒推的方法來建立迭代公式。3確定迭代終止條件。即在什么時候結(jié)束迭代過程？迭代過程的控制通?？煞譃閮煞N情況：一種是規(guī)定了迭代次數(shù)。另一種是迭代次數(shù)無法確定，分析得出結(jié)束迭代過程的條件。分析：根據(jù)題意，迭代公式已給定。設(shè)定兩個迭代變量x，x0，給定初值，利用迭代公式不斷計算下一個x, 直到x與x0的差的絕對值小于10-5為止。采用循環(huán)語句實現(xiàn)迭代，而此時不能確定循環(huán)次數(shù)，只給出迭代終止的條件，所以首選while循環(huán)語句或do-while循環(huán)語句來實現(xiàn)。用迭代法求平方根的算法描述：S1：設(shè)定迭代變量x0（舊值）的初值（一般是可設(shè)置為a/2，當(dāng)然也可以設(shè)置另外

8、的值）；S2：用迭代公式求出下一個x（新值）的值；S3：判斷x-x0的絕對值是否小于等于10-5，如條件不成立，就說明x1和x0相差較大，迭代還必須進行下去。所以，程序轉(zhuǎn)到S4繼續(xù)執(zhí)行；如條件成立，我們就認為x1和x0近似相等了，沒有必要再算下去了，退出循環(huán)體，執(zhí)行S6。S4：x0x。S5：將x0代入迭代公式，求出下一個x的值。返回S3。S6：輸出x的值。因為迭代變量x與x0的誤差很小，所以也可以輸出x0。#include #include void main() double x0,x; float a; printf(Please input a positive number:n); s

9、canf(%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);輸入測試數(shù)據(jù)：3程序運行結(jié)果：The square root of 3.00 is 1.732051小結(jié)：1. 以上程序，只能輸入正數(shù)，如果不小心輸入了負數(shù)，程序本身沒有容錯設(shè)置，就會出錯了。由此可以在該程序中增加一個循環(huán)程序段，用來判斷輸入的數(shù)是否正確。修改上述程序，實現(xiàn)程序的容錯設(shè)置。#include #include int main()

10、double x0,x; float a; printf(Please input a positive number:n); scanf(%f,&a); while(a0,a0,a0: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. 由于精度問題，實數(shù)在計算機中實際表示時存在誤差。因此，在程序設(shè)計中，判斷兩實數(shù)是否相等，不能

11、采用x=x0或x-x0=0的形式。而是采用fabs(x-x0)=10-5的形式，其含義是當(dāng)兩個實數(shù)的差逼近一個較小的精度值時，視這兩個實數(shù)近似相等。3. 迭代初值的給定可以是任意的，但初值的選取會直接影響到迭代的次數(shù)，有時也會影響迭代的收斂性。通常選取迭代初值時，估計一個與解接近的值?！?.3】編程實現(xiàn)，用牛頓迭代法求方程，在2附近的根。程序文件名ex5_3.c。牛頓迭代法（Newtons method），又稱為牛頓切線法，是牛頓在17世紀提出的一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法，是求非線性方程根的重要方法之一。圖5.1 牛頓迭代法求根設(shè)f(x)=0是非線性方程，f(x)在某一區(qū)間內(nèi)為單

12、調(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*為止。由此得到牛頓迭代公式，牛頓迭代法求非線性方程的根的

13、基本算法：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：先任意確定一個與真實的根接近的初始值x；S2：將x1作為舊值，x1=x；S3：求x1的函數(shù)值f1與在這點的導(dǎo)數(shù)值f2；S4：由牛頓迭代公式求新x；S5：判斷前后兩值是否小于給定的一個值精度，若是轉(zhuǎn)到S6，否則返回S2；S6：輸出x為方程的近似根。#include #include void main() d

14、ouble 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);程序運行結(jié)果：The root is 3.00【5.4】編程實現(xiàn)，用二分法求方程2x3-4x2+3x-6=0在（-10,10）之間的根。程序文件名ex5_4.c。二分法，也稱為對分法。是求非線性方程f(x)=0在區(qū)間a,b的實根的一種簡單高效的求解方法。二分法求方程的根是將給定的區(qū)間一分為二為兩個區(qū)間，確定存

15、在根的區(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)無根，返回S1。否則繼續(xù)S4；S4計算x1，x2的中點，x=（x1+ x2）/2；S5計算中點的函數(shù)值f；S6判斷根存在的區(qū)間。若f*f10，則根存在于區(qū)間x,x2，更改存在根的區(qū)間，即，x1=x，f1=f。否則根存在于區(qū)間x1,x，更改存在根的區(qū)間，即，x2=x

16、，f2=f。S7判斷|x1-x2|10-5 或|f(x0)| 10-5。若成立執(zhí)行S8，否則返回S4；S8輸出方程的近似根x的值。#include #include 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*f20); do x=(x1+x2)/2; f=2*x*x*x-4*x*x+3*x-6; if(f*f1=1e-5);

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

18、一個新的x1；（4）若x0-x1的絕對值小于0.000001，執(zhí)行步驟（5），否則執(zhí)行步驟（2）；（5）所求x1就是方程cos(x)-x=0的一個實根，作為函數(shù)值返回?！?.6】編程實現(xiàn)，有一只猴子第一天摘下了若干個桃子，當(dāng)即吃掉一半，還覺得不過癮，又多吃了一個。第二天接著吃了剩下的桃子中的一半，仍不過癮，又多吃了一個。以后每天都是吃前一天剩下的桃子的一半零一個。到第n天（n1）早上猴子再去吃桃子時，只剩下一個桃子了。問猴子第一天共摘下了多少個桃子。程序文件名：ex5_6.c。輸入測試數(shù)據(jù)：10程序運行結(jié)果：1534【參考源程序】#include stdio.hvoid main() int

19、day,sum; scanf(%d,&day); sum=1; do sum=2*sum+2; day-; while(day1); 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 。如

20、此經(jīng)過有限次運算后，總可以得到自然數(shù) 1 。人們把谷角靜夫的這一發(fā)現(xiàn)叫做“谷角猜想”。程序文件名：ex5_7.c。輸入測試數(shù)據(jù)：26程序運行結(jié)果：13 40 20 10 5 16 8 4 2 1#include 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 ，從鍵盤輸入任意驗證整數(shù)為初值。2. 按照谷角的猜想，得到迭代關(guān)系式：當(dāng)n為偶數(shù)時，n=n/2 ；當(dāng)n為奇數(shù)時，n=n*3+1。3. 當(dāng)n=1時，迭代終止。由問題可知，對任意

21、給定的一個自然數(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ù)：10000 4 5程序運行結(jié)

22、果：128.412767第二次運行程序輸入測試數(shù)據(jù)：100000 4 5程序運行結(jié)果：128.416277第三次運行程序輸入測試數(shù)據(jù)：100000 4 5程序運行結(jié)果：128.416628【參考源程序】#include 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)/n; /* 矩形寬度 */ for(i=0;in;i+) x=a+i*h; f=

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

24、 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程序運行結(jié)果：128.416667從程序運行結(jié)果可以看出，梯形法比矩形法求定積分更逼近結(jié)果。【5.9】程序填空題。求兩個正整數(shù)的最大公約數(shù)和最小公倍數(shù)。請?zhí)羁?，填空時不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_9.c。#include void main() int nm,r,a,b,t; printf(please input two number

25、s:n); scanf(%d,%d,&a,&b); nm=a*b; if(ab) t=a; a=b; b=t; while (_【1】_) a=b; _【2】_; nm=nm/b; printf(最大公約數(shù):%dn,b); printf(最小公倍數(shù):%dn,_【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ù)的條件。 【2】b=r 在循環(huán)體內(nèi)，需將a=b;b=r;從而施行輾轉(zhuǎn)相除的算法。 【3】nm 因兩正整數(shù)的最小公倍數(shù)等于兩數(shù)的乘積除以最大公約數(shù)，程序中有

26、語句nm=m*n;為兩數(shù)乘積，還有語句nm=nm/b(此時b已經(jīng)是最大公約數(shù))，所以，此時nm就是最小公倍數(shù)。【5.10】程序填空題。用二分法求方程x22在區(qū)間14，15的正實根的近似解(精確度0.00001)。請?zhí)羁眨羁諘r不得增行或刪行，也不得更改程序的結(jié)構(gòu)，一條橫線上只能填寫一條語句！程序文件名ex5_10.c。#include #include 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*f20); while(_【1】_) x=(x1+x2)/2; _【2】_; if(f*f2=1e-5 由于精度問題，判斷兩實數(shù)是否相等，不能采用x1=x2或x1-x2=0的形式。而是采用fabs(x1-x2)=1e-5。【2】 f=x*x-2 由前條語句可知，x為x1,x2的中點，此時計算出中點x所對應(yīng)的函數(shù)值f。 【3】 x1=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ù)，除此之外，還