計算思維導論05-問題求解的基本思維課件

1、5問題求解的基本思維天津科技大學計算機公共基礎系1目 錄5.1 計算機語言5.2 程序設計基礎5.3 算法5.4 算法設計5.5函數與遞歸5.6程序設計5.1 計算機語言計算機語言是語法、語義與詞匯的集合，它用來表達計算機程序。程序是指某種程序設計語言編制的、計算機能夠執(zhí)行的指令序列，表達的是讓計算機求解問題的步驟和方法。計算機語言的發(fā)展過程經歷了四個階段：機器語言匯編語言高級語言構件化語言1機器語言計算機的指令系統(tǒng)是指一組能夠識別和執(zhí)行的二進制和編碼表達的指令集合。使用二進制編碼的指令編寫程序的語言被稱為機器語言。2匯編語言匯編語言使用助記符來代替機器語言的指令碼，使機器語言符號化，從而提高

2、編程效率。如加法表示為ADD，指令“ADD A, 9”的含義是將A寄存器中的數與9相加，并將結果存入A中。使用匯編語言的助記符編寫的程序稱為匯編語言源程序。3高級語言與編譯器高級語言是類似于自然語言、以語句和函數為單位書寫程序的編程語言。高級語言編寫的程序稱為高級語言源程序。編譯器先使用其編譯程序將高級語言源程序轉換為匯編語言源程序，再由匯編程序將匯編語言源程序轉換為機器可執(zhí)行的二進制語言程序。4構件化的語言構件化的語言的每一個構件都是由一系列語句完成的復雜程序，能夠完成一定功能。構件化的語言，包括Visual Basic、Visual C+、Delphi，.Net等5編程語言的分層結構編程語

3、言的分層結構思維，以下層語言為基礎，再定義一套能力更強的新語言和編譯器。人們使用新語言高效率地編寫程序，使用編譯器將其編譯成下層語言能識別的源程序。編譯器將上級語言的源程序一層層向下翻譯，直到最終得到機器語言程序，計算機就可以執(zhí)行程序。6Java虛擬機Java是一種面向對象的編程語言Java源程序，編譯后會生成一種 .class 文件，稱為字節(jié)碼文件Java虛擬機（Java Virtual Machine，簡稱 JVM）負責將字節(jié)碼文件翻譯成特定平臺下的機器碼然后運行。只要在不同平臺上安裝對應的JVM，就可以運行JAVA字節(jié)碼文件5.2 程序設計基礎程序設計的本質：程序設計與計算機的組成有密切

4、關系，程序設計的本質是設計能夠利用計算機的5個部件完成特定任務的指令序列?！纠?.1】用鍵盤輸入價格與斤數，計算櫻桃的總價。Private Sub Command1_Click() Dim price As Single, number As Single, total As Single price = Val(Text1.Text) 輸入櫻桃價格 number = Val(Text2.Text) 輸入櫻桃斤數 total = price * number 計算總價錢 Text3.Text = total 輸出總價錢End Sub2常量常量指在程序運行過程中值不能改變的量，通常是固定的數值或

