第六講 計算思維之問題求解思想—2

1、第六講 計算思維之問題求解思想 主題一 探討問題求解過程 主題二 相關知識的認識與了解 主題三 關于算法的理解 主題四 算法策略大搜羅 主題五 幾個經(jīng)典案例的算法實現(xiàn)主題二相關知識的認識與了解 數(shù)學建模 數(shù)據(jù)結構 程序設計數(shù)學建模 我們對具體問題進行分析、抽象、歸納和推理，從中發(fā)現(xiàn)可以用數(shù)學語言來描述的關系或規(guī)律，然后把這個實際問題化成一個數(shù)學問題，這就稱為數(shù)學模型，而建立數(shù)學模型的整個過程就稱為數(shù)學建模。數(shù)學建模 數(shù)學模型的定義 數(shù)學模型（Mathematical Model）是一種模擬，是用數(shù)學符號、數(shù)學式子、程序、圖形等對實際問題本質屬性的抽象而又簡潔的刻劃，它或能解釋某些客觀現(xiàn)象，或能

2、預測未來的發(fā)展規(guī)律，或能為控制某一現(xiàn)象的發(fā)展提供某種意義下的最優(yōu)策略或較好策略。數(shù)學建模 數(shù)學模型的定義 數(shù)學建模是一種數(shù)學的思考方法，是運用數(shù)學的語言和方法，通過抽象、簡化建立能近似刻畫并“解決”實際問題的一種強有力的數(shù)學手段。 數(shù)學建模和計算機技術的相互輔佐和融合在知識經(jīng)濟時代的作用可謂是如虎添翼。數(shù)學建模 建立數(shù)學模型的方法和步驟 模型準備（問題的提出與分析）、模型假設與符號說明、模型的建立與求解、模型的分析與檢驗、模型的完善與推廣模型的完善與推廣模型的分析與檢驗模型的建立與求解模型假設與符號說明模型準備（問題的提出與分析）主題二相關知識的認識與了解 數(shù)學建模 數(shù)據(jù)結構 程序設計數(shù)據(jù)結構

3、 眾所周知，計算機的算法和程序是對信息進行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結構關系，這就是數(shù)據(jù)結構的內容。數(shù)據(jù)的結構，直接影響問題求解算法的策略選擇和程序的執(zhí)行效率。數(shù)據(jù)結構定義 數(shù)據(jù)結構的定義 數(shù)據(jù)結構（Data Structure）是計算機存儲、組織數(shù)據(jù)的方式。 數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。 一般認為，一個數(shù)據(jù)結構是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。數(shù)據(jù)結構定義數(shù)據(jù)結構的定義 數(shù)據(jù)結構主要包括三個組成成分：數(shù)據(jù)的邏輯結構，數(shù)據(jù)的物理（存儲）結構和數(shù)據(jù)的運算結構。 數(shù)據(jù)的邏輯結構 數(shù)據(jù)的邏輯結構指反映數(shù)據(jù)元素

4、之間的邏輯關系的數(shù)據(jù)結構，其中的邏輯關系是指數(shù)據(jù)元素之間的前后件關系，而與它們在計算機中的存儲位置無關。 邏輯結構有以下基本類型：集合結構、線性結構、非線性結構（樹狀結構和圖形結構）。數(shù)據(jù)結構定義數(shù)據(jù)結構的定義 數(shù)據(jù)結構主要包括三個組成成分：數(shù)據(jù)的邏輯結構，數(shù)據(jù)的物理（存儲）結構和數(shù)據(jù)的運算結構。 數(shù)據(jù)的物理結構 數(shù)據(jù)的物理（存儲）結構指數(shù)據(jù)的邏輯結構在計算機存儲空間的存放形式，是數(shù)據(jù)在計算機中的表示（又稱映像）。它所研究的是數(shù)據(jù)結構在計算機中的實現(xiàn)方法，包括數(shù)據(jù)結構中元素的表示及元素間關系的表示。 數(shù)據(jù)的存儲結構通常采用順序存儲或鏈式存儲的方法。數(shù)據(jù)結構定義數(shù)據(jù)結構的定義 數(shù)據(jù)結構主要包括三

