1.2 算法
1.2 算法
1.2.1 算法及算法的特性
算法是對(duì)具體問(wèn)題求解步驟的一種描述。做任何事情都必須事先想好執(zhí)行的步驟，然后按步驟進(jìn)行操作，才能避免產(chǎn)生錯(cuò)亂。對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟。有的方法需要的步驟很少，而有些方法需要的步驟則較多。一般來(lái)說(shuō)，希望采用過(guò)程簡(jiǎn)單明了和思路清晰正確的方法。因此，為了有效地解題，一個(gè)算法應(yīng)具有下列5個(gè)特性。
① 有窮性。一個(gè)算法必須在執(zhí)行有限個(gè)操作步驟之后結(jié)束，且每一步都可以在有窮時(shí)間內(nèi)完成。
② 確定性。算法中的每一條指令必須有確切的含義，不會(huì)產(chǎn)生二義性。
③ 可行性。算法中描述的操作在計(jì)算機(jī)上都是可以實(shí)現(xiàn)的。
④ 輸入。一個(gè)算法應(yīng)有零個(gè)或多個(gè)輸入。
⑤ 輸出。一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出。
1.2.2 算法的描述工具
為了使算法表達(dá)得更清晰，更容易實(shí)現(xiàn)算法的編寫，在程序設(shè)計(jì)時(shí)通常使用專門的算法表達(dá)工具對(duì)算法進(jìn)行描述。對(duì)于復(fù)雜的問(wèn)題，可以先用算法表達(dá)工具對(duì)算法進(jìn)行描述，再進(jìn)行編程，算法的最終實(shí)現(xiàn)應(yīng)該是計(jì)算機(jī)程序。算法的評(píng)價(jià)標(biāo)準(zhǔn)涉及很多方面，但正確性和清晰易懂性永遠(yuǎn)是一個(gè)好算法的基本條件。
計(jì)算機(jī)算法的表達(dá)工具通常有以下4種。
1．用自然語(yǔ)言表示算法
用自然語(yǔ)言表示算法就是把算法的各個(gè)步驟用人們所熟悉的自然語(yǔ)言依次表示出來(lái)。但要注意，用自然語(yǔ)言所表示的每一個(gè)操作步驟必須是計(jì)算機(jī)能夠?qū)崿F(xiàn)的。
【例1.1】 求兩個(gè)整數(shù)m與n的和，用自然語(yǔ)言求解該問(wèn)題的步驟如下。
步驟1：輸入整數(shù)n和m。
步驟2：求和sum=m+n。
步驟3：輸出兩數(shù)之和sum。
以上3個(gè)步驟都是在計(jì)算機(jī)上可以實(shí)現(xiàn)的，所以是一個(gè)正確的算法描述。用自然語(yǔ)言表示算法，人們比較容易理解，但書寫較煩瑣，而且在某些場(chǎng)合，由于自然語(yǔ)言含義的不確切性，容易引起歧義，造成誤解；另外對(duì)比較復(fù)雜的問(wèn)題，用自然語(yǔ)言又難以表達(dá)準(zhǔn)確。因此，較少采用自然語(yǔ)言表示復(fù)雜算法。
2．用流程圖表示算法
用流程圖表示算法就是用一些大家共識(shí)的專用圖形符號(hào)和帶有箭頭的流程線來(lái)表示算法。用圖形符號(hào)表示算法必須要有一組統(tǒng)一規(guī)定、含義確定的專用符號(hào)。表1.1所示為傳統(tǒng)流程圖所用的基本符號(hào)。圖1.2所示為例1.1中求兩個(gè)整數(shù)m與n之和的傳統(tǒng)流程圖算法。
可見(jiàn)，用流程圖來(lái)表示算法，直觀形象，繪制簡(jiǎn)單方便，流程清晰，各種操作一目了然，而且不會(huì)產(chǎn)生“二義性”。缺點(diǎn)是，占用面積大，由于使用流程線指出各框的執(zhí)行順序，且對(duì)流程線的方向沒(méi)有任何限制，可以隨意轉(zhuǎn)向，往往使人弄不清楚流程的思路。
針對(duì)上述問(wèn)題，1973年由美國(guó)計(jì)算機(jī)科學(xué)家 I.Nassi 和B.Shneiderman提出了結(jié)構(gòu)化程序設(shè)計(jì)流程圖，又稱N-S流程圖。N-S流程圖保留了傳統(tǒng)流程圖可以形象直觀地表示算法的優(yōu)點(diǎn)，去掉了流程線，即不允許流程任意轉(zhuǎn)移，只能從上到下順序進(jìn)行，算法的每一步都用一個(gè)矩形框來(lái)描述，把這些矩形框按執(zhí)行的次序連接起來(lái)就是一個(gè)完整的算法。這種流程圖規(guī)定了幾種基本結(jié)構(gòu)作為構(gòu)造算法的基本單元，將在下一節(jié)中結(jié)合3種基本結(jié)構(gòu)來(lái)介紹。
表1.1 傳統(tǒng)流程圖所用的基本符號(hào)表
所謂偽代碼是指用介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的一種代碼來(lái)描述算法。它的表示形式比較自由靈活，而且由于與程序設(shè)計(jì)語(yǔ)言比較接近，因此可以比較容易地轉(zhuǎn)換成計(jì)算機(jī)程序。偽代碼無(wú)統(tǒng)一的語(yǔ)法，只要自己或別人能看懂就行。
4．用程序設(shè)計(jì)語(yǔ)言表示算法
用自然語(yǔ)言和用圖形符號(hào)所表示的算法有一個(gè)共同的缺點(diǎn)就是計(jì)算機(jī)都不能識(shí)別和執(zhí)行。只有用計(jì)算機(jī)能理解和執(zhí)行的程序設(shè)計(jì)語(yǔ)言把算法表示出來(lái)，然后把程序輸入到計(jì)算機(jī)并執(zhí)行，計(jì)算機(jī)才能按照預(yù)定的算法去解決問(wèn)題。