5、字符。（1）數值型：40, -40 , 0, 123.456。（2）字符型：Hello wolrd! 。（3）邏輯型：真 為True，假為False。 3變量在程序運行過程中，其值可以改變的量稱為變量。變量占據內存中的一塊存儲單元，用來存放數據，存儲單元中的數據可以改變。給存儲單元起的名字，就是變量名4算術運算符算術運算符的作用是進行算術運算，用算術運算符將運算對象連接起來的表達式稱為算術表達式。算術運算符數學表達式編寫成Visual Basic表達式為：(a + b) 4 / (a * (b + c)5關系運算符關系運算符用于比較兩個操作數的關系，用關系運算符連接兩個表達式稱為關系表達式若關

6、系成立，則表達式值為True，否則為False。6邏輯運算符邏輯運算符用于對操作數進行邏輯運算，用邏輯運算符連接關系表達式或邏輯值稱為邏輯表達式。邏輯表達式的結果為True或False5.3 算法算法是解決一個問題所采取的一系列步驟。著名的計算機科學家Nikiklaus Wirth提出如下公式：程序=數據結構+算法算法給出了解決問題的方法和步驟，是程序的靈魂，決定如何操作數據，如何解決問題。5.3.2 算法舉例【例5.2】 求1+2+3+4+100。（1）“1+2+3+4+5+6+100”，不可行（2）可行： 算法舉例【例5.3】編寫英里與公里轉換程序，輸入英里數，轉換為千米數輸出。step1

7、: 輸入英里數 milesstep2: kms=0.621*milesstep3: 輸出 公里數kmsstep4: 結束啟發(fā)：判斷算法是否正確的方法：跟蹤上述算法的執(zhí)行過程，理解變量的作用、程序設計時可用的部件和功能，驗證算法的正確性。5.3.3 算法的表示1自然語言eg：求兩個數的最大值如果A大于B，那么最大值為A，否則最大值為B自然語言表示算法時拖沓冗長，容易出現歧義，因此不常使用。2偽代碼偽代碼用介于自然語言和計算機語言之間的文字和符號來描述算法。if A大于B then 最大值為A else 最大值為B偽代碼的描述方法比較靈活，修改方便，易于轉變?yōu)槌绦颍钱斍闆r比較復雜時，不夠直觀，

8、而且容易出現邏輯錯誤。3傳統(tǒng)流程圖流程圖表示算法比較直觀，它使用一些圖框來表示各種操作，用箭頭表示語句的執(zhí)行順序。4N-S流程圖N-S流程圖又稱盒圖，其中所有結構都用方框表示。算法的特性算法應該具有以下特性才可以正確執(zhí)行：（1）有窮性。（2）確定性。（3）輸入。0個或者多個輸入。（4）輸出。（5）可行性。5.3.4 算法類問題算法類問題是指那些可以由算法解決的問題。計算學科中有許多著名的算法類問題，如哥尼斯堡七橋問題、旅行商問題等。算法類問題算法類問題求解的第一步是數學建模。數學建模是一種基于數學的思維方式，運用數學的語言和方法，通過抽象和簡化建立對實際問題的描述和定義數學模型。將現實世界的問

9、題抽象成數學模型，可以發(fā)現其本質以及能否求解，找到求解問題的方法和算法。算法類問題【例5.4】哥尼斯堡七橋問題。尋找走遍這7座橋并最后返回原點且只允許每座橋走過一次的路徑。哥尼斯堡七橋問題數學建模：去除哥尼斯堡七橋問題的無關語義，將其抽象成由節(jié)點和連接節(jié)點的邊構成的圖哥尼斯堡七橋問題的本質是從任一節(jié)點開始，經過每條邊一次且僅一次的回路問題。哥尼斯堡七橋問題大數學家歐拉把它轉化成“一筆畫問題”，推斷如下：除了起點以外，當一個人由一座橋（邊）進入一塊陸地（節(jié)點）時，他同時也由另一座橋離開此節(jié)點。所以每行經一點時，計算為兩座橋（或線），從起點離開的線與最后回到開始點的線也計算兩座橋，因此每一個陸地與

10、其他陸地連接的橋數必為偶數。哥尼斯堡七橋問題七橋問題所構成的圖中，沒有一個節(jié)點含有偶數條邊，所以哥尼斯堡七橋問題無解。旅行商問題【例5.5】旅行商問題（Traveling salesman problem，TSP）：給定一系列城市和每對城市之間的距離，求解一條最短路徑，使得一個旅行商從某個城市出發(fā)訪問每個城市且只能在每個城市逗留一次，最后回到出發(fā)的城市。旅行商問題TSP抽象的數學模型如下：任意兩個城市 和 之間的距離為TSP問題的本質是尋找城市的訪問順序旅行商問題采用遍歷策略，求出TSP問題中所有可能路經及其總里程，從中選出總里程最短的路徑。4個城市的遍歷解：22222226665555444

