1第三講：算法及其描述數(shù)據(jù)結(jié)構(gòu)與算法2

算法（Algorithm)是描述計(jì)算機(jī)解決給定問題的操作過程（解題方法），即為解決某一特定問題而由若干條指令組成的有窮序列。ontents1.3算法及其描述程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問題選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法。而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。3（1）有窮性---

一個(gè)算法在執(zhí)行了有窮步后一定要終止。（2）確定性（無二義）---算法的每一步操作都必須有確切定義，不得有任何歧義性。ontents算法的五個(gè)重要特性：算法的概念和描述（3）可行性---算法的每一步操作都必須是可行的，即每步操作均能在有限時(shí)間內(nèi)完成。（4）輸入數(shù)據(jù)---一個(gè)算法有n（n>=0)個(gè)初始數(shù)據(jù)的輸入。（5）輸出數(shù)據(jù)---一個(gè)算法有一個(gè)或多個(gè)與輸入有某種關(guān)系的有效信息的輸出。思考：算法與程序有何區(qū)別？

【例（補(bǔ)充）】考慮下列兩段描述，這兩段描述均不能滿足算法的特性，試問它們違反了哪些特性？voidexam1(){intn＝2;while(n%2＝＝0)n＝n+2;printf("%d\n"，n);}其中有一個(gè)死循環(huán)，違反了算法的有窮性特性。（1）描述一4/16voidexam2(){intx，y;y=0;x=5/y;printf("%d，%d\n"，x，y);}其中包含除零錯(cuò)誤，違反了算法的可行性特性（2）描述二5/166

（1）正確性（2）可讀性要求算法可讀性好，易于理解，易于編碼，易于調(diào)試。（3）健壯性（4）效率與低存儲(chǔ)量要求執(zhí)行算法所耗費(fèi)的時(shí)間（高效率）。執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間（主要考慮輔存空間；低存儲(chǔ)要求）。ontents算法設(shè)計(jì)的目標(biāo)：算法的簡(jiǎn)單分析：7描述---可采用自然語言、數(shù)學(xué)語言或約定的符號(hào)語言、偽代碼、流程圖等。計(jì)算機(jī)相關(guān)專業(yè)學(xué)生應(yīng)該熟練使用計(jì)算機(jī)語言來描述算法。本課的描述---采用類C語言。ontents算法的描述和實(shí)現(xiàn)：算法的概念和描述8算法設(shè)計(jì)的一般步驟：1）分析算法的功能。2）確定算法有哪些輸入，將這些輸入設(shè)計(jì)成輸入型參數(shù)；

確定算法有哪些輸出，將這些輸出設(shè)計(jì)成輸出型參數(shù)。3）設(shè)計(jì)函數(shù)體完成從輸入到輸出的操作過程。算法輸入輸出ontents返回值類型

算法對(duì)應(yīng)的函數(shù)名(形參列表){//實(shí)現(xiàn)由輸入?yún)?shù)到輸出參數(shù)的操作 …}函數(shù)體返回值：通常為int型或bool類型，表示算法是否成功執(zhí)行。形參列表：由輸入型參數(shù)和輸出型參數(shù)構(gòu)成。算法輸入算法輸出算法的描述的一般格式：ontents10輸出型參數(shù)的設(shè)計(jì)：ontents示例：設(shè)計(jì)一個(gè)交換兩個(gè)整數(shù)的算法。

voidswap1(intx，inty){inttmp;tmp=x;x=y;y=tmp;}當(dāng)執(zhí)行語句swap1(a，b)時(shí)，a和b實(shí)參值不會(huì)發(fā)生了交換。分析：x、y既是輸入型參數(shù)，也是輸出型參數(shù)

改正方法1：采用指針的方式來回傳形參的值，需將上述函數(shù)改為：上述函數(shù)的調(diào)用改為swap2(&a，&b)

voidswap2(int*x，int*y){

inttmp;tmp=*x; //將x的值放在tmp中*x=*y; //將x所指的值改為*y*y=tmp；

//將y所指的值改為tmp}交換形參x和y所指向的值11/16輸出型參數(shù)的設(shè)計(jì)：ontentsvoid

swap(int&x，int&y)//形參前的“&”符號(hào)不是指針運(yùn)算符{

inttmp=x;

x=y;y=tmp;}

改正方法2：采用引用型形參將輸出型形參改為引用類型。當(dāng)執(zhí)行語句swap(a，b)時(shí)，形、實(shí)參的匹配相當(dāng)于：

int&x=a;//a為x的引用

int&y=b;//b為y的引用這樣，a與x共享存儲(chǔ)空間、b與y共享存儲(chǔ)空間，因此執(zhí)行函數(shù)后a和b的值發(fā)生了交換

簡(jiǎn)單明了。交換形參x和y的值12/16輸出型參數(shù)的設(shè)計(jì)：ontents13[例]假設(shè)8枚金幣中有一枚是偽造的，真假金幣的區(qū)別僅僅是重量不同，現(xiàn)只有一個(gè)沒有砝碼的天平做工具，則至少用幾次比較即可找出這枚偽造的金幣。要求用文字寫出比較的算法。(提示：參考折半查找法即二分法)【解答：】①先任選4枚金幣,每邊各2枚置于天平上,若天平平衡，則說明偽造的金幣在另外4枚中；若不平衡，則說明偽造的金幣在選擇的4枚中，于是1次比較可以確定偽造的金幣在哪4枚中；

自然語言描述算法舉例ontents算法的概念和描述14[例]假設(shè)8枚金幣中有一枚是偽造的，真假金幣的區(qū)別僅僅是重量不同，現(xiàn)只有一個(gè)沒有砝碼的天平做工具，則至少用幾次比較即可找出這枚偽造的金幣。要求用文字寫出比較的算法。(提示：參考折半查找法即二分法)【解答：】②然后在含偽造的金幣的4枚中，任選2枚金幣，每邊各1枚置于天平上，若天平平衡，則說明偽造的金幣在另外2枚中，若不平衡，則說明偽造的金幣在選擇的2枚中，于是2次比較可以確定偽造的金幣在哪2枚中；③最后在含偽造的金幣的2枚中，任選1枚金幣與其他1枚真幣置于天平上，若不平衡，則選擇的這枚是偽造的，否