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

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

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

計(jì)算機(jī)解決問題的過程1、分析問題

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

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

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

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

我們從鐵路公司、各航空公司和汽車客運(yùn)公司網(wǎng)站得知，直達(dá)B市的交通工具只有火車和汽車兩種，出發(fā)地有B1，B2，…，Bk市（沒有A市），從A市出發(fā)到B1，B2，…，Bk市的交通工具有飛機(jī)、火車和汽車三種，這樣從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市的交通班車（班機(jī)）數(shù)共有：S=M1×N1+M2×N2+…+Mk×Nk尋找從A市到B市耗時(shí)最少的旅行路線問題就轉(zhuǎn)化為在S種聯(lián)運(yùn)班次中找到一種耗時(shí)最少的聯(lián)運(yùn)班次。這樣就需要遍歷每一個(gè)班次進(jìn)行比較，人工方式找到能夠中轉(zhuǎn)且等待時(shí)間和行駛時(shí)間最少的班次，工作量極其浩大！假設(shè)從A市到B市的中轉(zhuǎn)城市只有B1，B2市，從A市經(jīng)B1，B2市到B市的交通情況如表3-2和表3-3所示。于是，從A市經(jīng)B1市到B市的聯(lián)運(yùn)班次有7×9=63班；從A市經(jīng)B2市到B市的聯(lián)運(yùn)班次有12×9=108班，合計(jì)為S=63+108=171班。然后在171班次中找到能夠中轉(zhuǎn)且等待時(shí)間加上行駛時(shí)間最少的聯(lián)運(yùn)班次，如下圖所示。

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

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

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

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

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

算法及其描述1、算法

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

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

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

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