第三章計算思維和計算機軟件基礎3.1計算思維概述解決問題的常用算法3.2程序與程序設計語言3.33.4軟件的特性和常用軟件本章內容導讀計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。通過學習本章，讀者應掌握以下內容：理解思維、科學思維、計算思維之間的聯系。理解計算的含義，掌握計算思維的本質和特征。理解算法的基本知識，掌握算法的基本表示方法。理解求解問題的基本方法、典型問題的求解策略。掌握程序、程序設計語言的概念、特點、應用領域。理解軟件的概念、分類、特性和知識產權保護的知識。理解通用應用軟件的分類和功能。3.1.1計算思維的基本概念思維:人類在實踐活動中，人腦對客觀現實世界的認知或智力活動。思維具有概括性、間接性和能動性的特點:思維的概括性:在人的感知基礎上，能將一類事物的共同的、本質的特征和規律抽取出來。思維的間接性:人們借助于一定的媒介和知識經驗對客觀事物進行間接認識，從而揭示事物的本質和規律思維的能動性:能認識和反映客觀世界，還能對客觀世界進行改造。3.1計算思維概述3.1.1計算思維的基本概念科學思維：思維的一種類型，是人類科學活動中所使用的思維方式；具有嚴謹性與科學性；科學思維:分為理論思維、實驗思維和計算思維；理論思維又稱為邏輯思維，是指以科學的原理、概念為基礎來解決問題的思維活動，具有推理和演繹的特征。實驗思維是通過觀察、實驗和歸納自然（包括人類社會活動）規律的思維活動，把觀察、歸納和推理完美地結合起來。計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、以及人類行為理解等涵蓋計算機科學之廣度的一系列思維活動。

計算思維是與形式化問題及其解決方案相關的思維過程，其解決問題的表示形式應該能有效地被信息處理代理執行。3.1.2計算思維的本質和特征計算思維本質：研究計算的，研究在解決問題過程中，哪些是可計算的，以及如何計算。計算的含義：指根據已知量算出未知量，即運算的意思；考慮、謀慮的意思。計算的實現：運算表達式：算術運算、邏輯運算、集合運算算法描述、編程實現很多看似不可計算的東西，如果能用嚴謹的數學符號或式子去描述解決過程的時候都能變得可計算。3.1.2計算思維的本質和特征計算思維的重要特征：抽象化、自動化和普適性。抽象化：建立計算過程模型；自動化：計算過程模型能被有效自動執行；普適性：通過計算科學探索可用的計算模型。七橋問題用電子地圖搜索最優路線3.2.1算法概述算法：解決問題的方法與步驟。例如，有三個外觀一樣的硬幣A、B和C，其中一個是假幣，兩個是重量相同的真幣，假幣在重量上與真幣有差異?，F提供一架天平秤，如何找出假幣？3.2解決問題的常用算法3.2.1算法概述在計算機學科中，算法是指用于完成某個信息處理任務的有序而明確的、可以由計算機執行的一組操作（或指令），它能在有限時間內執行結束并產生結果。算法具有下列特征：有0個或多個輸入：一個算法可以沒有輸入數據，也可以有多個輸入數據，輸入數據刻畫了算法的初始狀態；有1個或多個輸出：一個算法至少有一個輸出，也可以有多個輸出；確定性：算法中的每一步操作必須有明確的含義，不能有二義性；有窮性：一個算法必須在執行了有限步的操作后終止；可行性：算法中有待實現的操作都是計算機可執行的。3.2.2算法的表示方法常用的算法表示方法：自然語言、流程圖、偽代碼和程序設計語言等自然語言就是人們日常使用的語言，可以使漢語、英語或其他語言，用自然語言表示的算法通俗易懂，但是文字容易不嚴謹。算法輸入：硬幣A、B、C；算法輸出：找出的假幣；步驟1.比較A和B的重量；步驟2.如果A和B的重量相同，則C是假幣，算法結束；否則執行步驟3；步驟3.比較A和C的重量；步驟4.如果A和C的重量相同，則B是假幣，否則A是假幣；算法結束。1、自然語言2、流程圖流程圖是算法的圖形化表示方法，用圖的形似表示算法的各種操作，具有直觀、清晰、容易理解的特點。用圓角矩形表示算法的開始和結束，用平行四邊形表示輸入輸出，用菱形表示判斷，用矩形表示處理，各框之間用帶箭頭的線連接。