5、個組成成分：數(shù)據(jù)的邏輯結構，數(shù)據(jù)的物理（存儲）結構和數(shù)據(jù)的運算結構。 數(shù)據(jù)結構的運算 數(shù)據(jù)的運算是數(shù)據(jù)結構的一個重要方面，討論任一種數(shù)據(jù)結構時都離不開對該結構上的數(shù)據(jù)運算及其實現(xiàn)算法的討論。 不同數(shù)據(jù)結構有其相應的若干運算。數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結構上定義的操作算法，如檢索、插入、刪除、更新和排序等。數(shù)據(jù)結構選擇意義數(shù)據(jù)結構的選擇意義 在許多類型的程序設計算法中，數(shù)據(jù)結構的選擇是一個基本的設計考慮因素。許多大型系統(tǒng)的構造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構造的質量都嚴重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結構。許多時候，確定了數(shù)據(jù)結構后，算法就容易得到了。 算法的設計取決于數(shù)據(jù)的邏輯結構，而算法的實

6、現(xiàn)依賴于數(shù)據(jù)采用的物理存儲結構。 通常情況下，精心選擇的數(shù)據(jù)結構可以給算法和程序帶來更高的運行或者存儲效率。數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構數(shù)組(Array) 在程序設計算法中，為了處理方便，把具有相同類型的若干變量按有序的形式組織起來。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構棧(Stack) 棧是只能在某一端插入和刪除數(shù)據(jù)的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。數(shù)據(jù)結構常用數(shù)據(jù)結構常用數(shù)據(jù)結構隊列(Queue) 隊列是一種特殊的線性表，它只允許

7、在表的前端（Front）進行刪除操作，而在表的后端（Rear）進行插入操作。 進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列是按照“先進先出”或“后進后出”的原則組織數(shù)據(jù)的。隊列中沒有元素時稱為空隊列。數(shù)據(jù)結構常用數(shù)據(jù)結構常用數(shù)據(jù)結構鏈表(Linked list)數(shù)據(jù)結構常用數(shù)據(jù)結構常用數(shù)據(jù)結構鏈表(Linked list) 鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，它既可以表示線性結構，也可以用于表示非線性結構。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。 鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態(tài)生成。 每個結點包括兩個部分：一個是存儲

8、數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下個結點地址的指針域。導座員3排4座小明4排1座小強4排5座小紅3排7座小麗1排2座小榮2排2座小佳2排6座小軍3排13座小宇4排9座小偉3排10座小峰Null數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構樹(Tree)校長教學副校長A分院教學副院長教學部主任家偶爾不叫事研究所所長研究所教師B分院教學副院長C分院教學副院長行政副校長A分院院長B分院院長C分院院長后勤副校長校醫(yī)院院長校食堂負責人校環(huán)境保安負責人數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構樹(Tree) 樹是包含N（N0）個結點的有窮集合K，且在K中定義了一個關系N，N滿足以下條件： 有且僅有一個結點K0，它對于關系N來說

9、沒有前驅，稱K0為樹的根結點。簡稱為根（Root）。 除K0外，K中的每個結點，對于關系N來說有且僅有一個前驅。 K中各結點，對關系N來說可以有M個后繼（M=0）。數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構圖(Graph) 圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以區(qū)別，在圖結構中常常將結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。小明小強小紅小麗小軍小峰朋友圈數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構堆(Heap)745顆糖果320顆糖果135顆糖果50顆糖果20顆糖果（原始袋）30顆糖果（原始袋）85顆糖果40顆糖果（原始袋）45顆糖果（原