11、4333路徑：ABCDA 距離：12路徑：ABDCA 距離：14路徑：ACBDA 距離：18路徑：ACDBA 距離：14路徑：ADBCA 距離：14路徑：ADCBA 距離：12旅行商問題解空間：共有3*2*1= 6條可選路經，最短路徑為 和 ，最短距離為12。旅行商問題遍歷策略對于小規(guī)模的TSP問題是有效的，但是對于大規(guī)模的TSP問題則不可行。n個城市的組合路徑數為 (n-1)!20個城市組合路徑為隨著城市數目的增長其組合路徑數呈組合爆炸，即組合路徑數以階乘方式急劇增長，以至于無法計算。求解策略，包括貪心算法、分治法、動態(tài)規(guī)劃、啟發(fā)式算法等旅行商問題貪心算法策略的的基本思想是，一定做出當前狀況

12、的最好選擇，以免將來后悔。求解TSP問題的貪心算法為：“從一個城市開始，每次選擇下一個城市的時候，只考慮當前狀況下最好的選擇”根據貪心算法的策略，解為路徑： 其總距離為14。貪心算法求得的并非最優(yōu)解，而是可行解?？尚薪馀c最優(yōu)解相比，差距不大，已經足夠短。5.3.5 算法分析1算法的正確性算法的正確性是指問題求解的過程、方法是否正確，輸出結果是否正確。算法分析2算法的復雜性（1）算法的時間復雜性如果一個問題的規(guī)模為n，算法運行的時間記為T(n) O記法表示算法的時間復雜性求解TSP問題的貪心算法的時間復雜度為 算法分析（2）算法的空間復雜性算法的空間復雜性，指的是算法在執(zhí)行過程中所占用的存儲空間

13、的大小，用S(n)表示。5.4 算法設計1966年，Bohra和Jacopini提出：結構化程序設計方法的三種基本結構包括順序結構、選擇結構和循環(huán)結構已經證明，用三種基本結構可以組成解決所有編程問題的算法。5.4.1 順序結構順序結構按照語句的先后順序執(zhí)行程序，它是程序設計中最簡單的控制結構。順序結構【例5.6】設計算法，輸入三角形的3條邊長a、b和c，求三角形的面積。1分析根據數學知識，在已知三角形的3條邊時可以使用海倫公式來求其面積，即順序結構2算法設計順序結構【例5.7】求解雞兔同籠問題。已知籠子中雞和兔的頭數總共為h，腳數總共為f，問雞和兔各有多少只？（1）分析。5.4.2 選擇結構選

14、擇結構用于判斷給定的條件，根據判斷的結果來控制程序的流程?！纠?.8】輸入a、b值，輸出其中較大的數。（1）輸入變量a和b。（2）如果ab為真，則轉入（3），否則轉入（4）。（3）輸出a，轉入（5）。（4）輸出b，轉入（5）。（5）結束。選擇結構【例5.9】輸入x，求函數 的值。5.4.3 循環(huán)結構循環(huán)結構是用于實現同一段程序多次執(zhí)行的一種控制結構?！纠?.10】 求100!，即123100。step1: p=1 step2: i=2 step3: p=p i step4: i=i+1 step5: 如果i=100，那么轉入step3執(zhí)行 step6: 輸出p，算法結束循環(huán)結構【例5.11】輸

15、入整數n，求 1*2*3*n。step0: 輸入nstep1: p=1step2: i=2step3: p=p*istep4: i=i+1step5: 如果i=n，那么轉入step3執(zhí)行step6: 輸出p，算法結束循環(huán)結構For Next循環(huán)For Next循環(huán)是計數型循環(huán)，主要用于循環(huán)次數已知的情況，它的本質是當型循環(huán)。For = To Step Exit For 退出循環(huán)Next 循環(huán)變量窮舉法窮舉法又稱枚舉法，它的基本思路就是一一列舉所有可能性，逐個進行排查。窮舉法的核心是找出問題的所有可能，并針對每種可能逐個進行判斷，最終找出問題的解。窮舉法【例5.12】百錢買百雞問題。假定公雞每只

