第三章-算法基礎(chǔ)

第三章算法基礎(chǔ)引言

數(shù)據(jù)在信息社會中具有重要價值，掌握數(shù)據(jù)處理的基本方法與技能具有重要意義。隨著數(shù)據(jù)的快速增長，人工方式處理海量數(shù)據(jù)的效率正變得低下，因此掌握利用計算機和算法更高效地分析和解決問題的方法在計算機科學(xué)界的作用日益凸顯。

計算機解決問題的過程1、分析問題

在利用計算機解決問題之間，我們首先要分析問題的需求情況、已知條件和需要解決的問題2、設(shè)計算法

問題分析清楚后，需要給出解決問題的詳細方法和步驟，這一過程稱為設(shè)計算法。3、編寫程序

有了清晰可操作的算法描述，就可以選擇一種計算機語言工具來編寫程序，實現(xiàn)算法。一般來說，只要算法確定，對計算機程序設(shè)計語言的選擇沒有特別的限定，通常根據(jù)問題的特性和編程人員對語言的熟悉程度來選定編寫程序。4、調(diào)試運行程序

程序編寫完成以后，再通過鍵盤把程序輸入計算機中運行，檢查程序能否按預(yù)想的效果執(zhí)行，這一過程稱為程序的調(diào)試運行。一、設(shè)計從A市到B市耗時最少的旅行路線方案當從A市到B市沒有直達的交通工具時（不考慮水上交通工具），我們可以利用鐵路公司、汽車客運公司和航空公司公布的信息，設(shè)計出最佳的旅行路線。

我們從鐵路公司、各航空公司和汽車客運公司網(wǎng)站得知，直達B市的交通工具只有火車和汽車兩種，出發(fā)地有B1，B2，…，Bk市（沒有A市），從A市出發(fā)到B1，B2，…，Bk市的交通工具有飛機、火車和汽車三種，這樣從A市經(jīng)B1，B2，…，Bk市到B市的交通情況如右圖所示。

由于從A市到B1，B2，…，Bk市有不同的交通工具，每一種交通工具又有不同的班次，因此從A市出發(fā)到中轉(zhuǎn)城市B1，B2，…，Bk市就有M1、M2，…，Mk種班次。同樣，從中轉(zhuǎn)城市B1，B2，…，Bk市到B市也有不同的交通工具，每一種交通工具有不同的班次，因此從中轉(zhuǎn)城市B1，B2，…，Bk市到B市就有N1，N2，…，Nk種班次。于是從A市經(jīng)B1，B2，…，Bk市到B市的交通班車（班機）數(shù)共有：S=M1×N1+M2×N2+…+Mk×Nk尋找從A市到B市耗時最少的旅行路線問題就轉(zhuǎn)化為在S種聯(lián)運班次中找到一種耗時最少的聯(lián)運班次。這樣就需要遍歷每一個班次進行比較，人工方式找到能夠中轉(zhuǎn)且等待時間和行駛時間最少的班次，工作量極其浩大！假設(shè)從A市到B市的中轉(zhuǎn)城市只有B1，B2市，從A市經(jīng)B1，B2市到B市的交通情況如表3-2和表3-3所示。于是，從A市經(jīng)B1市到B市的聯(lián)運班次有7×9=63班；從A市經(jīng)B2市到B市的聯(lián)運班次有12×9=108班，合計為S=63+108=171班。然后在171班次中找到能夠中轉(zhuǎn)且等待時間加上行駛時間最少的聯(lián)運班次，如下圖所示。

當數(shù)據(jù)量很大，人工處理效率很低時，我們可以借助計算機，通過編寫計算機程序解決問題。在利用計算機解決問題之前，我們首先要分析問題的需求情況、已知條件和需要解決的問題。

在從A市到B市耗時最少的旅行路線問題中，在不知道有多少個中轉(zhuǎn)城市和每個城市有多少班車（或飛機）的情況下，我們可以利用大數(shù)據(jù)挖掘技術(shù)中的爬蟲程序（爬蟲：一段自動抓取互聯(lián)網(wǎng)信息的程序，從互聯(lián)網(wǎng)上抓取對于我們有價值的信息。）到鐵路網(wǎng)站、各航空公司和汽車客運公司網(wǎng)站獲取從A市經(jīng)中轉(zhuǎn)城市B1，B2，…，Bk市到達B市的交通班次信息，經(jīng)過數(shù)據(jù)清洗，形成結(jié)構(gòu)化的數(shù)據(jù)存儲為Excel文件。返回二、設(shè)計從A市到B市耗時最少旅行路線的算法