10、始袋）185顆糖果90顆糖果（原始袋）95顆糖果（原始袋）425顆糖果205顆糖果100顆糖果（原始袋）105顆糖果（原始袋）225顆糖果 110顆糖果（原始袋）115顆糖果（原始袋）有10袋糖果，兩兩合并裝到一個新袋子中，按每次確保糖果數(shù)最少的策略來組合合并裝袋。數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構堆(Heap) 堆是一種特殊的樹形數(shù)據(jù)結構，每個結點都有一個值。 通常我們所說的堆的數(shù)據(jù)結構，是指二叉堆。 堆的特點是根結點的值最?。ɑ蜃畲螅?，且根結點的兩個子樹也是一個堆。 堆總是一顆完全樹。數(shù)據(jù)結構常用數(shù)據(jù)結構常用數(shù)據(jù)結構散列表(Hash)數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構散列表(Hash)3排

11、4座（304房號）小明4排1座（401房號）小強4排5座（405房號）小紅3排7座（307房號）小麗1排2座（102房號）小榮2排2座（202房號）小佳2排6座（206房號）小軍3排13座（313房號）小宇4排9座（409房號）小偉3排10座（310房號）小峰數(shù)據(jù)結構常用數(shù)據(jù)結構 常用數(shù)據(jù)結構散列表(Hash) 散列表是根據(jù)關鍵碼值（Keyvalue）而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。 這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。由此，不需比較便可直接取得所查記錄。主題二相關知識的認識與了解 數(shù)學建模 數(shù)據(jù)結構 程序設計

12、程序設計在運用計算思維理念求解問題時，雖然需要經(jīng)歷分析抽象出數(shù)學模型、選擇合適的數(shù)據(jù)結構以及整理歸納出解題算法等一系列階段過程，但最終都要將算法轉換成計算機可計算執(zhí)行的計算機程序，經(jīng)過程序的編輯和運行并進行測試、調整直至問題得到最終解答。程序設計計算機程序計算機程序 計算機程序（Computer Program）就是按照實際解決問題的算法步驟而事先編制好的、具有特殊功能的指令序列。序列由一串CPU能夠識別并執(zhí)行的基本指令組成，每一條指令規(guī)定了計算機應該進行什么操作（如加、減、乘、除、判斷等）及操作需要的有關數(shù)據(jù)。計算機程序主要涉及兩部分內容，即數(shù)據(jù)的描述和數(shù)據(jù)的處理。 數(shù)據(jù)的描述是指各種變量的

13、定義，也稱數(shù)據(jù)結構描述； 數(shù)據(jù)的處理是指對變量的操作，這些操作按解決問題的步驟要求有一定的先后順序和規(guī)則，也稱為求解算法。程序設計計算機程序計算機程序 算法是程序的核心，它在程序編制、軟件開發(fā)及整個計算機科學中占據(jù)重要地位。 數(shù)據(jù)結構是算法加工的對象，一個程序要進行計算或處理總是以某些數(shù)據(jù)為對象的，要設計一個好的程序就需要將這些數(shù)據(jù)按要求組成合適并高效的數(shù)據(jù)結構。 所以，可以說：數(shù)據(jù)結構+計算算法=程序數(shù)據(jù)結構計算算法程序程序設計計算機程序設計計算機程序設計 計算機程序設計（Computer Programming）是指設計、編制、調試程序的方法和過程。 程序設計通常分為問題建模，算法設計，編

14、寫代碼，編譯調試和整理并寫出文檔資料五個階段。 程序設計過程就是通過分析問題、確定算法、編程求解等步驟來解決問題的過程，其中，算法具有重要的作用，它能夠提供一種思考問題的方向和方法。程序設計計算機程序設計計算機程序設計 在計算機中，把解決具體問題的過程準確完整地描述出來就形成解決該問題的算法。 在程序設計中，我們要考慮數(shù)據(jù)的結構和類型、變量的定義，要用到算法語句，要考慮使用順序結構、選擇結構和循環(huán)結構來控制程序等等，最終將一個具體的實際問題用程序設計語言表示出來并由計算機去執(zhí)行完成。程序設計程序設計語言程序設計語言 程序設計語言（Programming Language）是用來編寫計算機程序的

