《Python程序設計實踐教程》課程教案課題：問題求解與計算思維教學目的：理解計算的基本概念與原理：通過計算概述，幫助學生理解計算的定義、發(fā)展歷程及其在問題求解中的核心作用，為后續(xù)學習奠定理論基礎。掌握問題求解的基本方法與步驟：通過求解計算機問題的講解，培養(yǎng)學生分析問題、分解問題并設計解決方案的能力，提升實際問題求解的效率與準確性。培養(yǎng)計算思維的核心能力：重點闡述計算思維的內(nèi)涵，包括抽象、分解、模式識別和算法設計等核心能力，使學生能夠運用計算思維解決復雜問題。掌握算法的基本概念與設計方法：介紹算法的定義、特性及設計步驟，幫助學生理解算法在問題求解中的重要性，并能夠設計簡單高效的算法。理解常見數(shù)據(jù)結構及其應用：講解數(shù)據(jù)結構的基本概念與常見類型（如數(shù)組、鏈表、棧、隊列等），幫助學生理解數(shù)據(jù)結構在算法設計與問題求解中的關鍵作用。掌握算法評價的標準與方法：介紹算法評價的指標（如時間復雜度、空間復雜度）與方法，使學生能夠分析算法的效率并選擇最優(yōu)解決方案。為后續(xù)編程實踐與復雜問題求解奠定基礎：通過本章的學習，學生能夠從計算的角度分析問題，設計合理的算法與數(shù)據(jù)結構，并具備評價算法效率的能力，為后續(xù)編程實踐與復雜問題求解提供理論支持與方法指導。課型：新授課課時：本章安排8個課時。教學重點：重點：了解計算概述。掌握計算機解題的特性、應用步驟等相關內(nèi)容。掌握計算思維及算法。了解數(shù)據(jù)結構的定義及常用的數(shù)據(jù)結構。了解算法評價的相關內(nèi)容。教學難點：難點：本章教學難點在于如何將實際問題抽象為計算模型，并設計出高效、正確的算法，同時掌握數(shù)據(jù)結構的選擇與算法性能的評價方法。教學過程：教學形式：講授課，教學組織采用課堂整體講授和分組演示。教學媒體：采用啟發(fā)式教學、案例教學等教學方法。教學手段采用多媒體課件、視頻等媒體技術。板書設計：本課標題問題求解與計算思維課次2授課方式理論課□討論課□習題課□其他□課時安排8學分共8分授課對象普通高等院校學生任課教師教材及參考資料1.《Python程序設計實踐教程》。2.本教材配套視頻教程及學習檢查等資源。3.與本課程相關的其他資源。教學基本內(nèi)容教學方法及教學手段課程引入日常工作、學習和生活中會遇到各種各樣的問題，問題求解就是要找出解決問題的方法，并遵循一定的順序步驟，得到問題的答案或達到最終目標。計算機技術的發(fā)展和普及正在影響和改變著人們對世界的認識，也影響著人們的思維方式。以設計和構造為特征的“計算思維”被認為是除理論思維、實驗思維之外，人類應該具有的第三種思維方式，成為人們認識計算機科學的新高度。計算思維是指運用計算機科學的基礎概念去求解問題、設計系統(tǒng)并理解人類的行為，它代表著一種普遍的認識和一類普適的技能，是每個人的必備技能，不僅僅屬于計算機科學家。計算思維應成為信息社會中每個人必須具備的基本技能。本章將圍繞計算思維的核心思維—邏輯思維、算法思維、問題求解策略、模式與歸納、抽象與建模、求解的評價，以及算法、數(shù)據(jù)結構、算法與程序等內(nèi)容展開，為讀者利用計算思維解決各領域的問題奠定基礎。參考以下形式：1.銜接導入2.懸念導入3.情景導入4.激疑導入5.演示導入6.實例導入7.其他形式第2章問題求解與計算思維2.1計算概述圓周率的計算是一個結合計算方法和計算工具的典型案例，從圓周率小數(shù)點后的幾位、幾百位到幾十萬億位，跨越了2000多年。正是由于計算方法的不斷改進以及計算工具的不斷提高，圓周率的計算速度和精度取得了巨大提高。1.幾何法時期：割圓術最早計算圓周率的方法是割圓術。魏晉時期的數(shù)學家劉徽首創(chuàng)割圓術，為計算圓周率建立了嚴密的理論和完善的算法。所謂割圓術，就是不斷倍增圓內(nèi)接正多邊形的邊數(shù)，求出圓周率。劉徽從圓內(nèi)接正6邊形開始，每次都把邊數(shù)加倍，直至圓內(nèi)接正96邊形，算得圓周率為157/50（即3.14）。后來，他在此基礎上又計算出了圓內(nèi)接正3072邊形的面積，得到圓周率的近似值為3927/1250（即3.1416）。南北朝時期的數(shù)學家祖沖之進一步求出了圓內(nèi)接正12288邊形和圓內(nèi)接正24576邊形的面積，得出3.1415926<π<3.1415927。在之后的800年里，祖沖之計算出的圓周率是最準確的。2.解析法時期：無窮級數(shù)分析法割圓術的煩瑣計算促使人們探索新的計算方法，通過無窮乘積、無窮連分數(shù)、無窮級數(shù)等各種計算方法，圓周率的計算精度迅速增加。1706年，英國數(shù)學家梅欽率先將圓周率突破百位。1948年，英國的弗格森和美國的倫奇共同發(fā)表了π的808位小數(shù)值，成為人工計算圓周率的最高紀錄。3.計算機時期：蒙特卡羅法計算機的出現(xiàn)使圓周率的計算速度和精度有了突飛猛進的發(fā)展。2011年10月16日，日本長野縣飯?zhí)锸泄镜穆殕T近藤茂利用家用計算機將圓周率計算到小數(shù)點后10萬億位。2.2求解計算機問題隨著社會的發(fā)展與科技的進步，出于計算時間和復雜度等因素的考量，現(xiàn)實世界中的很多問題都需要借助計算機進行計算。現(xiàn)代計算機的工作原理是存儲程序和程序控制，也就是說，現(xiàn)代計算機只能對可計算性問題進行計算，但具體怎么計算，計算機卻不知道，需要人來告訴計算機。人與計算機的溝通方式是通過程序控制指令。1.計算機解題的特性日常生活中有許多應用順序流程的例子，炒菜時要根據(jù)一定的次序投放食材與調味品；網(wǎng)絡購物時要通過規(guī)定的步驟完成購物過程，如選擇商品、填寫數(shù)據(jù)、付款等；使用自動提款機進行交易時，需要依次完成插卡、輸入密碼、選擇金融交易方式、輸入金額等步驟。當我們要解決的問題比較復雜時，可以將大問題分成幾個較小的問題，再設計較小問題的解決方案。計算機解題的特性是根據(jù)所設計的步驟按順序執(zhí)行，每次執(zhí)行都會獲得一致的結果。由于垂直式思維的推理結論具有正確性、系統(tǒng)性、普遍性，所以大部分步驟能轉換成可以執(zhí)行的步驟。2.計算機解題的應用計算機解題的應用領域相當廣泛，只要是計算機提供的服務，在其背后都可以發(fā)現(xiàn)計算機解題的過程。計算機解題在各領域的應用實例有網(wǎng)絡購物系統(tǒng)、電子商務系統(tǒng)、搜索引擎、醫(yī)學工程系統(tǒng)、氣象預測系統(tǒng)、校務行政系統(tǒng)、電子地圖應用、各種數(shù)學計算問題等。（1）科學計算。科學計算是計算機應用的一個重要領域，如高能物理、工程設計、地震預測、氣象預報、航天技術等。同時，由于計算機具有很高的運算速度、精度及邏輯判斷能力，出現(xiàn)了計算力學、計算物理、計算化學、生物控制等新學科。（2）數(shù)據(jù)處理。數(shù)據(jù)處理是指通過計算機獲取、加工、處理各種數(shù)據(jù)及數(shù)據(jù)可視化，提高管理效率，如管理信息系統(tǒng)（MIS）、物資需求計劃（MRP）、企業(yè)資源計劃（ERP）、制造執(zhí)行系統(tǒng)（MES）、電子商務系統(tǒng)等。（3）計算機輔助系統(tǒng)。計算機輔助系統(tǒng)包括計算機輔助設計（CAD）、計算機輔助工藝過程設計（CAPP）、計算機輔助制造（CAM）、計算機輔助教學（CAI）等。（4）生產(chǎn)自動化。生產(chǎn)自動化包括工業(yè)流程控制、流水線控制、無人工廠等。（5）人工智能。生產(chǎn)自動化包括人臉識別、藥物研發(fā)、機器人、交通等場景應用。（6）生活出行。網(wǎng)絡信息資源的深層次利用和網(wǎng)絡應用的日趨大眾化正在改變著我們的工作方式和生活方式。3.計算機解題的基本步驟用計算機處理數(shù)據(jù)或解決問題時，雖然可以根據(jù)不同的情況采用多種方法，但基本步驟是相同的。（1）問題分析與建模對現(xiàn)實問題進行分析、抽象，建立相應的數(shù)學模型，把對現(xiàn)實問題的求解轉化為對抽象數(shù)學模型的求解，滿足計算機處理問題的特點和基本要求。問題分析與建模時首先要確定問題的邏輯結構和基本功能，然后在結合數(shù)學、物理、計算機等的基礎上，建立相關數(shù)學模型。數(shù)學建模是一種數(shù)學思考方法，是指運用數(shù)學語言和方法，通過抽象、簡化建立能近似刻畫并解決實際問題。數(shù)學建模和計算機技術的相互輔佐和融合在知識經(jīng)濟時代可謂是如虎添翼。2.3計算思維案例：用小白鼠檢驗毒水瓶假設有100瓶水，有1瓶是有毒的，小白鼠喝了有毒的水，7天內(nèi)就會死掉。請問至少需要幾只小白鼠，才能在7天內(nèi)檢驗出哪瓶水有毒？怎樣檢驗？求解過程如圖2-6所示（現(xiàn)假設97號有毒）。（1）將100瓶水編號，編號為0～99。僅用十進制數(shù)編號，很難看出如何求解。怎么解呢？可以用二進制數(shù)求解問題。（2）進行變換，將每瓶水的編號由十進制數(shù)轉換為二進制數(shù)。1位二進制數(shù)只能表示0或1（最大編號是21-1），2位二進制數(shù)能表示0～3（最大編號是22-1），以此類推，7位二進制數(shù)能表示0～127（最大編號是27-1）。因此，如果要表示99，則需要7位二進制數(shù)。由此，可想到需要7只小白鼠就可以在7天內(nèi)檢驗出哪瓶水有毒。問題接著來了，怎樣讓小白鼠喝水，才能從100瓶水中判斷出哪瓶水有毒呢？小白鼠喝了有毒的水，可能很快就死亡，也可能在第7天死亡，因此一只一只試驗也來不及。（3）每瓶水的編號都是7位二進制數(shù)，記為B6B5B4B3B2B1B0（Bi為0或1，i=0,1,2,…,6），7只小白鼠的編號分別是M6、M5、M4、M3、M2、M1、M0。制定規(guī)則為：如果一瓶水的Bi為0，則不讓Mi小白鼠喝水；如果Bi為1，則讓Mi小白鼠喝水。（4）將100瓶水按上述規(guī)則處理。小白鼠喝完后，等待7天，看哪只小白鼠死了。如果Mi小白鼠死了，則Mi=1，否則Mi=0。將Mi連起來，發(fā)現(xiàn)M6M5M4M3M2M1M0=1100001，就得出了有毒水瓶的二進制數(shù)編號，再還原回十進制數(shù)，便可得知97號有毒。其背后的思維邏輯是怎樣的呢？①二進制思維。二進制思維是指將很多事物及其狀態(tài)非常巧妙地統(tǒng)一起來，如0和1可以分別表示“無毒”和“有毒”、“不喝”和“喝”、“不死”和“死”?，F(xiàn)在的計算機也采用了這種思維，即二進制理論。②二分法思維。二分法思維是指不斷地排除“不可能”，進而找出問題的正確解。之所以稱為“二分”，是因為每次處理時都把所有情況分成“可能”與“不可能”兩種情況，然后排除所有“不可能”的情況，在“可能”的情況下再進行下一次排除。③過程化與符號變換思維?！坝眯“资髾z驗毒水瓶”的求解過程為：水瓶的十進制數(shù)編號→二進制編碼→分配給小白鼠并產(chǎn)生結果→二進制編碼→水瓶的十進制數(shù)編號→找出毒水瓶。2.4算法案例：“雙11”背后隱含的算法2019年天貓“雙11”的訂單數(shù)峰值是544000筆/秒，阿里云抗住了全球最大的流量洪峰，如圖2-7所示。每年“雙11”都是一次技術“大考”，技術人員要攻克一個個難關，涉及基礎設施、云計算、大數(shù)據(jù)、AR/VR、人工智能、物聯(lián)網(wǎng)等技術領域。一切關于搜索、推薦、人工智能的技術都需要計算平臺的強力支撐，如果不打破傳統(tǒng)Hadoop框架的“藩籬”，研發(fā)非常高效的離線和實時計算平臺，用戶在交易過程中就不可能有順暢的體驗。這里不探討管理機制，也不深究高深的理論和技術，僅從購物體驗的角度探求算法對保障系統(tǒng)運行的重要作用，介紹購物頁面上體現(xiàn)算法應用的幾個重要功能。1.商品搜索假如你搜索一件商品，你能容忍的最長等待時間是多久？對于大多數(shù)人來說，7秒是極限。在“雙11”巨大的流量下，技術團隊是如何滿足用戶的購物體驗的呢？除了用到數(shù)據(jù)存儲技術、云計算技術，還要用到搜索算法。2.商品排序除了要讓用戶搜索到商品，還要能根據(jù)用戶的需求迅速做出反應，將品牌、銷量、價格、評論數(shù)進行排序顯示，這用到了非常復雜的排序算法。3.廣告系統(tǒng)廣告的推送、展示效果同樣需要一套有效的算法支撐。此外，“雙11”還用到了流量調度算法、對數(shù)據(jù)進行篩選建模的預測算法、洪峰限流中的漏桶算法等。眾多問題的求解都需要算法的支持，算法是計算機科學的核心，也是計算的靈魂，在計算機問題的求解中具有重要的作用。2.4.1算法及其描述1.算法概述算法是解決特定問題的方法或步驟，或者說，算法是為解決一類特定問題而設計的確定的、有限的操作步驟。算法是程序設計的關鍵，找不到算法就無法編寫計算機程序，也就無法用計算機來解決問題。只要把現(xiàn)實中的實際問題描述成一種計算機可接受的算法，就可以用計算機求解這些問題，因此設計算法是程序設計的關鍵。從廣義上講，算法是指通過運算的方式，按照某種機械的步驟逐步求解問題。從狹義上講，算法是解決一個問題采取的方法和步驟的描述，如圖2-8所示。2.算法的分類不是所有算法都適合在計算機上執(zhí)行，能在計算機上執(zhí)行的算法就是計算機算法。計算機算法可以分為兩類，一類是數(shù)值算法（如求方程的根、定積分等），另一類是非數(shù)值算法（如人事管理系統(tǒng)、學生成績管理系統(tǒng)等）。3.算法的特性算法具有以下特性。（1）有窮性。一個算法必須在執(zhí)行有限個計算步驟后終止。（2）確定性。一個算法給出的每個計算步驟都必須是精確定義、無二義性的。（3）有效性。算法中的每個步驟都必須被有效地執(zhí)行，并能得到確定的結果。（4）有零個或多個輸入信息。一個算法可以沒有輸入信息，也可以有一個或多個輸入信息，這些輸入信息是算法的初始數(shù)據(jù)。（5）有一個或多個輸出信息。一個算法應有一個或多個輸出信息，沒有輸出信息的算法是沒有意義的。4.如何發(fā)現(xiàn)算法用計算機求解一個問題通常包括兩個步驟，一是發(fā)現(xiàn)潛在的算法，二是用程序表示并實現(xiàn)算法。發(fā)現(xiàn)算法是一門富有挑戰(zhàn)性的藝術，大致包括以下五個階段。（1）第一階段：分析、理解、抽象、歸納問題。（2）第二階段：尋找一個可能解決問題的思路。（3）第三階段：用數(shù)學語言將其表達出來。（4）第四階段：闡明算法并選用合適的數(shù)據(jù)結構，用程序將其編寫出來。（5）第五階段：評估算法的準確度以及算法是否有潛力作為一個解決問題的工具。這些階段不是一定要遵循的步驟，也不是一定要按順序執(zhí)行，要具體情況具體分析。2.4.2算法的表示形式算法的表示形式很多，通常有自然語言、偽代碼、流程圖、N-S結構化流程圖等。（1）自然語言自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語、英語或其他語言。用自然語言表示算法的優(yōu)點是通俗易懂，缺點是文字冗長，容易出現(xiàn)歧義性。（2）偽代碼偽代碼是介于自然語言和計算機語言之間的文字和符號（包括數(shù)學符號），如同寫一篇文章，自上而下地寫下來，每一行（或幾行）表示一個基本操作。偽代碼不使用圖形符號，因此書寫方便、格式緊湊，也比較易懂，便于向計算機語言程序轉換。（3）流程圖流程圖是一種傳統(tǒng)的算法表示方