計算機(jī)求解問題基礎(chǔ)

本章概述本章主要介紹了在利用計算機(jī)解決實際問題中常用的算法設(shè)計與分析方法，首先介紹了算法的基本概念，算法的常用表示方法，并以幾個經(jīng)典算法（枚舉法、遞推法、遞歸法、分治法）為例，詳細(xì)討論了算法分析的基本手段；其次，介紹了可視化算法設(shè)計軟件Raptor的基本使用方法和高級應(yīng)用。最后對精選案例進(jìn)行了分析和講解，并通過綜合練習(xí)加深對本章知識的理解。學(xué)習(xí)目標(biāo)(1) 理解編程思維的概念(2) 掌握可視化流程圖軟件Raptor的使用方法(3) 程序設(shè)計中的基本概念和常用數(shù)據(jù)結(jié)構(gòu)(4) 掌握程序的三種基本結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)(5) 了解解決問題的常用算法算法概述利用計算機(jī)求解問題的方法就是算法。算法一般具有以下特征：1. 有窮性（Finiteness）：算法必須能在執(zhí)行有限個步驟之后終止；2. 確切性(Definiteness)：算法的每一步驟必須有確切的定義；3. 輸入項(Input)：算法有0個或多個輸入，以刻畫運算對象的初始情況；4. 輸出項(Output)：算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果；5. 可行性(Effectiveness)：每個計算步驟都可以在有限時間內(nèi)完成，也稱之為有效性。算法的表示方法流程圖是對算法邏輯順序的圖形描述，在流程圖中常用的描述符號如下：算法的分析同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。一個算法的評價主要從時間復(fù)雜度和空間復(fù)雜度來考慮。時間復(fù)雜度：指算法需要消耗的時間資源，一般用算法中操作次數(shù)的多少來衡量。算法的時間復(fù)雜度是問題規(guī)模n的函數(shù)，一般用T(n)表示，當(dāng)問題的規(guī)模n趨向無窮大時，時間復(fù)雜度T(n)的數(shù)量級稱為算法的漸近時間復(fù)雜度。空間復(fù)雜度：指算法需要消耗的空間資源，即占用得存儲空間的大小，其計算和表示方法與時間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來表示，同時間復(fù)雜度相比，空間復(fù)雜度的分析要簡單得多。程序設(shè)計的三種基本結(jié)構(gòu)（1）順序結(jié)構(gòu)順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu)，是構(gòu)成算法框架的基礎(chǔ)部分，任何算法都包含順序結(jié)構(gòu)。順序結(jié)構(gòu)的特點就是算法以語句出現(xiàn)的先后順序從上到下依次控制執(zhí)行。流程先執(zhí)行語句塊1，再執(zhí)行語句塊2。各語句塊可以是一條或多條語句，甚至是空語句。程序設(shè)計的三種基本結(jié)構(gòu)（2）分支結(jié)構(gòu)為了解決一個較復(fù)雜的實際問題，算法需要根據(jù)某些條件做出判斷，或是有條件地執(zhí)行某一語句塊，以改變算法的執(zhí)行流向的一種程序結(jié)構(gòu)稱為分支結(jié)構(gòu)。如果條件成立則執(zhí)行語句塊1，不成立則執(zhí)行語句塊2。程序設(shè)計的三種基本結(jié)構(gòu)（2）分支結(jié)構(gòu)【例2.1】如果學(xué)生成績大于90分，則顯示“Youareagoodstudent.”，否則沒有顯示程序設(shè)計的三種基本結(jié)構(gòu)（2）分支結(jié)構(gòu)【例2.2】如果學(xué)生成績大于60分，則顯示“Youpassed.”，否則，顯示學(xué)生的姓名和“Youfailed”程序設(shè)計的三種基本結(jié)構(gòu)（3）循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)是指在算法中需要反復(fù)執(zhí)行某個功能而設(shè)置的一種結(jié)構(gòu)。它由判斷條件和循環(huán)體組成，根據(jù)判斷條件，循環(huán)結(jié)構(gòu)又可細(xì)分為以下兩種形式：當(dāng)型結(jié)構(gòu)：先判斷后執(zhí)行的循環(huán)結(jié)構(gòu)，當(dāng)條件判斷為假的時候執(zhí)行循環(huán)體，然后再次進(jìn)行條件判斷，直到條件判斷為真的時候退出循環(huán)。直到型結(jié)構(gòu)：先執(zhí)行后判斷的循環(huán)結(jié)構(gòu)，先執(zhí)行循環(huán)體，然后進(jìn)行條件判斷，當(dāng)條件判斷為假的時候再次執(zhí)行循環(huán)體，再條件判斷，直到條件判斷為真的時候退出循環(huán)。程序設(shè)計的三種基本結(jié)構(gòu)（3）循環(huán)結(jié)構(gòu)【例2.3】輸入年齡，當(dāng)輸入的年齡值不在0~130的范圍內(nèi)，則報錯并要求重新輸入，直到輸入的年齡值符合要求。典型算法1.枚舉法又稱為窮舉法、列舉法，是計算機(jī)求解問題最常用的方法之一，其核心思想就是枚舉所有的可能性。采用枚舉法解題的基本思路：(1) 確定枚舉對象、枚舉范圍和約束條件；(2) 枚舉可能的解，驗證是否是問題的解。典型算法2.遞推法應(yīng)用較為廣泛的算法之一，即通過已知條件，利用特定關(guān)系，按照一定的規(guī)律來計算序列中每個項的值，通常是通過計算前面的一些項值來得出序列中指定的后續(xù)項值。典型算法3.遞歸法實際生活中有許多這樣的問題，這些問題比較復(fù)雜，問題的解決又依賴于類似問題的解決，只不過后者的復(fù)雜程度或規(guī)模較原來的問題更小，而且一旦將問題的復(fù)雜程度和規(guī)模化簡到足夠小時，問題的解法其實非常簡單，對于這類問題，可以采用遞歸的方法進(jìn)行解決，它也算法設(shè)計中常用的一種算法。典型算法4.分治法分治法屬于計算思維中的分解方法，采取“分而治之”的思想，把一個復(fù)雜的問題分成二個或更多子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，最后通過子問題的解的合并得到原問題的解。分治法是很多高效算法的基礎(chǔ)，如排序中的快速排序、歸并排序等算法。Raptor簡介Raptor是一種可視化的算法設(shè)計環(huán)境，它允許用戶用基本流程圖符號來創(chuàng)建算法，且可以在其環(huán)境下直接調(diào)試和運行，包括單步執(zhí)行和連續(xù)執(zhí)行的模式。該環(huán)境可以直觀地顯示當(dāng)前算法的執(zhí)行過程，以及所有變量的狀態(tài)。使用Raptor設(shè)計的算法也可以直接轉(zhuǎn)換成為C++、C#、Java等高級程序語言。Raptor官網(wǎng)為/，用戶可以在該網(wǎng)站下載Raptor應(yīng)用程序，本章給出的算法示例的設(shè)計環(huán)境為Raptor4.0.5漢化版。Raptor的基本程序環(huán)境Raptor應(yīng)用程序安裝完畢后，桌面上會出現(xiàn)該應(yīng)用程序圖標(biāo)，雙擊圖標(biāo)運行程序，其主界面左邊為Raptor提供的6種基本符號，分別為輸入（Input）、賦值（Assignment）、過程調(diào)用（Call）、輸出（Output）、選擇（Selection）、循環(huán)（Loop），右邊為算法設(shè)計窗口。Raptor輸出界面為主控臺。Raptor的基本程序環(huán)境【例2.4】輸出字符串“HelloWorld”。Raptor中的語法元素1.數(shù)據(jù)類型不同的數(shù)據(jù)類型在表現(xiàn)形式、所占內(nèi)存字節(jié)長度及其取值范圍等都不相同，常用的數(shù)據(jù)類型可分為數(shù)值型和字符型。(1) 數(shù)值型數(shù)據(jù)：用來表示參與計算的數(shù)字?jǐn)?shù)據(jù)。例如：12，0.76，-23。(2) 字符型數(shù)據(jù)：用來表示不參與計算的文本數(shù)據(jù)，例如："12"，"HelloWorld"。字符型必須使用英文輸入法中的半角雙引號括起來。Raptor中的語法元素2.常量常量是指在算法運行過程中其值始終保持不變且不可改變的量。例如：PI：圓周率，定義為3.1416e：自然對數(shù)的底數(shù)，定義為2.7183true/yes：布爾值為真，定義為1false/no：布爾值為假，定義為0Raptor中的語法元素3.變量變量是計算機(jī)編程中的一個重要概念。變量是一個可以存儲值的字母或名稱。當(dāng)編程時，可使用變量來存儲數(shù)字，例如建筑物的高度，或者存儲單詞，例如人的名字。簡單地說，可使用變量表示程序所需的任何信息。而且變量可以隨著程序的運行而改變其表示的值。Raptor中的語法元素4.運算符與表達(dá)式表達(dá)式是指按一定的運算規(guī)則由運算符連接運算對象所組成的字符序列。一般可分為4類：算術(shù)表達(dá)式、字符串表達(dá)式、關(guān)系表達(dá)式和邏輯表達(dá)式。計算表達(dá)式的時候，Raptor會根據(jù)預(yù)定義的“優(yōu)先順序”執(zhí)行運算，不同的運算順序，會產(chǎn)生不同的結(jié)果，運算順序如下：計算所有的函數(shù)計算括號中的所有表達(dá)式計算乘冪(^,**)從左到右，計算乘法和除法從左到右，計算加法和減法從左到右，進(jìn)行關(guān)系運算從左到右，進(jìn)行not邏輯運算從左到右，進(jìn)行and邏輯運算，從左到右，進(jìn)行xor邏輯運算從左到右，進(jìn)行or邏輯運算。Raptor中的語法元素5.函數(shù)函數(shù)和過程都是用來完成特定功能的一段獨立模塊。在Raptor中，函數(shù)是預(yù)先編好的，由程序系統(tǒng)內(nèi)部提供的模塊。而過程是用戶自定義的模塊，又稱為“子程序”。Raptor中數(shù)據(jù)的存儲與處理1.數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)學(xué)模型，是描述數(shù)據(jù)元素及其關(guān)系的數(shù)學(xué)特性的，有時就把邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)，是在計算機(jī)存儲中的映像。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有以下四類基本的結(jié)構(gòu)：集合結(jié)構(gòu)：該結(jié)構(gòu)內(nèi)的數(shù)據(jù)之間是屬于同一集合的關(guān)系，集合的特征是集合內(nèi)數(shù)據(jù)時刻區(qū)分、無序的。線性結(jié)構(gòu)：該結(jié)構(gòu)內(nèi)的數(shù)據(jù)是一個有序數(shù)據(jù)元素的集合，每個元素有一個索引值，成意義對應(yīng)關(guān)系。樹結(jié)構(gòu)：樹結(jié)構(gòu)是具有層次的嵌套結(jié)構(gòu)，概結(jié)構(gòu)內(nèi)的數(shù)據(jù)成一對多的關(guān)系一個樹結(jié)構(gòu)的外層和內(nèi)層有相似的結(jié)構(gòu)。圖結(jié)構(gòu)：圖結(jié)構(gòu)是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)內(nèi)的數(shù)據(jù)存在多對多的關(guān)系，也稱為網(wǎng)狀結(jié)構(gòu)。圖可以表示數(shù)據(jù)元素之間的復(fù)雜關(guān)系。Raptor中數(shù)據(jù)的存儲與處理2.數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（映像）稱為數(shù)據(jù)的物理（存儲）結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示，通常一種邏輯結(jié)構(gòu)可以表示成一種多多種存儲結(jié)構(gòu)。數(shù)據(jù)元素的表示，計算機(jī)內(nèi)采用的是二進(jìn)制編碼，而數(shù)據(jù)元素之間的關(guān)系則有兩種不同的表示方法：順序映象和非順序映象，順序映像借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映像借助指示元素存儲位置的地址來表示數(shù)據(jù)元素之間的邏輯關(guān)系，并由此得到兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu):指用一段物理地址連續(xù)的存儲單元來依次存儲數(shù)據(jù)元素。鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)可以使用計算機(jī)中任意的存儲單元來存儲數(shù)據(jù)元素，存儲地址既可以是連續(xù)的，也可以是不連續(xù)的。數(shù)據(jù)結(jié)構(gòu)的設(shè)計算法的設(shè)計取決于數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)實質(zhì)上是它的邏輯結(jié)構(gòu)在計算機(jī)存儲器中的實現(xiàn)。不同數(shù)據(jù)結(jié)構(gòu)有其相應(yīng)的若干運算，通常包括結(jié)構(gòu)的生成與銷毀、在結(jié)構(gòu)中搜索滿足某條件的數(shù)據(jù)元素、結(jié)構(gòu)中插入新元素、結(jié)構(gòu)中刪除元素，以及遍歷結(jié)構(gòu)內(nèi)的數(shù)據(jù)元素等。數(shù)組數(shù)組是用一個統(tǒng)一的名稱表示的、順序排列的一組相同類型變量的集合，它本身并不是一種數(shù)據(jù)類型。數(shù)組中的變量稱為數(shù)組元素，用數(shù)字（下標(biāo)）來標(biāo)識它們，因此，數(shù)組元素又稱為下標(biāo)變量。如果一個數(shù)組的元素只有一個下標(biāo)，則稱這個數(shù)組為一維數(shù)組。例如，數(shù)組A有10個元素：A(1)，A(2)，……A(10)。如果一個數(shù)據(jù)的元素有兩個下標(biāo)，則稱這個數(shù)組為二維數(shù)組。例如，數(shù)組S(3,4)，其第一維是0到3，第二維是0到4，則這個數(shù)組共有20個元素（4*5=20），分別為：S(0,0)，S(0,1)，S(0,2)，S(0,3)，S(0,4)，S(1,0)，S(1,1)，……S(3,4)。數(shù)組【例2.6】統(tǒng)計10個學(xué)生成績的總分和平均分。分析：首先，定義一個一維的數(shù)組，用于保存學(xué)生的成績，輸入的成績?nèi)绻辉?~100之間，則需要重新輸入，然后將學(xué)生的成績加總相加得到總分，再除以10，即可得到學(xué)生的平均分。子圖使用“子圖”是實現(xiàn)結(jié)構(gòu)化程序設(shè)計思想的重要方法。結(jié)構(gòu)化程序設(shè)計思想的要點之一就是對一個復(fù)雜的問題采用“分而治之”的策略，即模塊化，把一個較大的程序劃分為若干個模塊，每個模塊只完成一個或幾個功能。在Raptor中，子圖可以將程序分解成邏輯塊，由主程序來調(diào)用它們，這樣可以簡化程序設(shè)計工作，便于流程圖的管理，減少錯誤的發(fā)生。子圖【例2.7】 創(chuàng)建一個計算半徑為3的圓面積的子圖。子程序子程序的功能與子圖類似，我們可以將子程序理解為一種“增強(qiáng)”型的子圖，子程序允許在每次被調(diào)用時，通過參數(shù)來調(diào)整運行的值，也可以將計算的結(jié)果反饋給主程序供后續(xù)使用。因而，可以看出，子圖與子程序的差別在于不能給子圖傳遞參數(shù)，子圖也不會返回任何值。子程序【例2.8】創(chuàng)建一個計算圓面積的子程序，半徑值由用戶自行輸入。圖形一個成功的程序需要有友好的界面，在界面設(shè)計中圖形是不可缺少的，可以為用戶帶來許多操作上的便利，Raptor圖形函數(shù)比較豐富，利用這些圖形函數(shù)可以設(shè)計出炫麗的界面。要使用Raptor中的圖形，必須打開一個圖形窗口。調(diào)用任何其他Raptor圖形過程或函數(shù)之前，必須創(chuàng)建此圖形窗口，打開窗口的語句為Open_graph_Window（X_Size，Y_Size），圖形窗口（X，Y）坐標(biāo)系的原點在窗口的左下角，X軸由1開始從左到右，Y軸由1開始自底向上。圖形【例2.9】繪制3個同心圓。綜合案例—閏年的判斷所指定的年份符合以下條件之一的即為閏年：(1) 能被400整除。(2) 能被4整除而不能被100整除。任意輸入一個年份判斷該年份是否為閏年，若是閏年，輸出該年份并顯示“Theyearisleapyear”的提示信息，否則輸出該年份并顯示“Theyearisn’tleapyear”的提示信息。綜合案例—神奇的數(shù)字?jǐn)?shù)學(xué)規(guī)律之神奇讓人為之感嘆！數(shù)學(xué)里有些巧合的邏輯也隱藏著神奇。例如“水仙花數(shù)”是指一個三位正整數(shù)，其各位數(shù)字的立方和等于該數(shù)本身，例如，153=13+53+33，153就是“水仙花數(shù)”。請設(shè)計算法求出100~999之間所有的“水仙花數(shù)”。綜合案例—植樹問題植樹節(jié)那天，有五位同學(xué)參加了植樹活動，他們完成植樹的棵數(shù)都不相同。問第一位同學(xué)植了多少棵時，他指著旁邊的第二位同學(xué)說：比他多植了兩棵，追問第二位同學(xué)，他又說比第三位同學(xué)多植了兩棵，如此，都說比另一位同學(xué)多植