15、語言，是用戶與計算機交流信息的工具。 程序設計語言的發(fā)展過程是伴隨整個計算機技術的發(fā)展而進行，從最初的機器語言到匯編語言，再到各種結構化的高級語言，最后到支持面向對象技術的面向對象語言。這個發(fā)展過程，使程序設計者更容易學習掌握語言，能以更接近問題本質的方式去思考和描述問題。 常用高級語言包括：C語言系列（C+、C#、基本C）、JAVA語言、Visual BASIC語言等。程序設計程序構成元素 程序構成元素 雖然各種高級程序設計語言的應用領域不同，功能和風格也存在差異，但是一門語言所包含的主要內容卻是類似的，程序設計語言的程序代碼組成元素一般包括： 數(shù)據(jù)類型 語言元素 控制結構 程序模塊等程序設

16、計程序構成元素 程序構成元素控制結構循環(huán)結構選擇結構順序結構語句元素表達式運算符常量變量函數(shù)賦值程序設計程序構成元素數(shù)據(jù)類型 計算機使用數(shù)據(jù)類型的目的是： 決定了該類型數(shù)據(jù)在計算機中的存儲與表示方式； 決定了該類型數(shù)據(jù)的取值范圍； 決定了該類型數(shù)據(jù)所能執(zhí)行的操作； 不同程序設計語言所提供的數(shù)據(jù)類型的種類是不盡相同的。 提供的數(shù)據(jù)類型越多，解決處理實際問題時就方便容易，但這也增加了學習編程的難度。程序設計程序構成元素數(shù)據(jù)類型 數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。 在計算機中，數(shù)據(jù)就是各種數(shù)字、字符及所有能輸入到計算機中，并能被計算機識別和處理的符號的集合。 常用的數(shù)據(jù)類型一

17、般有：整數(shù)類型、浮點數(shù)類型、字符類型、邏輯類型、指針類型、數(shù)組類型、記錄類型、枚舉類型、集合類型和文件等。程序設計程序構成元素數(shù)據(jù)類型 一方面，在程序設計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算。可以認為，數(shù)據(jù)類型是在程序設計中已經(jīng)實現(xiàn)了的數(shù)據(jù)結構。 另一方面，在程序設計過程中，當需要引入某種新的數(shù)據(jù)結構時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結構。程序設計程序構成元素語言元素 高級程序設計語言使用我們的日常文字、數(shù)學符號和表達式來書寫程序，內容包括字母符號、數(shù)字符號、變量、常量、表達式、運算符、特殊字符和標準函數(shù)等。

18、這些用來表示書寫程序的符號就是程序設計語言中的語言元素，不同的程序設計語言所使用的語言元素是不盡相同的，但基本一致。掌握和理解程序設計語言中的語言元素是正確書寫程序的基礎。程序設計程序構成元素語言元素變量 變量實際上是內存中的一個臨時存儲區(qū)域的編號或別名，用于存放程序中的數(shù)據(jù)和結果，是程序的基本操作對象。 程序設計時根據(jù)實際要求必須先定義好所需的變量，明確變量的類型和名稱，程序運行時，語言處理程序根據(jù)定義好的變量數(shù)據(jù)類型，會在內存分配相應的存儲空間，用于存放該變量的值。程序設計程序構成元素語言元素運算符 計算機可以進行各種運算，包括算術運算、邏輯運算、關系運算、字符運算和特殊運算。不同的程序設

19、計語言提供的運算符種類不同，表示形式也可能不同。一般有： 算術運算加、減、乘、除、整除和求余等； 字符運算合并字符串、取子字符串等。 關系運算大于、大于等于、小于、小于等于、等于、不等于等。 邏輯運算與、或、非等。程序設計程序構成元素語言元素標準函數(shù) 一般高級程序設計語言都提供許多常用的標準函數(shù)，供用戶在程序中直接使用。這些標準函數(shù)實際上就是為完成某一特定任務而專門設計的一段程序。 標準函數(shù)一般分為：數(shù)學函數(shù)、字符串函數(shù)、類型轉換函數(shù)、隨機數(shù)函數(shù)、日期和時間函數(shù)和文件函數(shù)等。程序設計控制結構控制結構 通常，結構化的程序設計都包括順序結構、選擇結構和循環(huán)結構三類，它們構成了程序的主體。只是不同的

