1、會計學1第程序第程序(chngx)的流程設計的流程設計第一頁，共150頁。第1頁/共150頁第二頁，共150頁。第2頁/共150頁第三頁，共150頁。第3頁/共150頁第四頁，共150頁。第4頁/共150頁第五頁，共150頁。第5頁/共150頁第六頁，共150頁。第6頁/共150頁第七頁，共150頁。過程判斷數據預定義過程起止流程線連接注釋圖圖3.2 常用常用(chn yn)的流程的流程圖標準化符號圖標準化符號 第7頁/共150頁第八頁，共150頁。第8頁/共150頁第九頁，共150頁。第9頁/共150頁第十頁，共150頁。S1S2S3PS1S2真假PS2假真（a）順序）順序(shnx)結結構

2、構 （b）選擇）選擇(xunz)結構結構 （c）重復結構）重復結構 圖圖3.3 用流程圖描述的三種流程基本結構用流程圖描述的三種流程基本結構 第10頁/共150頁第十一頁，共150頁。第11頁/共150頁第十二頁，共150頁。a=b輸入a,b,cmax=a真假max=bmax=c真假輸出max輸出c開始結束i=maxmax=n（a）一個）一個(y )三數中取大的算法三數中取大的算法 （b）另一個三數）另一個三數(sn sh)中取大的算法中取大的算法 圖圖3.4 三數中取大算法三數中取大算法(sun f)的流程的流程圖描述圖描述 第12頁/共150頁第十三頁，共150頁。圖圖3.5 無限制地使用

3、流線形成無限制地使用流線形成BS流程流程(lichng)結構結構 結構化程序設計主張限制這種無規律的任意轉向，采用三種基結構化程序設計主張限制這種無規律的任意轉向，采用三種基本結構作為構成本結構作為構成(guchng)程序的基本單位。這樣就必須限程序的基本單位。這樣就必須限制流線的使用。制流線的使用。第13頁/共150頁第十四頁，共150頁。第14頁/共150頁第十五頁，共150頁。S1S2S3PS1S2當PS假真（c）當型重復）當型重復(chngf)結構結構（a）順序）順序(shnx)結結構構 （b）選擇）選擇(xunz)結結構構圖圖3.6 用用N-S圖描述三種基本流程結構圖描述三種基本流程

4、結構 第15頁/共150頁第十六頁，共150頁。a=bmax=amax=b輸入a，b，c假真max=c輸出max輸出c真假當i=maxmax=n真假輸入n初始化：max=0，i=1輸出max（a）采用選擇）采用選擇(xunz)結構結構 （b）采用）采用(ciyng)當型重復結當型重復結構構 圖圖3.7 三數中取大算法的三數中取大算法的N-S圖描述圖描述 第16頁/共150頁第十七頁，共150頁。輸入輸入(shr)a,b,c；if(a=b)max=a;else max=bif(max=c) 輸出輸出max;else 輸出輸出c；第17頁/共150頁第十八頁，共150頁。初始化：初始化：mac=0

5、,i=1;當（當（i=max) max=n;)輸出輸出max;（3）與圖）與圖3.7（c）相對）相對(xingdu)應的三數中取大算法的偽代碼描述：應的三數中取大算法的偽代碼描述：初始化：初始化：mac=0,i=1; (輸入輸入n; i+;if(n=max) max=n;) 直到（直到（i3）輸出輸出max;第18頁/共150頁第十九頁，共150頁。第19頁/共150頁第二十頁，共150頁。s1: 輸入三數輸入三數(sn sh)a,b,c;s2: 從從a,b,c中找出大數賦給中找出大數賦給max;s3: 輸出輸出max。這一階段這一階段(jidun)算法是用漢語描述的，描述了按順序要完成的三個

6、算法是用漢語描述的，描述了按順序要完成的三個“做做什么什么”。可以用。可以用s1,s2,s3代表第代表第1步、第步、第2步、第步、第3步。步。s是步是步(step)的縮寫。的縮寫。 (2) 在前一階段在前一階段(jidun)的基礎上考慮各個的基礎上考慮各個“做什么做什么”的實現途徑，把的實現途徑，把算法細化為：算法細化為：s1: 調用調用scanf()函數；函數；s2: 設計一個函數設計一個函數max3 (a,b,c);s3: 調用調用printf()函數。函數。這一階段是用混合語言寫算法。這一階段是用混合語言寫算法。第20頁/共150頁第二十一頁，共150頁。int main(void) /

7、*三數三數(sn sh)中取大數中取大數*/float a,b,c, max;float max3(float x,float y, float z);printf (Input 3 numbers a b c:);scanf (%f%f%f, &a,&b,&c);max=max3(a,b,c);printf (The max is: %fn, max);return 0;第21頁/共150頁第二十二頁，共150頁。s2.1: 從從x與與y中取大數中取大數(d sh)送送m中；中；s2.2: 從從m與與z中取大數中取大數(d sh)送送m中；中；s2.3: 返回返回m給