16、2元，母雞每只3元，小雞每只0.5元。現有100元，要求買100只雞，編程求出公雞只數x、母雞只數y和小雞只數z。5.4.4 數組數組，也稱線性表（linear list）是一種數據結構，一個數組是n個具有相同特性的數據元素的有限序列。數組的相鄰元素之間存在著序偶關系每一個元素實際就是一個變量，可以賦值、輸入、輸出或參加各種運算。數組數組的處理實際上就是處理數組元素的過程，按順序對每個數組元素進行處理的過程稱為數組的遍歷1搜索在數組中，查找滿足條件的所有元素，并求和、計數等。算法設計：遍歷數組元素的過程中，判斷每個元素是否滿足條件，如滿足條件則做出處理?！纠?.13】一維數組中查找滿足條件（元

17、素能被4整除）的所有元素，統(tǒng)計個數、和及其平均值。2求最大值【例5.14】求一維數組中100個元素的最大值。3排序排序是最常見的問題，其本質是對一組對象按照某種規(guī)則進行有序排列的過程。在計算科學中，排序是許多復雜問題求解的基礎?！纠?.15】用“起泡法”把一維數組的n個元素按從小到大的順序排列并輸出。排序排序【例5.16】用選擇法把一維數組的n個元素按從小到大的順序排列并輸出。排序排序算法的比較：冒泡法排序每輪依次比較兩個相鄰元素，如果前大后小則交換；而選擇法排序則每輪次找到最小值，做一次交換。兩種算法的時間復雜度都為。排序快速排序：從序列中任意取出一個元素作為中心，所有比它小的都放在左側，比

18、它大的都放在右側，形成左右兩個序列；再對各子序列重新選擇中心元素依照規(guī)則；直到每個子序列只剩下一個元素排序問題的解決方法還有插入排序、桶排序、基數排序、堆排序等。5.5函數與遞歸函數是由多條語句組成的能夠實現特定功能的程序段，函數可以對程序進行模塊化。函數一般包括函數名、參數、返回值和函數體四個部分。函數【例5.17】輸入的兩個變量，使用函數計算兩個變量的和。int sum(int x, int y)int z;z=x+y;return z;main()int s,m,n;printf(請輸入兩個整數);scanf(%d%d,&m,&n);s=sum(m,n);printf(和為 %d,s);