3、偽代碼偽代碼是介于自然語言和計算機語言之間的、用文字和符號來描述算法的一種語言形式。用偽代碼描述算法時沒有嚴格的語法規則限制，書寫方便、格式緊湊、容易讀懂，也便于向計算機程序轉換。inputA、B、CifA=BthenoutputC是假幣elseifA=CthenoutputB是假幣

elseoutputA是假幣end4、程序設計語言計算機程序設計語言編寫的程序來表示一個算法。用計算機語言描述算法時，必須嚴格遵守所用語言的語法規則，常常要編寫很多與算法無關的又十分繁瑣的語句，3.2.3算法的設計要求一個好的算法應該達到以下目標。正確性：算法應能滿足具體問題的需求，能得到預想的結果。易讀性：算法應方便人們閱讀、理解和交流，也便于后續的修改和功能擴充。健壯性：算法可能面臨各種各樣的數據，當接收到不適合算法處理的數據時，算法能適當地進行處理，不會產生預料不到的運行結果。如果算法能發現異常數據，并做出報警等處理，則算法的健壯性能好。高效性：評價一個算法優劣的重要依據是分析該算法的程序在計算機中執行時所需占用的計算機資源的多少。

兩個重要指標：算法的時間復雜度和算法的空間復雜度。3.2.4解決問題的常用算法窮舉法：在一個有限的解集合中，對所有可能的情況逐一驗證題目給定的約束條件，若滿足條件，則其為該問題的一個解；若全部情況驗證后都不符合題目的條件，則本題無解。窮舉法充分利用計算機運算速度快、精確度高的特點，通過犧牲時間來換取答案的全面性。窮舉法又稱為枚舉法。例如，為了判斷n是否為素數，在2～n-1的自然數中，逐一判斷其是否為n的因數。若存在某一個數是n的因數，則n不是素數，否則n是素數。1、窮舉法3.2.4解決問題的常用算法貪心法：尋找最優解問題。在對問題求解時，不從整體最優上加以考慮，總是做出在當前看來是最好的選擇，得到的是在某種意義上的局部最優解。例如，假設錢柜里的貨幣只有25分、10分、5分和1分四種硬幣，如果要找給客戶41分錢的硬幣，如何才能找給客戶的錢既正確且硬幣的個數又最少？41分可以分成1個25分，1個10分，1個5分，1個1分，共四枚硬幣。貪心算法不能保證最后求得的解是最優的，其結果有時是最優解的近似，或者是滿足某些約束條件的可行解。2、貪心法3.2.4解決問題的常用算法分治法是“分而治之”的方法，其基本思想就是將一個大問題分成若干個同類的小問題，小問題的解構造出大問題的解。把大問題分成小問題稱為“分”；從小問題的解構造大問題的解稱為“治”。3、分治法3、分治法快速排序方法是典型的分治法。例如，有8個待排序的數據：40、60、89、10、70、20、45和12，對8個數據的快速排序方法：先從數據序列中選擇一個基準數，將數據序列中所有比基準數小的數據放在基準數的左側，比基準數大的數據放在基準數的右側，基準數就在數據序列中定位了；再對基準數左右兩側的數據序列分別用上述方法處理，直到每一個待排序的數據定位為止。該數據序列的快速排序過程如圖所示，經過8輪，每一個數據都定位。3、分治法4、遞歸法遞歸法是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸的思路：將問題拆解成規模更小的子問題來計算，子問題再拆解成子子問題，直到被拆解的子問題可以直接求解。最小的子問題得到解后，那么它的上一層子問題也就可計算；上一層的子問題得到解后，上上層子問題自然也就可計算，直到原問題可計算。4、遞歸法例如，為了求階乘n!，可以寫作n!=n(n-1)!=n×(n-1)×(n-2)!=……=n×(n-1)×(n-2)×…2×1!為了計算n!，需要先計算出(n-1)!；為了計算(n-1)!，需要先計算出(n-2)!；依此類推，直到得到1！=1。有了1！=1，就可以逐個計算出2！、3！、……、(n-2)!、(n-1)!最后計算得到n!。當n=5時，用遞歸方法求5！的過程，“→”方向是逐步分解的過程，“←”方向是逐步回歸計算的過程。5、回溯法回溯法是類似枚舉的搜索方法，按照解決問題的線索向前搜索，以達到目標。當探索到某一步時，發現當前選擇并不是最優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術稱為回溯法。走迷宮是一個選擇不同的岔路口尋找出口的過程。如果走錯了路，則返回來，找到岔路口的另一條路，直到找到出口為止?；厮莘ň皖愃朴谧呙詫m，在搜索嘗試過程中尋找問題的解。6、動態規劃法動態規劃算法通常用于求解具有某種最優性質的問題。把所需求解問題的過程恰當地分成若干個相互聯系的階段，每一個階段都有若干個決策可供選擇，一個階段的決策確定以后，常常會影響到下一個階段的決策。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線。動態規劃所處理的問題是一個多階段決策最優化問題。6、動態規劃法例如，假設錢柜里有若干個1元、5元和7元的代金幣如果要找給客戶10元錢，如何才能找給客人的錢既正確且代金幣的個數又最少？使用貪心算法求解：先拿出7元代金幣，因為它與10元最接近，10-7=3，需要再拿3個1元代金幣，共4個代金幣。使用動態規劃法求解：每個圈表示決策過程中的一個狀態，圈中數字表示當前找給客戶的錢數；狀態之間連線上的數字表示這次決策拿出的代金幣，對應著7元、5元或1元的面值。A-B2-C3的決策序列只需要找給客戶2張5元代金幣。A-B2-C3的決策序列只需要找給客戶2張5元代金幣例題A-B2-C3的決策序列只需要找給客戶2張5元代金幣。例2．某張單據上有一個4位數的編碼No.5**8，其中百位數與十位數處被模糊后看不清楚，但是知道這個4位數是56的倍數?，F要找出所有滿足條件的4位數，請問可以采用哪一種算法思路來求解這個問題解：百位數與十位數可能組合為00~99，共100種可能?？刹捎酶F舉法，依次檢測5008、5018、5028、5038…..5998的100個數據是否是56的倍數，如果能被56整除，就輸出這個數據。

