【正文】 、 B、 C，三點的坐標分別為： ax、 ay、 bx、by、 cx、 cy。該問題的解法可以描述為如下 PAD. 讀入三點坐標只是一個讀語句，不必求精 ，下邊考慮求垂直平分線和求交點。 輸入三點坐標： ax、 ay、 bx、 by、 cx、 cy 計算邊 AB的垂直平分線 R 計算邊 BC的垂直平分線 S 求直線 R、 S交點 T 輸出交點 T坐標 開始 結束 求垂直平分線 。 可以先設計一個函數求線段 VU的垂直平分線 ， 然后分別以 AB、 BC為實在參數調用該函數 。 求線段的垂直平分線應該找到該線段的中點 ， 和該線段的直線方程 ，然后過中點的與線段方程垂直的直線即是 。 按這個分析得如下 PAD。 計算邊 UV的中點坐標 求線段 UV的直線方程 求垂直平分線方程 開始 結束 計算 UV中點，只是兩個公式： x=(ux+vx)/2 y=(uy+vy)/2 求 AB直線方程也只是兩個公式： 斜率 a=(uyvy)/(uxvx) 截距 b=uya*ux 可以寫一個函數 line(x1,y1,x2,y2, *a,*b ) line *b = y1*a*x1 結束 *a = (y2y1)/(x2x1) x1,y1,x2,y2：兩點坐標 *a, *b ：直線方程系數 垂直平分線方程為： 斜率 aa= 1/a 截距 bb=ya*x 問題已經解決。 求 R、 S交點。已知 AB的垂直平分線 R 的斜率為 aa，截距為 bb ，設線段 BC的垂直平分線 S 的斜率 aaa，截距為 bbb，則兩條垂直平分線方程的交點為： x=(bbbbb)/(aaaaa) y=aa*x+bb 這就是所求。綜合上述分析，編出程序如下： /*PROGRAM test*/ include include /*求由兩點所確定直線方程系數 y=a*x+b */ void line(float x1,float y1,float x2,float y2,float *a,float *b){ *a=(y1y2)/(x1x2)。 *b=y1(*a)*x1。 } /*求由兩點所確定直線的中垂線的方程 */ void vline(float x1,float y1,float x2,float y2,float *a, float *b){ float ta,tb。 float x,y。 x=(x1+x2)/2。 y=(y1+y2)/2。 //兩點所確定直線的中點 line(x1,y1,x2,y2,amp。ta,amp。tb)。 //兩點所確定直線的方程 *a=1/ta。 *b=y(*a)*x。 //中垂線方程 } 運行結果演示 /*求兩條直線交點，計算交點坐標 */ void OnePoint(float a1,float b1,float a2,float b2,float *x,float *y){ *x=(b2b1)/(a1a2)。 *y=a1*(*x)+b1。 //交點坐標 } /*主程序 */ void main(){ float ax,ay,bx,by,cx,cy。 //三點坐標 float a_a,a_b,b_a,b_b。 //三角形兩條邊中垂線的直線方程 */ float centerx,centery。 //中垂線交點坐標 */ printf(please input coordinat of point a、 b、 c:)。 //輸入三角形三點坐標 scanf(%f%f %f%f %f%f ,amp。ax,amp。ay,amp。bx,amp。by,amp。cx,amp。cy)。 vline(ax,ay,bx,by,amp。a_a,amp。a_b)。 vline(bx,by,cx,cy,amp。b_a,amp。b_b)。 //求兩條中垂線的斜率和截距 OnePoint( a_a,a_b,b_a,b_b,amp。centerx,amp。centery)。 //兩條中垂線交點 printf(the center of the circumcircle is:(%g,%g)\n ,centerx,centery)。 } 例 ，全部都是使用 “ 自頂向下、逐步求精 ” 的方法開發(fā)的。 “ 自頂向下、逐步求精 ” 的程序設計技術是目前較為時髦的（當然也是較為合理的）找出一個問題的解題算法的一種思維方法。該技術的基本思想在第五章已經初步介紹過。 “自頂向下、逐步求精 ” 過程中的每一步，分解某一具體問題時，主要用到如下四種求精技術： 1. 順序連接的求精 2. 分支、選擇的求精 3. 循環(huán)的求精 4. 遞歸的求精 “自頂向下，逐步求精 ” 的分析技術實質上是上圖所示過程的反復。 求解一個問題 粗略的解決方案 細 化 第一步子問題 第二步子問題 第 n步子問題 ... 前處理 結束條件 后處理 進展 一 步 前處理 后處理 條件 處理 1 處理 2 處理 n ... ... 條件 2 條件 n 條件 1 前處理 后處理 遞歸 條件 遞歸 順序 連接 循環(huán) 分支 選擇 遞歸 當問題的子解具有前后關系時，采用第一種順序連接的求精技術，將問題分解成互不相交的幾個子問題的順序執(zhí)行。 當問題是分別不同情況而應該進行不同處理時，采用分支、選擇的求精技術，構造分支。這時要注意分支的條件一定要正確。 當問題的子解具有特性：如果有向解的方向前進一步的方法，且不斷重復該步驟，即能解決問題，最終達到完全解。則應該采用循環(huán)的求精技術（構造循環(huán)）。這時一定要弄清循環(huán)的初始條件、結束條件和有限進展的一步都是什么。 當問題的某步解法與前邊高層次的某步解法具有相同性質，只是某些參數不同時，可采用遞歸的求精技術。這時應注意遞歸的參數變化規(guī)律以及遞歸出口。 “自頂向下、逐步求精 ” 是一種思維方式，它不是計算機程序員獨有的。事實上在日常生活、工作中也經常的使用該技術，只不過不自覺或沒意識到罷了。 例如寫一本書、或文章，總要作一個提綱，全書分成幾章；然后對每一章又列出本章分幾節(jié)；對每一節(jié)又分出幾小節(jié)等等；最后再具體著手寫每個小節(jié)。 又如，設計生產某產品的一個工廠（比如汽車廠）：首先應考慮全廠應該分成幾個車間（例如，生產發(fā)動機的發(fā)動機車間、生產底盤的底盤車間、生產車輪的車輪車間、總裝車間、 ...）；然后再考慮每個車間應分成幾個工段（例如，發(fā)動機車間應分成生產機殼的機殼工段、生產活塞的活塞工段、負責工件熱處理的熱處理工段、 ...）；然后再考慮每個工段應該配備多少種設備，每種設備應配備多少臺， ... 等等。 這就是自頂向下、逐步求精。 采用自頂向下、逐步求精方法構造程序有如下優(yōu)點 : 1. 程序的層次分明、結構清晰。 2. 便于集體開發(fā)程序。對于大型程序來講，可以每組負責一個模塊（一個子部分），在一個組內又可以每個人負責一個子模塊（更小的子部分）等等。而各個模塊之間以及各個子模塊之間相對獨立，互相之間沒有制約，各個模塊的負責人員可以獨立的進行各自的程序設計。 3. 便于調試。若程序有錯誤，可以很容易的將錯誤局部于某一子部分，找出錯誤，同時每一部分的錯誤是獨立的，也不至于影響其它的部分。 例 三個齒輪嚙合問題 設有三個齒輪互相銜接，求當三個齒輪的某兩對齒互相銜接后到下一次這兩對齒再互相銜接，每個齒輪最少各轉多少圈。 解 :這是求最小公倍數的問題。每個齒輪需轉圈數是三個齒輪齒數的最小公倍數除以自己的齒數。設 – 三個齒輪的齒數分別為 :na、 nb、 nc ； – 嚙合最小圈數分別為 :ma、 mb、 mc ； – 三齒輪齒數的最小公倍數為 k3 。 計算步驟表示為： 開始 讀入三齒輪齒數 求三齒數的最小公倍數 k3 分別計算嚙合的最小圈數 輸出結果 結束 讀入三齒輪齒數和輸出結果，分別只是一次調用讀或寫函數，不必求精。 求精計算三齒數的最小公倍數 k3 。可以把該問題分解成 先求兩個齒數 na與 nb的最小公倍數 k2 ， 然后再求 k2與第三個齒數 nc 的最小公倍數 k3 ， k3即為 na、 nb、 nc三個齒輪齒數的最小公倍數。 設已經有求兩個數的最小公倍數的函數 int lowestcm( int x, int y ) 則該求精過程可表示成 。 求三齒數的 最小公倍數 k3=lowestcm( lowestcm(na,nb), nc ) 結束 求精求兩個數的最小公倍數的函 lowestcm 。 x、 y的最小公倍數是 x、 y 的積除以 x、 y 的最大公約數。設已經有求兩個數的最大公約數的函數 int gcd(int x, int y) 則該求精過程可表示成： int lowestcm(int x , int y) return x*y / gcd(x,y) 結束 def ? 歐幾里德輾轉相除法 – u % v → R1 – v % R1 → R2 – R1 % R2 → R3 – R2 % R3 → R4 – … … … … – Rn2 % Rn1 → Rn=0 – Rn1 % Rn → – Rn 為正整數 u 、 v的最大公因數 采用展轉相除法求兩個數的最大公約數，函數 int gcd(int x, int y) 定義如下 ??????0y )%,g c d (0y y)g c d ( x , yxyx函數 gcd是一個遞歸函數，先采用分支求精過程、再采用遞歸求精過程，可以求精成下圖 int gcd( int x, int y) 結束 y≠0 return gcd(y , x % y) return x 最后，分別計算嚙合的最小圈數可以被求精成下圖 。 開始 ma = na / k3 mb = nb / k3 mc = nc / k3 結束 /*PROGRAM mesh*/ include /*求 x,y的最大公約數 */ int gcd(int x,int y){ if(y==0) return x。 else return gcd(y,x%y)。 } /*求 x,y的最小公倍數 */ int lcm(int x,int y){ return(x*y/gcd(x,y))。 } /*主函數 */ void main(){ int n1,n2,n3,result。 printf(please input n1 n2 n3:)。 scanf(%d%d%d,amp。n1,amp。n2,amp。n3)。 result=lcm(lcm(n1,n2),n3)。 printf(to mesh again the first gear must rotate about %4d rings\n,result/n1)。 printf(to mesh again the second gear must rotate about %4d rings\n,result/n2)。 printf(to mesh again the third gear must rotate about %4d rings\n,result/n3)。 getchar()。getchar()。 } 運行結果演示 167。 結構化程序設計原則 從 20世紀 60年代開始，計算機軟件系統日益發(fā)展，作為軟件主要組成部分的程序系統越來越龐大，復雜度越來越高，造價也越來越昂貴，同時出錯率也不斷增加，系統的可靠性越來越難以保證，維護也越來越困難。比如，當年著名的 IBM360操作系統出錯率是 3‰ 。經過幾年運行后，征集了廣大用戶的意見 , 集中進行一次修改，修改完成后，最后測試出錯率仍是3‰ 。例子很多，此種情況的不斷發(fā)展，最后終于導致一場所謂的軟件危機。在該背景下， 1968年 Dijkstra 提出了結構化程序設計思想。這種思想的基點是： “清晰，易懂地書寫程序邏輯，使程序結構表現