8、主調函數。給主調函數。進一步細化得進一步細化得 s2.1:if(xy)m=x;elsem=y;s2.2: if(mz)m=m;elsem=z;s2.3: return (m); 第22頁/共150頁第二十三頁，共150頁。float max 3 (float x, float y, float z)float m;if (xy)m=x;elsem=y;if (mz)m=m;elsem=z;return (m);一次執行一次執行(zhxng)結果：結果：Input 3 numbers a b c: 34.7 45.9 678The max is: 678.000000第23頁/共150頁第二十四

9、頁，共150頁。第24頁/共150頁第二十五頁，共150頁。第25頁/共150頁第二十六頁，共150頁。第26頁/共150頁第二十七頁，共150頁。第27頁/共150頁第二十八頁，共150頁。第28頁/共150頁第二十九頁，共150頁。if (a & b)c=1;elsec=0; 圖圖3.8(b)中中c燈亮的條件是燈亮的條件是a“或或”b之一合上之一合上(二者都合上也行二者都合上也行)，即至，即至少少a或或b之一為之一為“真真”（1）。在）。在C語言中，語言中，“或或”運算用運算用“|”運算符表運算符表示。下面是邏輯示。下面是邏輯“或或”的簡單的簡單(jindn)應用：應用：if (a

10、|b)c=1;else c=0;第29頁/共150頁第三十頁，共150頁。ABBAA（a）邏輯）邏輯(lu j)“與與” （b）邏輯）邏輯(lu j)“或或” （c）邏輯）邏輯(lu j)“非非” 圖圖3.8 三個基本邏輯運算三個基本邏輯運算 第30頁/共150頁第三十一頁，共150頁。if (!a)c=1;elsec=0; &和和|是二元運算符，結合方向是二元運算符，結合方向(fngxing)為自左至右；為自左至右；!為一為一元運算符，元運算符， 結合方向結合方向(fngxing)為自右至左。為自右至左。&和和|的優先級低于關系運算符，而的優先級低于關系運算符，而!的優先級高

11、于關系運算符。的優先級高于關系運算符。例如表達式例如表達式!31，應先計算，應先計算!3，得，得0；再計算；再計算01，得，得0。第31頁/共150頁第三十二頁，共150頁。第32頁/共150頁第三十三頁，共150頁。ab!a!ba|ba&bTTFFTTTFFTFTFTTFFTFFTTFF表表3.1 基本基本(jbn)邏輯運算的真值表邏輯運算的真值表 第33頁/共150頁第三十四頁，共150頁。if (表達式)語句(yj)1else語句(yj)2第34頁/共150頁第三十五頁，共150頁。-x (x0)x (x0)x=/* 文件名：文件名：ex030301.c */* 求絕對值求絕對值

12、 */double abstr (double x)if (x0.0)x=-x;elsex=x;return (x);第35頁/共150頁第三十六頁，共150頁。#include int main(void)double a, abstr (double a);printf (Enter real number a please:);scanf (%1f,&a);printf (abstr(%1f)=%1 fn, a, abstr (a);rerurn 0;運行情況運行情況(qngkung)如下如下 Enter real number a please: -98.7654 abstr

13、(-98.765400)=98.765400第36頁/共150頁第三十七頁，共150頁。double abstr (double x)if (x0.0)x=-x;return (x); 這種結構稱為不平衡這種結構稱為不平衡if結構。它不如平衡的結構。它不如平衡的if結構容易理解結構容易理解(lji)和清晰。下面看一個稍復雜的例子。和清晰。下面看一個稍復雜的例子。if (表達式)語句(yj)第37頁/共150頁第三十八頁，共150頁。/* 文件名：文件名：ex030401.c */* 三數三數(sn sh)取大取大 */float max3 (float x, float y, float z)

14、float max=x;if (zy)if (zx)max=z;elseif (yx)max=y;return (max);然而然而(rn r)，它被，它被main()函數調用時的的一次運行情況如下：函數調用時的的一次運行情況如下： Enter 3 real numbers a,b,c:12.34 5.67 34.56 The max is 12.300000這就因為使用不平衡這就因為使用不平衡if結構時，沒有搞清結構時，沒有搞清ifelse結構的語法規則。結構的語法規則。第38頁/共150頁第三十九頁，共150頁。zxmax=z（空）max = x假真yxmax=y（空）真假zy真假retu

15、rn(max)圖圖3.9 例例3.4的設計者使用的設計者使用(shyng)的算法的算法 第39頁/共150頁第四十頁，共150頁。（空）zxmax=z假真yxmax=y真假max = xzy真假return(max)圖圖3.10 例例3.4程序實際程序實際(shj)使用的算法使用的算法 第40頁/共150頁第四十一頁，共150頁。float max3 (float x, float y, float z) float max=x;if (zy)if (zx)max=z;elseif (yx)max=y;return (max);第41頁/共150頁第四十二頁，共150頁。b=0輸出“無解”輸出