這個問題還可以有另一種方法求解。5008÷56=89余24，5998÷56=107余6，可采用窮舉法，依次檢測90～107的18個數據與56相乘的結果，若結果符合5**8特征，則輸出這個數據。相比于前一種方法，這種方法需要窮舉的數據量小，算法的效率高。例題例3．甲排在一個隊列的末尾，甲想知道他前面有多少人，就問他前面的乙：你是第幾位，甲想：他知道乙的位數就知道他前面有多少人了。乙也不知道自己是第幾位，就問自己前面的丙：你是第幾位？同理，丙又問他前面的?。耗闶堑趲孜唬恳源艘恢毕蚯耙晃粏栂氯?，直到第1位回答：我是第1位，第2位的接著向后回答：我是第2位。第3位的向后回答：我是第3位。以此繼續，丁告訴丙：我是第23位，丙告訴乙：我是第24位，乙告訴甲：我是第25位，甲就知道他前面有25個人。至此，隊列中每一位都知道自己前面有多少人了，這種方法體現了哪一種算法的思路？解：把上述問話和回答的流程可用圖表示，這種方法體現了遞歸算法的思路。3.3.1程序概述計算機程序（簡稱程序）：為了得到某種結果而可以由計算機等具有信息處理能力的裝置執行的代碼化指令序列，或者可以被自動轉換成代碼化指令序列的符號化指令序列或者符號化語句序列。解決問題的算法轉換為程序后，就可運行于計算機上。程序設計語言：機器語言、匯編語言和高級語言機器語言：與計算機硬件功能緊密相關的一種語言，由二進制0、1表示的代碼指令構成。匯編語言：對機器語言的符號化表示，用一些容易理解和記憶的縮寫單詞來表示特定的含義，高級語言：面向用戶的、基本獨立于計算機種類和結構的語言，形式上接近于算術語言和自然語言。3.3程序與程序設計語言3.3.1程序概述例如，為了計算3+4，C語言、x86匯編語言和x86機器語言的程序片段分別如下所示。C語言 匯編語言 機器語言（十六進制表示）3.3程序與程序設計語言movdwordptr[ebp-4],3movdwordptr[ebp-8],4moveax,dwordptr[ebp-4]addeax,dwordptr[ebp-8]movdwordptr[ebp-0ch],eaxx=3;y=4;z=x+y;C745FC03000000C745F8040000008B45FC0345F88945F43.3.1程序概述源程序：用高級語言或匯編語言書寫的程序。機器語言程序：用機器語言書寫的程序。目標程序：源程序經過語言處理系統翻譯后所得到的代碼化指令序列（二進制代碼），目標程序屬于機器語言程序?？蓤绦心繕顺绦?。多個源程序對應的目標程序組合在一起，并且與庫函數連接，形成完整的可在操作系統下獨立執行的程序。

