Python程序設(shè)計實踐 課件 ch02 問題求解與計算思維

第二章問題求解與計算思維浙江省普通本科高?！笆奈濉敝攸c教材Python程序設(shè)計實踐教程01計算概述PARTONE1.幾何法時期：割圓術(shù)最早計算圓周率的方法是割圓術(shù)。魏晉時期的數(shù)學家劉徽首創(chuàng)割圓術(shù)，為計算圓周率建立了嚴密的理論和完善的算法。所謂割圓術(shù)，就是不斷倍增圓內(nèi)接正多邊形的邊數(shù)，求出圓周率。劉徽從圓內(nèi)接正6邊形開始，每次都把邊數(shù)加倍，直至圓內(nèi)接正96邊形，算得圓周率為157/50（即3.14）。后來，他在此基礎(chǔ)上又計算出了圓內(nèi)接正3072邊形的面積，得到圓周率的近似值為3927/1250（即3.1416）。南北朝時期的數(shù)學家祖沖之進一步求出了圓內(nèi)接正12288邊形和圓內(nèi)接正24576邊形的面積，得出3.1415926<π<3.1415927。在之后的800年里，祖沖之計算出的圓周率是最準確的。2.解析法時期：無窮級數(shù)分析法割圓術(shù)的煩瑣計算促使人們探索新的計算方法，通過無窮乘積、無窮連分數(shù)、無窮級數(shù)等各種計算方法，圓周率的計算精度迅速增加。1706年，英國數(shù)學家梅欽率先將圓周率突破百位。1948年，英國的弗格森和美國的倫奇共同發(fā)表了π的808位小數(shù)值，成為人工計算圓周率的最高紀錄。

【例2-1】格里高利公式求圓周率利用格里高利公式（）求圓周率。3.計算機時期：蒙特卡羅法計算機的出現(xiàn)使圓周率的計算速度和精度有了突飛猛進的發(fā)展。2011年10月16日，日本長野縣飯?zhí)锸泄镜穆殕T近藤茂利用家用計算機將圓周率計算到小數(shù)點后10萬億位。圖2-2圓及其外接正方形畫一個圓的外接正方形，假設(shè)圓的半徑是1，那么圓的面積是π，外接正方形的面積是4，如圖2-2所示。任意產(chǎn)生正方形內(nèi)的一個點，該點落在圓內(nèi)的概率=圓面積/正方形面積，即π/4。3.計算機時期：蒙特卡羅法蒙特卡羅法利用了概率統(tǒng)計的思想，使用隨機數(shù)來解決計算問題。隨著實驗次數(shù)增多，會出現(xiàn)概率收斂，計算值會更好地逼近精確解，這使求得的解是可以接受的。蒙特卡羅法在金融工程學、宏觀經(jīng)濟學、計算物理學等領(lǐng)域中有著廣泛的應(yīng)用。蒙特卡羅法利用了概率統(tǒng)計的思想，使用隨機數(shù)來解決計算問題。隨著實驗次數(shù)增多，會出現(xiàn)概率收斂，計算值會更好地逼近精確解，這使求得的解是可以接受的。蒙特卡羅法在金融工程學、宏觀經(jīng)濟學、計算物理學等領(lǐng)域中有著廣泛的應(yīng)用。02求解計算機問題PARTTWO1.計算機解題的特性日常生活中有許多應(yīng)用順序流程的例子，炒菜時要根據(jù)一定的次序投放食材與調(diào)味品；網(wǎng)絡(luò)購物時要通過規(guī)定的步驟完成購物過程，如選擇商品、填寫數(shù)據(jù)、付款等；使用自動提款機進行交易時，需要依次完成插卡、輸入密碼、選擇金融交易方式、輸入金額等步驟。

當我們要解決的問題比較復(fù)雜時，可以將大問題分成幾個較小的問題，再設(shè)計較小問題的解決方案。計算機解題的特性是根據(jù)所設(shè)計的步驟按順序執(zhí)行，每次執(zhí)行都會獲得一致的結(jié)果。由于垂直式思維的推理結(jié)論具有正確性、系統(tǒng)性、普遍性，所以大部分步驟能轉(zhuǎn)換成可以執(zhí)行的步驟。2.計算機解題的應(yīng)用（1）科學計算