16、單根：x=-c/b假真disc0輸出兩復數根輸出兩實根真假a=0真假 disc=b*b - 4*a*c圖圖3.12 求一元二次方程根的算法求一元二次方程根的算法(sun f)第42頁/共150頁第四十三頁，共150頁。/* 文件名：文件名：ex030501.c */* 求解求解(qi ji)一元二次方程一元二次方程 */include void solv_quadr_equa (float a, float b, float c)if (a=0.0)if (b=0.0)printf (no answer due to input errorn);elseprintf (the single r

17、oot is %fn, -c/b);elsedouble disc, twoa, term1, term2;disc=b*b-4*a*c;twoa=2*a;term1=-b/twoa;term2=sqrt (fabs (disc)/twoa;if (disc0.0printf (complex root:n real part=%f,imag part=%fn, term1, term2);elseprintf (real root:n root1=%f, root2=%fn，term1+term2, term1-term2);第43頁/共150頁第四十四頁，共150頁。第44頁/共150頁第

18、四十五頁，共150頁。if(表達式1) 語句(yj)1else if(表達式2) 語句(yj)2else if(表達式n) 語句(yj)nelse語句(yj)n+1第45頁/共150頁第四十六頁，共150頁。真假表達式1表達式2表達式n語句n+1語句n語句2語句1真真假假圖圖3.13 if-else if結構結構(jigu)的流程圖描述的流程圖描述第46頁/共150頁第四十七頁，共150頁。圖圖3.14 else if結構結構(jigu)的的N-S圖描述圖描述語句1語句2語句3真假表達式1假真表達式2真假表達式3第47頁/共150頁第四十八頁，共150頁。真假score=80score=70等

19、級A真假輸入scorescore=60等級B等級D等級C圖圖3.15 根據根據(gnj)百分制分數決定成績的等級百分制分數決定成績的等級第48頁/共150頁第四十九頁，共150頁。/* 文件名：文件名：ex031701.c */* 按成績按成績(chngj)分等分等 */include int main(void)float score;printf(“Input a scre:”);scanf(“%f”,&score);if (score = 80)printf (%f is An,score);else if (score = 70)printf (%f is Bn,score);

20、else if (score = 60)printf (%f is Cn,score);elseprintf (%f is Dn,score);return 0;第49頁/共150頁第五十頁，共150頁。第50頁/共150頁第五十一頁，共150頁。switch(表達式表達式)case 常量常量(chngling)表達表達式式1:語句序列語句序列1case 常量常量(chngling)表達表達式式2:語句序列語句序列2case 常量常量(chngling)表達表達式式n：語句序列語句序列ndefault:語句序列語句序列n+1第51頁/共150頁第五十二頁，共150頁。表達式語句序列1常量表達式

21、1:語句序列2常量表達式2:語句序列i常量表達式i:語句序列n常量表達式n:語句序列n+1default圖圖3.16 switch3.16 switch控制結構控制結構1 1第52頁/共150頁第五十三頁，共150頁。switch(表達式表達式)case 常量常量(chngling)表達表達式式1:語句序列語句序列1break;case 常量常量(chngling)表達表達式式2:語句序列語句序列2break;case 常量常量(chngling)表達表達式式n：語句序列語句序列nbreak;default:語句序列語句序列n+1break;圖圖3.17 switch3.17 switch控制

22、結構控制結構2 2表達式語句序列1常量表達式1:語句序列2常量表達式2:語句序列i常量表達式i:語句序列n常量表達式n:語句序列n+1defaultbreak;break;break;break;break;第53頁/共150頁第五十四頁，共150頁。/* 文件名：文件名：ex030701.c */* 輸出輸出(shch)月份名稱月份名稱 */void MonthName(int month)(switch (month)case 1: priontf(“Januaryn”);break;case 2: priontf(“Februaryn”);break;case 3: priontf(“M

23、archn”);break;case 4: priontf(“Apriln”);break;case 5: priontf(“Mayn”);break;case 6: priontf(“Junen”);break;case 7: priontf(“Jaulyn”);break;case 8: priontf(“Augustn”);break;case 9: priontf(“Septembern”);break;case 10: priontf(“Octobern”);break;case 11: priontf(“Novembern”);break;case 12: priontf(“Dec

24、embern”);break;default: priontf(“Illegal monthn”);break;return;第54頁/共150頁第五十五頁，共150頁。/* 文件名：文件名：ex030801.c */* 測試測試(csh)字符類型字符類型 */int test_char (int c)switch (c)case 0:case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:printf (its a digit n);break;case ：case n：case t：printf (it s a whit

25、en);break;default:printf (it s a charn);break;第55頁/共150頁第五十六頁，共150頁。第56頁/共150頁第五十七頁，共150頁。case 3+4：但不允許但不允許(ynx)寫為：寫為：int x=3,y=4;switch (z)case x+y:第57頁/共150頁第五十八頁，共150頁。case 3+2: case 8-3: 是不允許的。是不允許的。（4）switch的匹配測試，只能測試是否相等，不能測試關系或邏輯的匹配測試，只能測試是否相等，不能測試關系或邏輯(lu j)。（5）C89要求要求C編譯系統應當實現編譯系統應當實現 一個一個s

26、witch最少可以包含最少可以包含257個個case子結構，而子結構，而C99要求最少支持要求最少支持1023個個case子結構。子結構。（6）switch結構允許嵌套。結構允許嵌套。第58頁/共150頁第五十九頁，共150頁。/* 文件名：文件名：ex030901.c */* 聯想猜詞游戲聯想猜詞游戲 */include stdio.hint main(void)int c;c=getchar(); getchar(); /* 為接收一個為接收一個(y )字符，再字符，再接收一個接收一個(y )分隔符分隔符換行或空格換行或空格*/例例3.9 聯想猜詞游戲聯想猜詞游戲 這個游戲是：游戲者心中想

27、好一個單詞，并先在鍵盤上輸入這個游戲是：游戲者心中想好一個單詞，并先在鍵盤上輸入第第1個字母，然后讓計算機猜所選的是哪個單詞；如果計算機個字母，然后讓計算機猜所選的是哪個單詞；如果計算機顯示出的單詞不只一個，游戲者就要再輸入第顯示出的單詞不只一個，游戲者就要再輸入第2個字母，如此個字母，如此操作，知道計算機猜出這個單詞或得出操作，知道計算機猜出這個單詞或得出“猜不出猜不出”的結果為止的結果為止(wizh)。 下面的程序以猜下面的程序以猜“計算機語言名稱計算機語言名稱”為例。為例。第59頁/共150頁第六十頁，共150頁。switch (c)case a:case A:printf (Ada,

28、Algol?n);c=getchar(); getchar();switch (c)case d:case D:printf (Ada n);break;case l：case L:printf (Algol n);break;default：printf (input errorn);break;break;case b:case B:printf (Basic, BCDL?n);c=getchar(); getchar();switch (c)case a:case A:printf (Basicn)；break;case c:case C:printf (BCDLn);break;def

29、ault:printf (I am sorry!n);break;break；第60頁/共150頁第六十一頁，共150頁。case c:case C:printf (C,Cobol,C+,C#? n);c=getchar(); getchar();switch (c)case c:case C:printf (Cn);break;case o:case O:printf (Coboln);break;case +:printf (C+n);break;case #:printf (C#n);break;default:printf (I am sorry!n);break;break;defa

30、ult:printf (I am sorry!n);break;return 0;這是一個這是一個(y )簡單的簡單的switch嵌套。輸入嵌套。輸入2個個字母后就可找出唯一的單詞。如果單字母后就可找出唯一的單詞。如果單詞量大而且兩個字母還不能區分出單詞量大而且兩個字母還不能區分出單詞時，嵌套層次就要增加，程序也就詞時，嵌套層次就要增加，程序也就復雜了。復雜了。第61頁/共150頁第六十二頁，共150頁。表達式1？表達式2：表達式3它的操作過程為：若表達式的值為真它的操作過程為：若表達式的值為真(非非0)，則以表達式，則以表達式2的值作的值作為該條件為該條件(tiojin)表達式的值；否則取表

31、達式表達式的值；否則取表達式3的值作為該條件的值作為該條件(tiojin)表達式的值。表達式的值。第62頁/共150頁第六十三頁，共150頁。例例3.10 計算計算(j sun)a+b的值。的值。/* 文件名：文件名：ex031001.c */* 計算計算(j sun)絕對值絕對值 */#include int main(void) /*計算計算(j sun)a+b的值的值*/float a,b;printf (input 2 reals please:);scanf (%f%f,&a,&b);printf (n%f+%f=%f,a,b,b=0?a+b:a-b);return

32、0;第63頁/共150頁第六十四頁，共150頁。運行運行(ynxng)情況如下：情況如下：input 2 reals please: 10-9010.000000+-90.000000=100.000000printf()函數中函數中b=0? a+b a-b，當，當b0(b為正值為正值)時，取值時，取值a+b；當；當b0(b為負為負)時，時，取值取值a-b。條件運算符條件運算符“?:”共要求三個運算量，是共要求三個運算量，是C語言中唯一語言中唯一(wi y)的三元運算符。的三元運算符。第64頁/共150頁第六十五頁，共150頁。例例3.11 輸入輸入(shr)兩數，輸出大者。兩數，輸出大者。/

33、* 兩數中取大兩數中取大 */* 文件名：文件名：ex031101.c */#include int main(void)float a,b, max;printf (input 2 reals please:);scanf (%f%f,&a,&b);max=ab?a b;printf (The max is %fn, max);return 0;運行情況運行情況(qngkung)如下：如下：input 2 reals please: -100 89The max is 89.000000第65頁/共150頁第六十六頁，共150頁。因為條件運算符的優先級很低，僅僅比賦值操作符的

34、級別高。其結合方式因為條件運算符的優先級很低，僅僅比賦值操作符的級別高。其結合方式與賦值操作一樣是從右至左的。因此，表達式與賦值操作一樣是從右至左的。因此，表達式max=ab? a b相當于：相當于：max=(ab?a:b);還須注意，還須注意，C語言程序設計中，要求盡量避免使用語言程序設計中，要求盡量避免使用“多余的臨時變量多余的臨時變量”，盡量把程序表述得簡潔。如上述程序中可以盡量把程序表述得簡潔。如上述程序中可以(ky)省去一個變量省去一個變量max，寫，寫為：為：#include int main(void)float a,b;printf (input 2 relas please:

35、);scanf (%f%f,&a,&b);printf (The max is %fn,ab?a:b);return 0;第66頁/共150頁第六十七頁，共150頁。第67頁/共150頁第六十八頁，共150頁。1. 迭代迭代 迭代是一個不斷用新值取代變量的舊值，或由舊值遞推出變量的迭代是一個不斷用新值取代變量的舊值，或由舊值遞推出變量的新值的過程。新值的過程。例例3.12 人口增長人口增長(zngzhng)問題。問題。 按年按年0.2%的增長的增長(zngzhng)速度，現有速度，現有13億人，億人，10年后將有多年后將有多少人少人? 設現人口數為設現人口數為m，則第，則第1年

36、后人口變為：年后人口變為： m = m*(1+0.2%) 即將即將m的值用的值用m*(1+2%)替代。替代。圖圖3.18 計算人口的計算人口的N-S圖當圖當i=10i+m = m*(1+0.2%)初值：初值： m=13,i=1輸出輸出m 第第2年后，把上述替代（賦值表達式）再執行一次。年后，把上述替代（賦值表達式）再執行一次。 要計算要計算10年后的人口，就是把上述表達式執行年后的人口，就是把上述表達式執行10次。這也要用循次。這也要用循環結構實現，重復操作的內容是不斷從一個變量的舊值出發計算它的環結構實現，重復操作的內容是不斷從一個變量的舊值出發計算它的新值。圖新值。圖3.18為計算人口的為

37、計算人口的N-S圖。圖。第68頁/共150頁第六十九頁，共150頁。迭代與下列因素有關迭代與下列因素有關(yugun)： 初值；初值； 迭代公式；迭代公式； 迭代次數或迭代終止標志。迭代次數或迭代終止標志。圖3.18 計算人口的N-S圖當i=10i+m = m*(1+0.2%)初值：m=13,i=1輸出m圖圖3.18 計算計算(j sun)人口的人口的N-S圖圖第69頁/共150頁第七十頁，共150頁。例例3.13 兔子繁殖問題。兔子繁殖問題。 著名著名(zhmng)意大利數學家意大利數學家Fibonacci曾提出一個有趣的曾提出一個有趣的問題：設有一對新生兔子，從第三個月開始它們每個月都生一

38、對問題：設有一對新生兔子，從第三個月開始它們每個月都生一對兔子。按此規律，并假設沒有兔子死亡，一年后共有多少對兔子。兔子。按此規律，并假設沒有兔子死亡，一年后共有多少對兔子。 人們發現每月的兔子數組成如下數列：人們發現每月的兔子數組成如下數列： 1，1，2，3，5，8，13，21，34， 并把它稱為并把它稱為Fibonacci數列。那么，這個數列如何導出呢數列。那么，這個數列如何導出呢?觀察一下觀察一下Fibonacci數列可以發現這樣一個規律：從第數列可以發現這樣一個規律：從第3個數開個數開始，每一個數都是其前面兩個相鄰數之和。這是因為，在沒有兔始，每一個數都是其前面兩個相鄰數之和。這是因為

39、，在沒有兔子死亡的情況下，每個月的兔子數由兩部分組成：上一月的老兔子死亡的情況下，每個月的兔子數由兩部分組成：上一月的老兔子數，這一月剛生下的新兔子數。上一月的老兔子數即其前一個子數，這一月剛生下的新兔子數。上一月的老兔子數即其前一個數。這一月剛生下的新兔子數恰好為上上月的兔子數。因為上一數。這一月剛生下的新兔子數恰好為上上月的兔子數。因為上一月的兔子中還有一部分到這個月還不能生小兔子，只有上上月已月的兔子中還有一部分到這個月還不能生小兔子，只有上上月已有的兔子才能每對生一對小兔子。有的兔子才能每對生一對小兔子。第70頁/共150頁第七十一頁，共150頁。 上述算法上述算法(sun f)可以描

40、述為可以描述為 fib1=fib2=1 (1) fibn=fibn-1+fibn-2 (n=3) (2) 式式(1)為賦初值，式為賦初值，式(2)為迭代公式。用為迭代公式。用C語言來描述式語言來描述式(2)為：為：fib=fib1+fib2；fib1=fib2; /* 為下一次迭代為下一次迭代(di di)作準備作準備*/fib2= fib; 這里，這里，fib1和和fib2和不再僅代表第和不再僅代表第1個月和第個月和第2個月的兔子數，而作為中個月的兔子數，而作為中間變量，代表前兩個月的兔子數，間變量，代表前兩個月的兔子數，fib當前月的兔子數。圖當前月的兔子數。圖3.19為為Fibonacc

41、i算法算法(sun f)的的N-S圖。表圖。表3.2為迭代過程中為迭代過程中fib1、fib2和和fib的變化情形。的變化情形。第71頁/共150頁第七十二頁，共150頁。圖3.19 計算Fiboonacci數列的N-S圖當i=E0f(x) 與f(x1)同號x1=xx2=x真假x=(x1+x2)/2輸入兩個端點：x1和x2，誤差E0圖圖3.21 用二分法求一元方程用二分法求一元方程(y yun fn chn)的根的根該重復過程由誤差控制，而不能用計數法。因為事先該重復過程由誤差控制，而不能用計數法。因為事先(shxin)無法無法估計出所需的迭代次數。估計出所需的迭代次數。 第77頁/共150頁

42、第七十八頁，共150頁。(2) 牛頓迭代法牛頓迭代法 牛頓迭代法又稱牛頓切線法，是比一般迭代法有更高的牛頓迭代法又稱牛頓切線法，是比一般迭代法有更高的收斂速度的近似計算方法。它的基本思想如圖收斂速度的近似計算方法。它的基本思想如圖3.22所示。所示。圖中設圖中設xk是方程是方程f(x)=0的精確的精確(jngqu)解解x*附近的一個猜測附近的一個猜測解，過點解，過點Pk(xk,f(xk)作作f(x)的切線。該切線方程為：的切線。該切線方程為： y=f(xk)+f(xk)(x-xk) 它與它與x軸的交點是方程軸的交點是方程 f(xk)+f(xk)(x-xk)=0 的解，為的解，為 xk+1=xk

43、-f(xk)/f(xk)這就是牛頓迭代法的迭代公式。可以證明，若猜測解這就是牛頓迭代法的迭代公式。可以證明，若猜測解xk取在取在單根單根x*附近，則它恒收斂。這樣，經過有限次迭代后，便可附近，則它恒收斂。這樣，經過有限次迭代后，便可以求得符合誤差要求的近似根。它的算法可以用圖以求得符合誤差要求的近似根。它的算法可以用圖3.23中的中的N-S圖表示。圖表示。第78頁/共150頁第七十九頁，共150頁。xkxk+1f(x)x0yxk+2xk+3x*圖圖3.22 牛頓牛頓(ni dn)迭代發迭代發第79頁/共150頁第八十頁，共150頁。圖圖3.23 用牛頓用牛頓(ni dn)迭代法一元方迭代法一元

44、方程的根程的根x2=x1-f(x1)/f(x2)當|x1-x2|=E0 x1=x2輸入一個猜測解x1，誤差E0 x2=x1-f(x1)/f(x1)輸出x2第80頁/共150頁第八十一頁，共150頁。前面介紹了例前面介紹了例3.12、例、例3.13、例、例3.14三個迭代的例子。例三個迭代的例子。例3.12與例與例3.13稱稱為精確迭代。因為這種算法本身為精確迭代。因為這種算法本身(不考慮機器字長所引起的誤差不考慮機器字長所引起的誤差)經過有限經過有限次迭代可以提供問題的精確解。例次迭代可以提供問題的精確解。例3.14稱為近似迭代，也稱逐次逼近法。稱為近似迭代，也稱逐次逼近法。因為經過有限次迭代

45、仍不能得到問題的精確解。但是只要迭代過程收斂，因為經過有限次迭代仍不能得到問題的精確解。但是只要迭代過程收斂，經過有限次的迭代，總可以得到足夠精度的近似解。一般說來，精確迭代經過有限次的迭代，總可以得到足夠精度的近似解。一般說來，精確迭代的迭代次數是事先的迭代次數是事先(shxin)可以計算出來的可以計算出來的(但不一定用它去控制循環過但不一定用它去控制循環過程程)；而近似迭代的迭代次數，事先；而近似迭代的迭代次數，事先(shxin)無法計算出來，它的循環結無法計算出來，它的循環結構要靠誤差進行控制。構要靠誤差進行控制。注意，在當重復結構之前要先按照迭代公式計算一次注意，在當重復結構之前要先按

46、照迭代公式計算一次x2。否則，沒有辦法。否則，沒有辦法計算當循環的判斷表達式。計算當循環的判斷表達式。第81頁/共150頁第八十二頁，共150頁。2. 窮舉窮舉 窮舉是另一種重復型算法。它的基本思想是，對問題的所有可能窮舉是另一種重復型算法。它的基本思想是，對問題的所有可能狀態一一測試，直到找到解或將全部可能狀態都測試過為止。狀態一一測試，直到找到解或將全部可能狀態都測試過為止。 循環控制有兩種辦法：計數法與標志循環控制有兩種辦法：計數法與標志(biozh)法。計數法要先確法。計數法要先確定循環次數，然后逐次測試，完成測試次數后，循環結束。標志定循環次數，然后逐次測試，完成測試次數后，循環結束

47、。標志(biozh)法是達到某一目標后，使循環結束。法是達到某一目標后，使循環結束。例例3.15 輸入輸入10個數，將最大的一個數打印出來。個數，將最大的一個數打印出來。 從輸入的從輸入的10個數中選取最大的一個數的算法，可以粗略地看作個數中選取最大的一個數的算法，可以粗略地看作這樣的過程：、這樣的過程：、 S1：輸入：輸入10個數；個數； S2：從：從10個數中選最大一個數；個數中選最大一個數； S3：輸出最大的一個數。：輸出最大的一個數。但是，在介紹數組之前，目前還沒有合適的方法來存儲但是，在介紹數組之前，目前還沒有合適的方法來存儲10個數。為個數。為此可以考慮類似打擂臺一樣的一種算法：此

48、可以考慮類似打擂臺一樣的一種算法： S1：輸入：輸入1個數，暫時作為擂主個數，暫時作為擂主最大數。最大數。 S2：輸入：輸入9個數個數窮舉這窮舉這9個數，每輸入一個，打一次擂臺個數，每輸入一個，打一次擂臺把最大數與剛輸入的數據進行比較，把大者作為新擂主把最大數與剛輸入的數據進行比較，把大者作為新擂主最大數。最大數。 S3：輸出最大數。：輸出最大數。第82頁/共150頁第八十三頁，共150頁。這個算法可以用圖這個算法可以用圖3.24所示的算法表示為一個所示的算法表示為一個(y )重復結重復結構。構。當imaxmax=n( 空)真假輸入第i個數n輸入一個數給max輸出max初始化：i=1圖圖3.2

49、4 采用采用(ciyng)計數器的計數器的10中取大算法中取大算法 第83頁/共150頁第八十四頁，共150頁。這里，變量這里，變量i是一個計數器，每輸入一個數，它要自增是一個計數器，每輸入一個數，它要自增1，用，用來。計數法使用起來很方便。但它要求在程序執行前必須先來。計數法使用起來很方便。但它要求在程序執行前必須先知道循環的總次數，并要先給知道循環的總次數，并要先給I賦一個初值。但是，它需要賦一個初值。但是，它需要(xyo)操作人員記住每次輸入的是第幾個數。當數據量很操作人員記住每次輸入的是第幾個數。當數據量很多時，會使操作人員感到很不方便。多時，會使操作人員感到很不方便。當不想或無條件使

50、用計數法時，可以使用標志法。這是一種當不想或無條件使用計數法時，可以使用標志法。這是一種“有多少算多少有多少算多少”的辦法。具體方法是：在測試前先設置一的辦法。具體方法是：在測試前先設置一個標志性數據，如對本例可以設為個標志性數據，如對本例可以設為-32768（輸入的數據中不（輸入的數據中不可能用得到的數據）。這樣，操作者在沒有數據可以輸入時，可能用得到的數據）。這樣，操作者在沒有數據可以輸入時，輸入該數來表示已經沒有數據。這樣輸入是數就不限于輸入該數來表示已經沒有數據。這樣輸入是數就不限于10個個了。圖了。圖3.25為采用標志法的多中取大算法。為采用標志法的多中取大算法。第84頁/共150頁

51、第八十五頁，共150頁。圖圖3.25 采用標志采用標志(biozh)法的多中取法的多中取大算法大算法 當（n！=FLAG）nmaxmax=n( 空)真假輸入下一個數nmax=n輸出max初始化：i=1，FLAG=-32768輸入一個數n第85頁/共150頁第八十六頁，共150頁。例例3.16 百錢買百雞問題。百錢買百雞問題。 公元前五世紀公元前五世紀(shj)，我國古代數學家張丘建在算經，我國古代數學家張丘建在算經一書中提出了一書中提出了“百雞問題百雞問題”：雞翁一值錢五，雞母一值錢三，雞：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、母、雛各幾何雛三值錢一。百錢買百雞，問雞翁

52、、母、雛各幾何?(1) 基本解題思路基本解題思路 這是一個有名的不定方程問題：這是一個有名的不定方程問題：cocks+hens+chicks=100(1)5*cocks+3*hens+chicks/3=100(2) 式中：式中：cocks：雞翁數：雞翁數hens：雞母數：雞母數chicks：雞雛：雞雛(j ch)數數第86頁/共150頁第八十七頁，共150頁。 對上述不定方程問題，要先確定一個變量對上述不定方程問題，要先確定一個變量(binling)的值，才能對其進行求解。的值，才能對其進行求解。由問題中給出的條件，很容易得到三個變量由問題中給出的條件，很容易得到三個變量(binling)的取

53、值范圍：的取值范圍：cocks: 019中的整數中的整數(因為每只雞翁因為每只雞翁5錢，因此它不可能錢，因此它不可能(knng)超過超過19只只)hens: 033中的整數中的整數chicks: 0100中的整數中的整數 基本基本(jbn)的解題思路是：依次取的解題思路是：依次取cocks值域中的一個值，然后求其余值域中的一個值，然后求其余兩數，看是否合乎題意，合乎者為解。這個基本兩數，看是否合乎題意，合乎者為解。這個基本(jbn)解題思路便是解題思路便是解本題的粗略算法，下面是它的偽代碼描述，圖解本題的粗略算法，下面是它的偽代碼描述，圖3.26為其為其N- S圖。圖。s1: cocks=0;

54、 /*賦初值賦初值*/s2: 當當(cocks=19)s2.1: 找滿足題意的找滿足題意的hens, chicks;s2.2: cocks+；S3:輸出一組輸出一組cocks,hens和和chichs第87頁/共150頁第八十八頁，共150頁。圖圖3.26 百錢買百雞的粗略百錢買百雞的粗略(cl)算法算法 當（cocks=19）找滿足題意的hens和chicks輸出一組cocks,hens和chichs初始化：cocks=0cocks +第88頁/共150頁第八十九頁，共150頁。 (2) 對對s2.1細化細化思路思路1：把已確定的：把已確定的cocks代入式代入式(1)與與(2)中，求解方程

55、，看能否找到滿中，求解方程，看能否找到滿足題意的解。這種思路不太適合計算機求解。足題意的解。這種思路不太適合計算機求解。思路思路2：在每個給定的：在每個給定的cocks下，面對下，面對(min du)hens的取值范圍內的各的取值范圍內的各個值依次測試，看能找到哪些個值依次測試，看能找到哪些hens及及chicks滿足題意。于是得滿足題意。于是得到如下到如下s2.1細化算法。細化算法。 用這段算法代替圖用這段算法代替圖3.26中的中的“找滿足題意找滿足題意(t y)的的hens和和chicks”，得到圖，得到圖3.27所示的百錢買百雞的所示的百錢買百雞的N-S圖算法。圖算法。當(hens=33

56、)找滿足(mnz)題意的chicks;即hens=hens+1*/第89頁/共150頁第九十頁，共150頁。圖圖3.27 百錢買百雞算法百錢買百雞算法(sun f)的細化算法的細化算法(sun f) 當（cocks=19）當（hens=33）初始化：cocks=0輸出一組cocks,hens和chichscocks +hens=0找滿足題意的chicksHens+第90頁/共150頁第九十一頁，共150頁。(3) 對細化對細化 對來說，對來說，cocks及及hens都已確定都已確定(qudng)，這時的，這時的chicks可以計算可以計算出：出： chicks=100-cocks-hens 式

57、式(1)已滿足。只要用式已滿足。只要用式(2)指定的條件測試便可知這一組指定的條件測試便可知這一組cocks, hens及及chicks是否滿足題意。滿足則打印出一組解。于是可細化為：是否滿足題意。滿足則打印出一組解。于是可細化為：圖圖3.28為進一步細化的百錢買百雞算法為進一步細化的百錢買百雞算法(sun f)。chicks=100-cocks-hens;if(5*cocks+3*hens+chicks/3.0)=100)printf (%d %d %dn, cocks, hens, chicks);第91頁/共150頁第九十二頁，共150頁。 圖3.28 百錢買百雞算法(sun f)的細化

58、算法(sun f) 當（cocks=19）當（hens=33）cocks=0cocks +hens=0chicks=100-cocks-henshens+(5*cocks+3*hens+chicks/3.0)=100輸出一組cocks,hens和chichs（空）真假這一小節介紹了應用重復結構的典型這一小節介紹了應用重復結構的典型(dinxng)問題及算法思想，下面介紹問題及算法思想，下面介紹如何用如何用C語言提供的三種重復語句來實現有關算法。語言提供的三種重復語句來實現有關算法。第92頁/共150頁第九十三頁，共150頁。循環結構循環結構while是一種循環結構，其形式是一種循環結構，其形式

59、(xngsh)如下：如下：while (表達式表達式) 循環體語句循環體語句(yj)循環體在執行循環體在執行while語句時，先對判斷表達式進行語句時，先對判斷表達式進行(jnxng)計算，若計算，若其值為真其值為真(非非0)，則執行循環體語句；否則跳過循環體，而執行該結，則執行循環體語句；否則跳過循環體，而執行該結構后面的語句。在進入循環體后，每執行完一次循環體語句后，再對構后面的語句。在進入循環體后，每執行完一次循環體語句后，再對判斷表達式進行判斷表達式進行(jnxng)一次計算和判斷。當發現判斷表達式的值為一次計算和判斷。當發現判斷表達式的值為0時，便立即退出循環。時，便立即退出循環。下

60、面介紹這種重復結構的應用。下面介紹這種重復結構的應用。第93頁/共150頁第九十四頁，共150頁。例例3.17 計算人口增長的計算人口增長的C程序。程序。 按照圖按照圖3.18所示的算法，可以很容易地得到下面的所示的算法，可以很容易地得到下面的C程序。程序的程序。程序的主體結構是一個主體結構是一個(y )while重復結構。重復結構。/* 文件名：文件名：ex031701.c */* 計算人口計算人口(rnku)增長增長 */#include int main(void)double m=13;int i=1; while(i=10)m=m*(1+0.002);i+; printf(“Population after 10 yers is:%fn”,m); return 0;第94頁/共150頁第九