19、5.5.2 遞歸遞歸是一種重要的計算思維模式，既是抽象表達的一種手段，也是問題求解的重要方法。遞歸故事：“從前有座山，山里有座廟，廟里有個老和尚在講故事，故事是（從前有座山，山里有座廟，廟里有個老和尚在講故事，故事是（從前有座山，山里有座廟，廟里有個老和尚在講故事，故事是(）”遞歸使用遞歸的方法繪制的圖形遞歸算法遞歸算法的基本思想是將一個大規(guī)模的復雜問題，層層轉換為一個與原問題相同但是規(guī)模較小問題來求解，函數調用函數本身、高階調用低階。使用遞歸的方法進行問題求解的基礎是構造遞歸函數。遞歸算法【例5.18】用遞歸算法求n!。分析：（1）觀察可知：n!=n* (n-1)!，(n-1)!=(n-1)

20、 * (n-2)!，3!=3*2!，2!=2*1!，1!=1。（2）n！可以表示為以下分段函數遞歸算法（3）假設fact(n)用于計算n的階乘，則遞歸函數fact(n)表示為遞歸算法Private Sub Command1_Click() Text1.Text = fact(10)End SubFunction fact(n As Integer) As Double 遞歸函數fact() Dim s As Double If n = 0 Or n = 1 Then s = 1 Else s = n * fact(n - 1) 遞歸調用fact() End If fact = sEnd Fun

21、ction遞歸算法遞歸過程可以總結為以下兩個階段。1回推階段：n!(n-1)!(n-2)!(n-3)!3!2!1!。2遞推階段：n!(n-1)!(n-2)!(n-3)!3!2!1!。遞歸算法【例5.19】漢諾塔（Hanoi）問題是這樣的問題，有3根柱子A、B和C，開始A柱上有64個盤子，從上到下，依次大一點，如圖5-36所示，把所有盤子移到C柱上，要求：盤子必須放在A、B或C柱上，一次只能移動一個盤子，大盤子不能放在小盤子上邊。遞歸算法分析：3個盤子 7次；4個盤子 15次；5個盤子 31次；6個盤子 63次；64個盤子。經過實驗可知，當盤子為n個時，需要 次移動盤子。遞歸算法將n個盤子從A移

22、動到C的問題，遞歸過程歸納如下。（1）如果將n個盤子從a，通過b移動到c，計作函數Hanoi(n，a，b，c)。（2）遞歸函數過程：if n=1 then 直接從a移動到c，Move (a，c)。if n1 then 將n-1個盤子從a通過c移到b，Hanoi(n-1，a，c，b)，第n個盤子從a移到c，Move (a，c)，再將n-1個盤子從b通過a移到c，Hanoi(n-1，b，a，c)。遞歸算法Private Sub Command1_Click() Call Hanoi(5, a, b, c)End SubPrivate Sub Hanoi(n As Integer, a As Str

23、ing, b As String, c As String) 遞歸函數Hanoi() If n 1 Then Call Hanoi(n - 1, a, c, b) Call Movem(a, c) 第n個盤子從a 移動到 c Call Hanoi(n - 1, b, a, c) Else Call Movem(a, c) End IfEnd SubPrivate Sub Movem(x As String, y As String) Print x, -, yEnd Sub5.6程序設計本節(jié)以Visual Basic為例，介紹程序設計的一般方法。程序設計對象是實體的邏輯模型，一個實體就是一個對

24、象。如一輛汽車、一個氣球、一部電腦等。類是將多個對象共有的特征抽取出來，形成這些對象的抽象模型。類是對象的抽象，而對象是類的實例。程序設計對象包括屬性、方法和事件：（1）屬性：性是對象的性質，即用來描述和反映對象特征的參數。例如，汽車有排氣量，顏色等（2）方法：對象自身可以進行的動作或行為，是對象自身包含的功能。例如打開車燈、鳴笛等。（3）事件：預先設置好的，可以被對象觸發(fā)的動作。只要用戶設計好了某個事件的代碼，對象在響應了該事件后，就會執(zhí)行相應代碼。5.6.2 Visual Basic編程Visual Basic的類和對象：（1）類：工具箱中的標準控件類（2）對象：用戶在窗體上放置一個控件就

25、是創(chuàng)建該控件類的一個對象Visual Basic編程（3）屬性：Visual Basic程序中的對象都有自己的屬性Visual Basic編程（4）事件過程：為對象的事件編寫程序，如Click、DblClick等Visual Basic編程【例5.20】編寫程序，輸入三角形的三條邊長a、b和c，求三角形的面積。Visual Basic編程Private Sub Command1_Click() Dim a As Single 定義變量 Dim b As Single Dim c As Single Dim s As Single Dim area As Single a = Val(Text_a.Text) 輸入邊,并轉換為數字 b = Val(Text_b.Text) c = Val(Text_c.Text) s = (a + b + c) / 2 計算周長 area = Sqr(s * (s - a) * (s - b) * (s - c) 計算面積 Text_area.Text = area 輸出End SubVisual Basic編程程序調試：掌握正確的調試程序方法，能夠迅速有效地發(fā)現和