科學計算是計算機應(yīng)用的一個重要領(lǐng)域，如高能物理、工程設(shè)計、地震預(yù)測、氣象預(yù)報、航天技術(shù)等。同時，由于計算機具有很高的運算速度、精度及邏輯判斷能力，出現(xiàn)了計算力學、計算物理、計算化學、生物控制等新學科。（3）計算機輔助系統(tǒng)

計算機輔助系統(tǒng)包括計算機輔助設(shè)計（CAD）、計算機輔助工藝過程設(shè)計（CAPP）、計算機輔助制造（CAM）、計算機輔助教學（CAI）等。（2）數(shù)據(jù)處理

數(shù)據(jù)處理是指通過計算機獲取、加工、處理各種數(shù)據(jù)及數(shù)據(jù)可視化，提高管理效率，如管理信息系統(tǒng)（MIS）、物資需求計劃（MRP）、企業(yè)資源計劃（ERP）、制造執(zhí)行系統(tǒng)（MES）、電子商務(wù)系統(tǒng)等。2.計算機解題的應(yīng)用（4）生產(chǎn)自動化

生產(chǎn)自動化包括工業(yè)流程控制、流水線控制、無人工廠等。（6）生活出行

網(wǎng)絡(luò)信息資源的深層次利用和網(wǎng)絡(luò)應(yīng)用的日趨大眾化正在改變著我們的工作方式和生活方式。（5）人工智能

生產(chǎn)自動化包括人臉識別、藥物研發(fā)、機器人、交通等場景應(yīng)用。3.計算機解題的基本步驟問題分析與建模1對現(xiàn)實問題進行分析、抽象，建立相應(yīng)的數(shù)學模型，把對現(xiàn)實問題的求解轉(zhuǎn)化為對抽象數(shù)學模型的求解，滿足計算機處理問題的特點和基本要求。問題分析與建模時首先要確定問題的邏輯結(jié)構(gòu)和基本功能，然后在結(jié)合數(shù)學、物理、計算機等的基礎(chǔ)上，建立相關(guān)數(shù)學模型。數(shù)學建模是一種數(shù)學思考方法，是指運用數(shù)學語言和方法，通過抽象、簡化建立能近似刻畫并解決實際問題。3.計算機解題的基本步驟算法設(shè)計與實現(xiàn)2算法設(shè)計與實現(xiàn)是指設(shè)計解決某一特定問題或某一類問題的一系列步驟，并且要求這些步驟可以通過計算機的基本操作來實現(xiàn)。算法設(shè)計完成后，要將其表示成計算機語言，從而能夠通過計算機來解決現(xiàn)實中的具體問題。算法分析3算法分析是指對所設(shè)計算法的性能特征進行分析、評價和總結(jié)。03計算思維PARTTHREE1.思維和思維過程