從A市到B市耗時最少的旅行路線問題，根據(jù)獲取的從A市到B市的中轉(zhuǎn)城市B1，B2，…，Bk的班次，以及各城市各交通班次的發(fā)車時間和行駛時間等信息，采用以下的思想找出耗時最少的聯(lián)運班次問題，即算法如下：（1）分別找出能夠中轉(zhuǎn)的從A市經(jīng)B1，B2，…，Bk市到達B市的聯(lián)運班次，并計算所用的時間。（2）分別找到能夠中轉(zhuǎn)的從A市經(jīng)B1，B2，…，Bk市到達B市的聯(lián)運班次中耗時最少的聯(lián)運班次，共k條線路。（3）取k條線路中耗時最少的聯(lián)運班次為最佳旅行路線。返回三、編寫求解從A市到B市耗時最少的旅行路線問題的程序

Python語言編寫從A市到B市耗時最少的旅行路線問題的算法的程序。其中，找出能夠從A市經(jīng)Bi（i=1，2，…，k）市到達B市的中轉(zhuǎn)聯(lián)運班次，并計算所用的時間以及找到耗時最少的聯(lián)運路線的關(guān)鍵程序段如下。

返回調(diào)試運行程序在從A市到B市耗時最少的旅行路線問題中，我們分析并設(shè)計了算法和編寫了程序之后，可以快速地找出從A市到B市耗時最少的旅行路線問題的結(jié)果，如下圖所示。

算法及其描述1、算法

算法是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗地說，算法就是用計算機求解某一問題的方法，是能被機械地執(zhí)行的動作或指令的有窮集合。

若要求方程6x+5y+4z=50的正整數(shù)解的個數(shù)t，則解決問題的算法步驟如下：2、算法的特征

算法作為能確實解決某個問題的策略，具有五個方面的重要特征。有窮性。一個算法在了有窮的運算之后就必須結(jié)束。例如，在上面的算法中，x的值從1開始窮舉，重復(fù)執(zhí)行語句，直到x>8時終止執(zhí)行。確定性。算法執(zhí)行的每一個步驟必須有確切的定義，不能出現(xiàn)模棱兩可的情況。例如，上面算法步驟5。數(shù)據(jù)輸入。一個算法必須有零個或多個數(shù)據(jù)輸入，這些輸入是在算法開始之前給出的量，取自于特定的對象集合——定義域（或值域）。數(shù)據(jù)輸出。一個算法有一個或多個數(shù)據(jù)輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果，沒有輸出的算法是毫無意義的。例如，在上面的算法中，有兩個輸出，即步驟5的個數(shù)t和具體解（x、y、z的值）?？尚行?。算法中執(zhí)行的任何計算步驟都可以被分解為基本的可執(zhí)行的操作步驟，即每個計算步驟都可以在有限時間內(nèi)完成。3、算法的描述算法是對解題過程的精確描述，且需要使用某種方法將其表示出來。（1）用自然語言描述算法。用自然語言描述算法，就是用人們?nèi)粘Ｋ玫恼Z言，如漢語、英語等來描述算法。例如，從A市到B市耗時最少的旅行路線問題的算法描述，即使用了自然語言。使用自然語言描述算法比較容易掌握，但也存在明顯的缺點。例如，當算法中含有多分支或循環(huán)操作較多時，使用自然語言就很難將其清晰地表示出來。（2）用流程圖描述算法用流程圖描述算法是用程序框圖來描述算法的一種表示方法。使用流程圖描述算法，可使算法的流程描述得清晰、簡潔。流程圖的基本圖形及其功能如表3-4所示。前面的算法描述中，我們用到了順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這三種基本結(jié)構(gòu)，而任何復(fù)雜的算法都可以用這三種基本控制結(jié)構(gòu)組合來表示。1、順序結(jié)構(gòu)表示程序中的各步操作按出現(xiàn)的先后順序執(zhí)行。2、選擇結(jié)構(gòu)表示程序的處理步驟出現(xiàn)了分支，需要根據(jù)某一特定的條件選擇其中的一個分支執(zhí)行。選擇結(jié)構(gòu)有單選擇、雙選擇和多選擇三種。3、循環(huán)結(jié)構(gòu)表示程序反復(fù)執(zhí)行某個或某些操作，直到判斷條件為假（或為真）時才可終止循環(huán)。（3）用偽代碼描述算法。用偽代碼描述算法就是用介于自然語言和計算機語言之間的文字和符號來描述算法。它不用圖形符號，書寫方便，格式緊湊，易于理解，便于向計算機程序設(shè)計語言過渡。3.3計算機程序與程序設(shè)計語言