可執行目標程序才是由計算機等具有信息處理能力的裝置能執行的代碼化指令序列。3.3.1程序概述語言處理系統會提供一個語言編程的環境，包括程序編輯、翻譯、調試、鏈接、裝入運行等功能。例如，VisualStudioC/C++是一個可以開發C/C++應用程序的集成開發環境。任何一個語言處理系統都包含一個翻譯程序，按照不同的翻譯處理方法，翻譯程序可分為三類。編譯程序：將高級語言源程序轉換為匯編語言源程序（或目標程序）的翻譯程序。匯編程序：將匯編語言源程序轉換為目標程序的翻譯程序。解釋程序：按源程序中語句的執行順序，逐條翻譯并立即執行相應功能的處理程序。這種翻譯方式不形成機器語言形式的目標程序。3.3.1程序概述從源程序到可執行目標程序的轉換過程3.3.2程序設計的一般步驟程序設計：設計、編制、調試程序的方法和過程。程序設計的一般步驟如下：分析問題：明確求解問題的已知條件、數據、目標，進行詳細分析確定數學模型：將求解問題直接或間接地轉化為數學問題。設計算法：給出解決問題的方法和步驟，清晰地描述出算法。編制程序：選擇一種程序設計語言，并編寫出算法對應的程序。運行和調試程序：運行可執行目標程序，對結果進行分析，發現和排除程序中的錯誤。編寫程序文檔和維護程序：整理和編寫程序文檔。3.3.3常用的程序設計語言FORTRAN：適用于數值計算的面向過程的高級程序設計語言。。FORTRAN廣泛應用于科學和工程計算領域，長期以來作為科學計算的主流程序設計語言。BASIC：標準BASIC是一種使用解釋程序的編程語言。BASIC語言發展了很多版本，如TrueBASIC、QuickBASIC、VisualBASIC（簡稱VB）等。VBA是基于VisualBASIC發展而來的，可以使用VBA編寫程序來擴展Office軟件的功能。VBScript是VisualBASIC的腳本語言，可以在HTML（超文本標記語言）中插入VBScript腳本，使網頁有一些動態效果，還可以實現一些交互操作。3.3.3常用的程序設計語言Pascal：最早出現的結構化編程語言，具有豐富的數據類型和簡潔靈活的操作語句，運行效率高，查錯能力強，可以被方便地用于描述各種算法與數據結構，編寫出高質量的程序。Delphi：是由傳統Pascal語言發展而來的ObjectPascal語言。這是在傳統Pascal語言的基礎上，擴充了面向對象的功能，并加入了可視化開發手段，用于開發Windows環境下的應用程序。3.3.3常用的程序設計語言C語言：具有高級程序設計語言的功能，又具有匯編語言的特點。Ｃ語言生成的目標程序質量高，程序執行效率高，可移植性好。著名的UNIX操作系統是第一個用C語言編寫的操作系統；也可用于開發應用軟件，目前在工業控制、智能裝備、物聯網等相關領域普遍使用C語言；各類科研活動也常常用C語言來編寫實驗程序。C語言是當代最優秀的、面向過程的程序設計語言之一。C++語言：在C語言的基礎上發展起來的，既支持面向過程的程序設計，又支持面向對象的程序設計。一直是面向對象程序設計的主流語言。C#是一種由C和C++衍生出來的面向對象的、運行于.NETFramework和.NETCore(完全開源，跨平臺)之上的高級程序設計語言。C#源程序被編譯成為中間代碼，然后通過.NETFramework的虛擬機執行。3.3.3常用的程序設計語言Java語言：一種面向對象的、適合網絡環境的程序設計語言，是目前使用最為廣泛的網絡編程語言之一。Android應用：Android手機中運行的應用程序大多是用Java語言所編寫。在金融業的應用：由于Java的安全性，大型跨國投資銀行常常用Java來編寫前臺和后臺的電子交易系統、結算和確認系統、數據處理項目以及其他項目。網站的應用：Java在電子商務領域以及網站開發領域占據了一定的席位。例如醫療救護、保險、教育、國防以及其他的不同部門的網站通常都是以Java為基礎來開發的。在大數據技術領域的應用：Hadoop是用java語言實現的開源軟件框架，是開發和運行處理大規模數據的軟件平臺，在Hadoop平臺上開發的大數據處理程序通常使用Java語言。3.3.3常用的程序設計語言Python語言：一種面向對象的解釋型程序設計語言。Python解釋器將源代碼轉換成為字節碼的中間形式，可以直接翻譯運行。Python是開源的，即所有用戶都可以看到Python源代碼。開源體現在兩方面：①程序員使用Python編寫的代碼是開源的。②Python解釋器和模塊是開源的。Python是免費的，即用戶進行開發或者發布自己的程序，不需要支付任何費用，也不用擔心版權問題，即使作為商業用途，Python也是免費的。Python應用廣泛，既可以開發小工具，也可以開發企業級應用。下面列舉一些Python語言的應用：網站開發、游戲開發、科學計算、網路爬蟲、人工智能領域等3.4.1計算機軟件的基本組成計算機軟件：計算機運行所需要的程序、數據和有關文檔的總和。程序：計算任務的處理對象和處理規則的描述；數據：程序處理的對象，例如文檔、圖像、視頻、音頻等；文檔：在程序編制、運行過程中的有關資料，如開發技術資料、用戶使用手冊、系統維護及升級資料等。通常軟件以程序文件和文檔文件的形式保存在磁盤和光盤等介質上，通過操作計算機才能體現出它的功能和作用。例如，微軟的office是一組軟件，它包括一系列互相關聯的文件，其中的WINWORD.exe、EXCEL.exe屬于程序文件。3.4軟件的特性和常用軟件3.4.1計算機軟件的基本組成計算機軟件：計算機運行所需要的程序、數據和有關文檔的總和。程序：計算任務的處理對象和處理規則的描述；數據：程序處理的對象，例如文檔、圖像、視頻、音頻等；文檔：在程序編制、運行過程中的有關資料，如開發技術資料、用戶使用手冊、系統維護及升級資料等。通常軟件以程序文件和文檔文件的形式保存在磁盤和光盤等介質上，通過操作計算機才能體現出它的功能和作用。例如，微軟的office是一組軟件，它包括一系列互相關聯的文件，其中的WINWORD.exe、EXCEL.exe屬于程序文件。根據軟件的作用，將計算機軟件劃分為系統軟件和應用軟件3.4計算機軟件的特性和常用軟件1、系統軟件系統軟件：為了有效使用計算機系統、提高計算機資源的使用效率、協調計算機各部件之間工作的一類軟件。主要功能：調度，監控和維護計算機系統；負責管理計算機系統中各種獨立的硬件，使得它們可以協調工作。常用的系統軟件：操作系統、語言處理系統、數據庫管理系統和各種服務軟件等。操作系統：計算機軟件中最重要且最基本的系統軟件。在微機上常見的操作系統有DOS、Windows、Linux、MacOS等操作系統，手機上移動操作系統有安卓Android和蘋果手機的iOS。服務軟件：稱為實用工具軟件，一般包括診斷程序、調試程序等。例如磁盤碎片整理程序。1、系統軟件數據庫管理系統：一種操縱和管理數據庫的軟件；Access、Oracle、SQLServer、Sybase等。TiDB、openGauss、GaussDB、OceanBase和DM8等。數據庫是一個長期存儲在計算機內的、有組織的、可共享的、統一管理的大量數據的集合。例如：數據庫管理系統介于圖書數據庫和圖書查詢程序之間，數據庫管理系統是創建和管理圖書數據庫的軟件，圖書查詢程序通過數據庫管理系統訪問圖書數據庫2、應用軟件應用軟件：為滿足用戶不同領域、不同問題的應用需求而開發的那些軟件或程序。應用軟件具有很強的實用性和針對性，應用軟件數量巨大、種類繁多、功能強大。根據應用軟件的開發方法和適用范圍，應用軟件分類：通用應用軟件：常用的辦公類軟件MicrosoftOffice、WPSOffice；圖形圖像處理軟件Photoshop；繪圖軟件AutoCAD；即時通信軟件微信、QQ；影音視頻播放軟件PotPlay等等。定制應用軟件：是根據某一單位或某一行業的業務需求定制開發的軟件。例如圖書管理系統、學校的教務系統、財務系統、醫院掛號計費系統、酒店客房管理系統等等。3.4.2計算機軟件的特性不可見性：程序和數據以二進位編碼表示并通過電、磁或光的形式進行存儲和傳輸?？吹降闹皇撬奈锢磔d體，而不是軟件本身。適用性：成功的軟件往往是能滿足一類問題的需要。依附性：軟件不能獨立存在，需要依附一定的環境。在某臺PC機上能正常運行的某個軟件，在平板電腦或手機上不能直接安裝運行，也未必在另一臺計算機上能運行。無磨損性：理論上，只要軟件所依賴的硬件和軟件環境不改變，它的功能和性能就不會發生變化。復雜性：軟件規模越來越大，結構越來越復雜，開發成本越來越高有限責任：不能保證軟件在任何情況下穩定運行。軟件廠商一般要求軟件運行的風險由用戶自己承擔。脆弱性：軟件漏洞、網絡等因素，軟件的運行存在安全性問題。易復制性：軟件可無失真地進行復制，存在軟件的知識產權保護。3.4.3計算機軟件的保護軟件產品的生產屬于高強度的腦力勞動，是智力活動的成果，受知識產權保護：著作權法、專利法、商標法和商業秘密。軟件的著作權保護依據是《中華人民共和國著作權法》和《計算機軟件保護條例》。受到著作權法保護的軟件作品表現形式為計算機程序代碼及其相關說明文檔。軟件的專利保護依據是《中華人民共和國專利法》，受到知識產權保護的軟件作品表現形式為軟件的技術構思，如技術方案（包含軟件流程圖）、圖形用戶界面等。軟件的商標保護依據是《中華人民共和國商標法》，軟件商標刻錄在光盤、軟盤等有形載體上，還可以標