思維（Thinking）是人類對情感、信息處理過程的一種概括和抽象，是一種心理活動的反映，是人腦從對客觀事物的直接感知過渡到抽象思維的升華，反映了客觀事物的本質(zhì)與規(guī)律。思維是通過一系列比較復(fù)雜的操作來實現(xiàn)的，如分析與綜合、比較、抽象與概括等，通常具有概括性、間接性、能動性三大特性。1.思維和思維過程（1）概括性在人的感性基礎(chǔ)上，將一類事物的共同特性和本質(zhì)規(guī)律抽象出來，加以歸納與概括。例如，人類通過長期對地球氣候和植物生長規(guī)律的觀察，總結(jié)出了二十四節(jié)氣與種植時節(jié)。（2）間接性將非直接的事物作為媒介，來反映事物的特征或規(guī)律。例如，醫(yī)生根據(jù)醫(yī)學知識和臨床經(jīng)驗，結(jié)合病人的癥狀和化驗結(jié)果，推斷出病人的病情。（3）能動性思維不僅能認識和反映客觀規(guī)律，而且能改造客觀世界。例如，人類認識了萬有引力，還發(fā)射了人造衛(wèi)星、太空飛船。2.科學思維傳統(tǒng)的科學研究手段理論研究和實驗研究，計算則是兩種研究的一種輔助手段。隨著計算技術(shù)和計算機技術(shù)的迅速發(fā)展，計算已上升為科學研究的一種手段，它直接并有效地為科學研究服務(wù)?？茖W思維（ScientificThinking）理論認識及其過程，即通過整理和改造感性階段獲得的大量材料，形成概念、判斷、推理，反映事物的本質(zhì)和規(guī)律。2.科學思維理論思維（TheoreticalThinking）又稱為邏輯思維1通過抽象和概括，描述事物的本質(zhì)，用科學的方法探尋概念之間的聯(lián)系。它以推理和演繹為特征，以數(shù)學學科為代表。通過觀察和實驗獲取自然規(guī)律、法則的一種思維方法。它以觀察和歸納自然規(guī)律為特征，以物理學科為代表。實驗思維（ExperimentalThinking）又稱為實證思維22.科學思維計算思維（ComputationalThinking）又稱為構(gòu)造思維3從具體的算法設(shè)計規(guī)范入手，通過算法過程的構(gòu)造與實施來解決特定問題。它以設(shè)計和構(gòu)造為特征，以計算學科為代表。3.理解計算思維

計算思維的認識過程計算思維的定義計算思維的特征計算機科學與計算思維010203044.計算思維的應(yīng)用計算生物學1計算生物學是生物學的一個分支，用于開發(fā)和應(yīng)用數(shù)據(jù)分析及理論、數(shù)學建模、計算機仿真等，并應(yīng)用于生物學、行為學、社會群體研究的一門學科，如基因測序、蛋白質(zhì)結(jié)構(gòu)預(yù)測等。4.計算思維的應(yīng)用計算化學2計算化學主要用計算機程序和方法對特定的化學問題進行研究，如數(shù)值計算（量子化學和結(jié)構(gòu)化學中的演繹計算、分析化學中的條件模擬、化工過程中的應(yīng)用計算等）、化學模擬、模式識別等。4.計算思維的應(yīng)用計算數(shù)學3計算數(shù)學也叫作數(shù)值計算方法或數(shù)值分析，如數(shù)值計算和分析、系統(tǒng)建模和仿真、數(shù)字信號處理、數(shù)據(jù)可視化、財務(wù)與金融工程計算、軟件機器人等。4.計算思維的應(yīng)用其他學科領(lǐng)域4許多其他學科通過抽象建模，將研究從定性分析轉(zhuǎn)化為定量研究，將計算思維應(yīng)用于經(jīng)濟學、管理科學、法學、文學、藝術(shù)、體育等社會科學領(lǐng)域。計算思維改變了各學科領(lǐng)域的研究模式，如計算機博弈論改變了經(jīng)濟學家的思考方法。1994年諾貝爾經(jīng)濟學獎授予約翰·納什（JohnNash）、萊茵哈德·澤爾騰（ReinhardSelten）、約翰·海薩尼（JohnC.Harsanyi）三位博弈論專家，他們有力地證明了博弈論在現(xiàn)代經(jīng)濟學中的地位。5.為什么要倡導計算思維計算思維就是用計算機科學解決問題的思維，它是每個人都應(yīng)該具備的基本技能，不僅僅屬于計算機科學家。計算思維訓練對計算機應(yīng)用人才的培養(yǎng)是極為重要的，它不僅能使學生理解計算機的實現(xiàn)機制和約束條件，有利于學生進行發(fā)明和創(chuàng)新，更重要的是有利于提高學生的信息素養(yǎng)，也就是處理計算機問題時應(yīng)有的思維方法、表達形式、行為習慣。因此，提高計算機基礎(chǔ)教學的質(zhì)量，增強學生的計算思維能力，是培養(yǎng)應(yīng)用型、創(chuàng)新型人才的必然要求。盡管計算機科學不等于程序設(shè)計，但不可否認的是，學習程序設(shè)計方法是理解計算機的最好途徑。編程思維是無止境的，不同問題有不同的分析方法、算法、代碼實現(xiàn)方法。在教學中有意識地引導學生多視角、多方位地進行編程思考，會使學生的思維能力得到跳躍式擴展和提高。（1）計算思維與數(shù)學基礎(chǔ)的構(gòu)建計算機科學在本質(zhì)上源于數(shù)學思維，它的形式化解析基礎(chǔ)筑于數(shù)學之上。（2）計算思維與計算機科學導論的學習為了對計算機科學的課程體系和知識體系有比較清晰的了解，必須站在計算思維的高度和廣度來了解和掌握計算機學科的基本概念、基本方法、發(fā)展趨勢，知曉學科的內(nèi)涵和本質(zhì)，將其作為計算機科學的導學部分。6.如何培養(yǎng)和訓練計算思維（3）計算思維與思維能力的培養(yǎng)計算思維是人類求解問題的一條途徑。過去，人們認為計算機科學家的思維就是用計算機去編程，這種認識是片面的。計算思維不僅是程序化的，而是在抽象的多個層次上進行思維。（4）計算思維與應(yīng)用能力的培養(yǎng)目前，計算機應(yīng)用已經(jīng)深入到各行各業(yè)中，融入人類活動中，解決了大量計算時代之前無法解決的問題。（5）計算思維與創(chuàng)新能力的培養(yǎng)創(chuàng)新是一個民族生存、發(fā)展和進步的原動力。計算思維的培養(yǎng)對創(chuàng)新能力的培養(yǎng)至關(guān)重要，創(chuàng)新要靠科學素養(yǎng)和理解科學，靠科學的思想方法。6.如何培養(yǎng)和訓練計算思維04算法PARTFOUR1.算法及其描述算法概述1算法解決特定問題的方法或步驟，或者說，算法是為解決一類特定問題而設(shè)計的確定的、有限的操作步驟。算法是程序設(shè)計的關(guān)鍵，找不到算法就無法編寫計算機程序，也就無法用計算機來解決問題。廣義上