在完成問題分析和算法設(shè)計兩個環(huán)節(jié)之后，接下來就要開始編寫計算機程序?qū)?shù)據(jù)進行統(tǒng)計分析，進而形成解決問題的方案。計算機程序計算機程序是指為了得到某種結(jié)果而可以由計算機等具有信息處理能力的裝置執(zhí)行的代碼化指令序列，或者可被自動轉(zhuǎn)換成代碼化指令序列的符號化指令序列或者符號化語句序列。簡而言之，計算機程序就是指計算機可以識別運行的指令集合。常用的計算機主要包括運算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備五大基本部件。計算機內(nèi)部采用二進制形式表示和存儲指令或數(shù)據(jù)，把解決問題的程序和需要加工處理的原始數(shù)據(jù)事先轉(zhuǎn)換成二進制數(shù)，并存入存儲器中。計算機的工作過程實際上是周而復(fù)始地獲取指令、執(zhí)行指令的過程，如下圖。計算機程序設(shè)計語言在用計算機解決問題時，用自然語言、流程圖或是偽代碼所描述的解決問題的算法都不能被計算機直接執(zhí)行，還必須將算法按照一定的規(guī)則編寫成計算機能夠識別和運行的程序。而人們編寫程序時需要遵循的規(guī)則就是計算機語言規(guī)則。計算機程序設(shè)計語言，是指一組用來定義計算機程序的語法規(guī)則，通常簡稱為“編程語言”。它是一種被標準化的交流技巧，用于向計算機發(fā)出指令。正確地使用計算機程序設(shè)計語言，能讓程序員準確地定義計算機所需要使用的數(shù)據(jù)，并精確地定義在不同情況下所應(yīng)執(zhí)行的命令。計算機程序設(shè)計語言的發(fā)展，經(jīng)歷了從機器語言、匯編語言到高級語言的發(fā)展歷程。1、機器語言目前，計算機采用的物理器件主要是電子元件，但由于電子元件的物理特性，計算機只能識別“0”和“1”組成的二進制數(shù)。因此，二進制是計算機語言的基礎(chǔ)。因此，早期的程序設(shè)計語言是由“0”和“1”所表示的二進制代碼指令組表示的。這樣的語言是計算機能直接接收和執(zhí)行的，通常被稱為“機器語言”。機器語言是第一代計算機語言。這種機器語言所編寫的程序難以被理解，程序設(shè)計任務(wù)也非常繁重，而且在程序出現(xiàn)錯誤需要修改時，效率更是低下。但由于使用的是針對特定型號計算機的語言，因此它的運算效率卻是所有語言中最高的。2、匯編語言為了讓使用機器語言編寫的程序更容易被理解，人們使用了一種類似英文縮略詞且?guī)в兄浶苑柕恼Z言，來替代一個特定的二進制串，每條指令都和一條機器指令相對應(yīng)，只是指令碼和操作數(shù)都采用符號形式，這種程序設(shè)計語言就被稱為匯編語言，即第二代計算機語言。例如，指令碼用“ADD”代表加法，用“MOV”代表數(shù)據(jù)傳遞等。這樣一來，人們就會比較容易讀懂并理解程序，糾錯及維護也會變得更加方便了。但是，計算機是不能直接認識這些符號的，計算機還需要一個專門的語言翻譯器，負責(zé)將程序的每條語句都翻譯成用二進制數(shù)表示的機器語言。匯編語言編寫的程序不僅精練、質(zhì)量高，而且易于理解，所以至今在一些領(lǐng)域仍是一種常用而強有力的軟件開發(fā)工具。3、高級語言人們在使用機器語言和匯編語言這兩種語言與計算機交流的過程中，依然存在很大的障礙，而且對于程序的理解和調(diào)試仍然十分困難。于是，高級語言應(yīng)運而生。高級語言接近于數(shù)學(xué)語言和人的自然語言，并用不再過渡地依賴某種特定的機器或環(huán)境。第一種高級語言是Fortran,它主要用于科學(xué)和工程計算。在其之后，