20、程序設計語言，具體表示的語句命令形式有所不同。程序設計控制結構 控制結構 在實際的應用程序開發(fā)中，順序結構、選擇結構和循環(huán)結構往往是綜合在一起的使用的，從總體看一個應用程序可能很龐大很復雜，但如果從局部看卻都是由這三種基本結構的嵌套和組合而成。程序設計控制結構控制結構順序結構順序結構是指程序的執(zhí)行按語句的排列順序從上到下依次執(zhí)行，每條語句均被執(zhí)行一次，直至結束。其為最常用、最簡單、最基本的控制結構?？刂平Y構選擇結構選擇結構是指程序中的某些語句的執(zhí)行會受到某一條件的制約，當條件成立時，執(zhí)行一部分語句，否則執(zhí)行另外一些語句，也就是說，有些語句可能被跨過未被執(zhí)行。選擇結構又可分為：二路分支結構和多路

21、分支結構。程序設計控制結構控制結構循環(huán)結構 循環(huán)結構是指程序中的某些語句在某一條件成立時，需要重復執(zhí)行，直到條件不成立時，才結束重復執(zhí)行。 循環(huán)結構要特別注意的是在重復執(zhí)行語句過程中，要有控制條件的語句，以避免出現(xiàn)死循環(huán)現(xiàn)象。程序設計程序過程模塊程序過程模塊 從軟件開發(fā)的角度，一個功能豐富繁多、規(guī)模龐大復雜的項目，通常需要團隊的合作，才能最大限度的縮短軟件開發(fā)研制的周期。 同時，為了使整個程序結構清晰明了，避免代碼冗余率，便于程序的調試維護和代碼重復使用，通常會根據(jù)應用程序的規(guī)模和功能，將問題總體模塊劃分為若干個相對獨立的子模塊，使其中每個部分解決一個相對簡單的功能。程序設計程序過程模塊程序過

22、程模塊 簡單地說，這種程序設計思想就是“自頂向下、化整為零、逐步細化”的設計方法，即把一個龐大復雜的程序劃分成若干個功能相對簡單的子模塊，這些子模塊之間盡可能彼此獨立，然后再通過過程調用語句把這些子模塊聯(lián)系起來，最終形成一個完整的程序。項目總模塊項目分模塊1項目子模塊11項目子模塊12項目分模塊2項目子模塊21項目子模塊22項目子模塊23項目分模塊3項目子模塊31項目子模塊32項目分模塊4項目子模塊41項目子模塊42項目子模塊43項目子模塊44項目子模塊45程序設計程序過程模塊程序過程模塊 一個子程序即為一個程序模塊。一個程序模塊可以借助調用的方法與其他程序模塊來建立彼此的聯(lián)系，進而完成整個程

23、序功能。 這種程序設計的方法，稱為模塊化的程序設計高級程序設計語言都提供設計子程序模塊的功能，一般將子程序模塊稱為過程或函數(shù)。 過程和函數(shù)的主要區(qū)別是過程沒有返回值，函數(shù)可帶回返回值。過程和函數(shù)需要先定義設計好后，才能被主程序調用。程序設計程序過程模塊 程序過程模塊程序設計程序設計方法程序設計方法結構化程序設計 結構化程序設計（Structured Programming）是一種程序設計的原則和方法。用幾種標準的控制結構（順序、分支和循環(huán)）通過重復和嵌套來表示。 結構化程序設計思想采用“自頂向下、逐步求精”的方法。按結構化程序設計的要求設計出的高級程序設計語言稱為結構化程序設計語言。 利用結構化程序設計語言，或者說按結構化程序設計思想編寫出來的程序稱為結構化程序。結構化程序具有結構清晰、容易理解、容易修改、容易驗證等特點。缺點就是代碼的可重用性差；可維護性差；穩(wěn)定性差；難以實現(xiàn)。程序設計程序設計方法程序設計方法面向對象程序設計 面向對象程序設計（Object Oriented Programming，OOP）是一種計算機編程架構。OOP的一條基本原則是計算機程序是由單個能夠起到子程序作用的單元或對象組合而成。OOP達到了軟件工程的三