算法是指通過運算的方式，按照某種機械的步驟逐步求解問題。狹義上

算法是解決一個問題采取的方法和步驟的描述，如圖2-8所示。圖2-8狹義的算法1.算法及其描述算法的分類2不是所有算法都適合在計算機上執(zhí)行，能在計算機上執(zhí)行的算法就是計算機算法。計算機算法可以分為兩類：一類是數(shù)值算法，另一類是非數(shù)值算法。1.算法及其描述算法的特性3（1）有窮性一個算法必須在執(zhí)行有限個計算步驟后終止。（2）確定性一個算法給出的每個計算步驟都必須是精確定義、無二義性的。（3）有效性算法中的每個步驟都必須被有效地執(zhí)行，并能得到確定的結(jié)果。（4）有零個或多個輸入信息一個算法可以沒有輸入信息，也可以有一個或多個輸入信息，這些輸入信息是算法的初始數(shù)據(jù)。（5）有一個或多個輸出信息一個算法應(yīng)有一個或多個輸出信息，沒有輸出信息的算法是沒有意義的。1.算法及其描述如何發(fā)現(xiàn)算法4（1）第一階段：分析、理解、抽象、歸納問題。（2）第二階段：尋找一個可能解決問題的思路。（3）第三階段：用數(shù)學語言將其表達出來。（4）第四階段：闡明算法并選用合適的數(shù)據(jù)結(jié)構(gòu)，用程序?qū)⑵渚帉懗鰜?。?）第五階段：評估算法的準確度以及算法是否有潛力作為一個解決問題的工具。2.算法的表示形式自然語言1自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語、英語或其他語言。用自然語言表示算法的優(yōu)點是通俗易懂，缺點是文字冗長，容易出現(xiàn)歧義性。偽代碼2偽代碼是介于自然語言和計算機語言之間的文字和符號（包括數(shù)學符號），如同寫一篇文章，自上而下地寫下來，每一行（或幾行）表示一個基本操作。偽代碼不使用圖形符號，因此書寫方便、格式緊湊，也比較易懂，便于向計算機語言程序轉(zhuǎn)換。2.算法的表示形式流程圖3流程圖是一種傳統(tǒng)的算法表示方法，它使用不同的幾何圖形框來代表不同性質(zhì)的操作，用流程線來指示算法的執(zhí)行方向。流程圖直觀形象、易于理解，所以應(yīng)用廣泛。05數(shù)據(jù)結(jié)構(gòu)PARTFIVE1.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)（DataStructure）計算機存儲、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理（存儲）結(jié)構(gòu)、數(shù)據(jù)的運算結(jié)構(gòu)。2.常用的數(shù)據(jù)結(jié)構(gòu)（1）數(shù)組（Array）在程序設(shè)計算法中，為了處理方便，把具有相同類型的若干變量有序地組織起來，這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。數(shù)組是n（n>1）個相同類型的數(shù)據(jù)元素a0，a1，…，an-1構(gòu)成的有限序列，該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中，可以把它看作一種長度固定的線性表。（2）棧（Stack）棧是只能在某一端插入和刪除數(shù)據(jù)的特殊線性表。它按照“先入后出”的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后進入的數(shù)據(jù)在棧頂，讀取數(shù)據(jù)時從棧頂開始彈出數(shù)據(jù)（最后進入的數(shù)據(jù)第一個被讀?。鐖D2-11所示。特點：先入后出、后入先出；除了頭、尾節(jié)點，每個節(jié)點都有一個后繼和一個前驅(qū)。2.常用的數(shù)據(jù)結(jié)構(gòu)（3）隊列（Queue）隊列是一種特殊的線性表，它只允許在表的前端（Front）進行刪除操作，以及在表的后端（Rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列是按照“先入先出”和“后入后出”的原則組織數(shù)據(jù)的。隊列中沒有元素時稱為空隊列。特點：先入先出，后入后出；除了尾節(jié)點，每個節(jié)點都有一個后繼；除了頭節(jié)點，每個節(jié)點都有一個前驅(qū)。（4）鏈表（LinkedList）鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，它既可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。每個節(jié)點包括兩部分，一是存儲數(shù)據(jù)元素的數(shù)據(jù)域，二是存儲下個節(jié)點地址的指針域。2.常用的數(shù)據(jù)結(jié)構(gòu)（5）樹（Tree）樹是由n（n≥0）個節(jié)點組成的有限集合，若n=0，稱為空樹；若n>0，則滿足以下兩個條件。①有一個特定的稱為根（Root）的節(jié)點，它只有直接后繼，但沒有直接前驅(qū)。②除根節(jié)點以外的其他節(jié)點可以劃分為m（m≥0）個互不相交的有限集合（T0,T1,…,Tm-1），集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹。（6）圖（Graph）圖由節(jié)點的有窮集合V和邊的集合E組成。為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常將節(jié)點稱為頂點，邊是頂點的有序偶對。如果兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關(guān)系。圖被廣泛應(yīng)用于各個領(lǐng)域，可以解決很多實際問題。圖的應(yīng)用有求最短路徑、拓撲排序、關(guān)鍵路徑等。06算法評價PARTSIX1.算法的評價標準（1）正確性：算法的執(zhí)行結(jié)果應(yīng)當滿足規(guī)定的功能和性能要求。（2）可讀性：算法應(yīng)當思路清晰、層次分明、簡單明了、易讀易懂。（3）健壯性：算法應(yīng)具有對不合理數(shù)據(jù)的反應(yīng)能力和處理能力，也稱為容錯性。。（4）高效性：算法應(yīng)有較高的時間效率。（5）低存儲量需求：存儲量是指算法執(zhí)行過程中需要的最大存儲空間，即有效使用存儲空間。2.時間復(fù)雜度算法的時間復(fù)雜度（TimeComplexity）是指算法運行的時間，是算法所求解的問題規(guī)模n的函數(shù)，通常記為T(n)。時間復(fù)雜度是算法的時間代價，用執(zhí)行算法所需的基本操作（原操作）次數(shù)來描述，以基