Python程序設(shè)計(jì)實(shí)踐 課件 張銀南 ch01 Python程序設(shè)計(jì)實(shí)驗(yàn)的目的與要求 -實(shí)驗(yàn)6 循環(huán)結(jié)構(gòu)程序設(shè)計(jì)

第一章Python程序設(shè)計(jì)實(shí)驗(yàn)的目的與要求浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01Python程序設(shè)計(jì)實(shí)驗(yàn)的目的PARTONE（1）掌握常見問題的求解方法。（2）掌握程序調(diào)試技術(shù)。（3）加深對(duì)語法規(guī)則的理解。（4）培養(yǎng)良好的編程習(xí)慣。（5）熟悉Python程序的集成開發(fā)環(huán)境。02Python程序設(shè)計(jì)實(shí)驗(yàn)的基本要求PARTTWO1.實(shí)驗(yàn)前的準(zhǔn)備工作（1）回顧與本次實(shí)驗(yàn)有關(guān)的知識(shí)內(nèi)容。（2）根據(jù)實(shí)驗(yàn)內(nèi)容，預(yù)先設(shè)計(jì)算法并編寫主要代碼。（3）準(zhǔn)備測(cè)試數(shù)據(jù)。2.實(shí)驗(yàn)中的測(cè)試工作（1）不要只測(cè)試一組數(shù)據(jù)，應(yīng)當(dāng)考慮程序運(yùn)行時(shí)可能出現(xiàn)的各種情況，使用不同的數(shù)據(jù)進(jìn)行測(cè)試。（2）面對(duì)出現(xiàn)的各種錯(cuò)誤，不要灰心，這是初學(xué)者在編程過程中遇到的正?，F(xiàn)象。（3）盡量嘗試自己解決問題，這樣更有利于總結(jié)經(jīng)驗(yàn)。（4）請(qǐng)教師幫助分析錯(cuò)誤時(shí)，注意總結(jié)分析錯(cuò)誤原因，使自己今后再次面對(duì)同類問題時(shí)能舉一反三。3.實(shí)驗(yàn)后的總結(jié)工作（1）自我審查本次實(shí)驗(yàn)是否達(dá)到預(yù)期目標(biāo)。（2）認(rèn)真整理實(shí)驗(yàn)報(bào)告，包括以下幾部分。①實(shí)驗(yàn)?zāi)康暮蛢?nèi)容。②程序設(shè)計(jì)說明（程序結(jié)構(gòu)、算法設(shè)計(jì)等）。③經(jīng)調(diào)試的正確源程序。④程序的運(yùn)行情況（對(duì)不同測(cè)試數(shù)據(jù)的運(yùn)行結(jié)果）。⑤分析程序調(diào)試過程中出現(xiàn)的主要錯(cuò)誤。⑥總結(jié)本次實(shí)驗(yàn)中掌握的程序設(shè)計(jì)方法和編程技巧。03程序的編寫與測(cè)試PARTTHREE語法錯(cuò)誤是指不遵循Python的語法結(jié)構(gòu)引起的錯(cuò)誤，例如括號(hào)不成對(duì)使用等。如果程序中出現(xiàn)語法錯(cuò)誤，Python會(huì)中斷執(zhí)行，返回錯(cuò)誤信息。1.語法錯(cuò)誤常見的語法錯(cuò)誤有以下三種。（1）缺少某些必要的符號(hào)（冒號(hào)、括號(hào)等）。（2）關(guān)鍵字拼寫錯(cuò)誤。（3）縮進(jìn)不正確。語法錯(cuò)誤的示例如下。>>>print('HelloWorld) #引號(hào)不成對(duì)使用SyntaxError:EOLwhilescanningstringliteral語義錯(cuò)誤也稱為邏輯錯(cuò)誤，是指一個(gè)程序可以通過編譯，沒有拋出錯(cuò)誤信息，但得到的結(jié)果是錯(cuò)誤的，或者不是所期望的結(jié)果。這類錯(cuò)誤可能是因?yàn)樗惴ㄔO(shè)計(jì)錯(cuò)誤，也可能是因?yàn)樗惴ㄕ_而編寫程序時(shí)出現(xiàn)差錯(cuò)。2.語義錯(cuò)誤常見的語義錯(cuò)誤有以下三種。（1）缺少某些必要的符號(hào)（冒號(hào)、括號(hào)等）。（2）關(guān)鍵字拼寫錯(cuò)誤。（3）縮進(jìn)不正確。例如，把關(guān)系運(yùn)算符“==”寫成賦值運(yùn)算符“=”，系統(tǒng)無法檢查出這種錯(cuò)誤，只能通過不同的測(cè)試數(shù)據(jù)來檢查程序中可能存在的邏輯錯(cuò)誤。運(yùn)行錯(cuò)誤是指運(yùn)行時(shí)出現(xiàn)的錯(cuò)誤，也叫作“異常”。3.運(yùn)行錯(cuò)誤常見的運(yùn)行錯(cuò)誤有以下三種。（1）除數(shù)為0（ZeroDivisionError）。（2）打開的文件不存在（FileNotFoundError）。（3）導(dǎo)入的模塊沒被找到（ImportError）。運(yùn)行錯(cuò)誤的示例如下。發(fā)現(xiàn)程序中存在錯(cuò)誤時(shí)，需要對(duì)程序進(jìn)行調(diào)試以確定出錯(cuò)位置。常用的調(diào)試方法包括：臨時(shí)增加輸出語句，將要觀察的數(shù)據(jù)顯示在屏幕上；設(shè)置斷點(diǎn)，單步運(yùn)行程序。04人才培養(yǎng)與課程學(xué)習(xí)建議PARTFOUR1.人才培養(yǎng)黨的二十大報(bào)告明確提出：教育、科技、人才是全面建設(shè)社會(huì)主義現(xiàn)代化國家的基礎(chǔ)性、戰(zhàn)略性支撐。報(bào)告指出，我們要堅(jiān)持教育優(yōu)先發(fā)展、科技自立自強(qiáng)、人才引領(lǐng)驅(qū)動(dòng)，加快建設(shè)教育強(qiáng)國、科技強(qiáng)國、人才強(qiáng)國，堅(jiān)持為黨育人、為國育才，全面提高人才自主培養(yǎng)質(zhì)量，著力造就拔尖創(chuàng)新人才，聚天下英才而用之。2.新時(shí)代青年的使命擔(dān)當(dāng)（1）從科技發(fā)展史來看，新時(shí)代青年要發(fā)揚(yáng)斗爭精神，增強(qiáng)斗爭本領(lǐng)，堅(jiān)持團(tuán)結(jié)奮斗，依靠頑強(qiáng)斗爭打開事業(yè)發(fā)展新天地，依靠團(tuán)結(jié)奮斗不斷創(chuàng)造新偉業(yè)、開創(chuàng)新輝煌；認(rèn)識(shí)軟件發(fā)展對(duì)國力的重要性，為實(shí)現(xiàn)中華民族偉大復(fù)興而認(rèn)真學(xué)習(xí)。（2）新時(shí)代青年要增強(qiáng)民族自信心，應(yīng)厚植愛國主義情懷，培養(yǎng)奮斗精神。（3）當(dāng)今世界，新一代信息技術(shù)已成為信息化社會(huì)不可或缺的基礎(chǔ)設(shè)施，計(jì)算機(jī)軟件開發(fā)和應(yīng)用不再僅僅是程序員的專業(yè)技能，還將成為一種生活技能和基本素養(yǎng)。新時(shí)代青年要提升自身的數(shù)字素養(yǎng)，要敢于思考、敢于創(chuàng)新、敢于標(biāo)新立異，要想辦法做新的、比別人強(qiáng)的東西。3.學(xué)習(xí)建議養(yǎng)成良好的編程習(xí)慣，遵循以下步驟。1①上機(jī)實(shí)踐前構(gòu)思程序設(shè)計(jì)思路，認(rèn)真思考。注重認(rèn)識(shí)問題、分析問題、解決問題的步驟和流程。②用心設(shè)計(jì)，遵循?Python?的編程規(guī)范，一絲不茍，哪怕是一個(gè)空格、符號(hào)。③每次上機(jī)實(shí)踐后及時(shí)總結(jié)，把沒有搞清楚的問題記錄下來，進(jìn)行分析。④多使用調(diào)試工具分析程序。⑤注意錯(cuò)誤信息的提示。⑥經(jīng)常使用幫助文檔。3.學(xué)習(xí)建議閱讀、借鑒別人設(shè)計(jì)好的程序。2讀者經(jīng)常有這樣的體會(huì)：

看別人的代碼時(shí)感覺很簡單，自己編寫代碼就容易犯各種錯(cuò)誤。如果遇到問題，通過已有的知識(shí)不能解決，則可以去后面的章節(jié)或其他資料中尋找。這樣，編程水平才能不斷提高。注重實(shí)踐訓(xùn)練。3“Python?程序設(shè)計(jì)”：

是一門對(duì)動(dòng)手能力要求很高的課程，讀者不僅要掌握程序設(shè)計(jì)的理論知識(shí)，還要通過大量的上機(jī)實(shí)踐加強(qiáng)對(duì)理論知識(shí)的掌握，從融會(huì)貫通到實(shí)際應(yīng)用，最終解決相關(guān)專業(yè)領(lǐng)域的實(shí)際問題。做題練習(xí)時(shí)不能直接復(fù)制代碼、提交、判題，而應(yīng)該參考書中的實(shí)現(xiàn)步驟，自己做一遍。之后可以根據(jù)自己對(duì)知識(shí)點(diǎn)的理解，對(duì)實(shí)驗(yàn)內(nèi)容進(jìn)行練習(xí)。3.學(xué)習(xí)建議Python?語言雖然容易上手，并具有眾多優(yōu)點(diǎn)，但要學(xué)好并熟練應(yīng)用于實(shí)際問題并非易事。4

學(xué)習(xí)的過程永遠(yuǎn)不可能一帆風(fēng)順，有樂趣同時(shí)必然有坎坷，讀者要有非常強(qiáng)的耐心和實(shí)踐精神，養(yǎng)成一絲不茍、刻苦鉆研的工匠精神和求真務(wù)實(shí)的科學(xué)精神。注重培養(yǎng)團(tuán)隊(duì)協(xié)作精神。5同學(xué)之間要相互討論，培養(yǎng)團(tuán)隊(duì)協(xié)作精神和溝通交流能力，切實(shí)感受合作、責(zé)任、誠信等職業(yè)素養(yǎng)的內(nèi)涵，打牢成長的思想根基。

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

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

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

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

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

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

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

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

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

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

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

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

算法是解決一個(gè)問題采取的方法和步驟的描述，如圖2-8所示。圖2-8狹義的算法1.算法及其描述算法的分類2不是所有算法都適合在計(jì)算機(jī)上執(zhí)行，能在計(jì)算機(jī)上執(zhí)行的算法就是計(jì)算機(jī)算法。計(jì)算機(jī)算法可以分為兩類：一類是數(shù)值算法，另一類是非數(shù)值算法。1.算法及其描述算法的特性3（1）有窮性一個(gè)算法必須在執(zhí)行有限個(gè)計(jì)算步驟后終止。（2）確定性一個(gè)算法給出的每個(gè)計(jì)算步驟都必須是精確定義、無二義性的。（3）有效性算法中的每個(gè)步驟都必須被有效地執(zhí)行，并能得到確定的結(jié)果。（4）有零個(gè)或多個(gè)輸入信息一個(gè)算法可以沒有輸入信息，也可以有一個(gè)或多個(gè)輸入信息，這些輸入信息是算法的初始數(shù)據(jù)。（5）有一個(gè)或多個(gè)輸出信息一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出信息，沒有輸出信息的算法是沒有意義的。1.算法及其描述如何發(fā)現(xiàn)算法4（1）第一階段：分析、理解、抽象、歸納問題。（2）第二階段：尋找一個(gè)可能解決問題的思路。（3）第三階段：用數(shù)學(xué)語言將其表達(dá)出來。（4）第四階段：闡明算法并選用合適的數(shù)據(jù)結(jié)構(gòu)，用程序?qū)⑵渚帉懗鰜?。?）第五階段：評(píng)估算法的準(zhǔn)確度以及算法是否有潛力作為一個(gè)解決問題的工具。2.算法的表示形式自然語言1自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語、英語或其他語言。用自然語言表示算法的優(yōu)點(diǎn)是通俗易懂，缺點(diǎn)是文字冗長，容易出現(xiàn)歧義性。偽代碼2偽代碼是介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)（包括數(shù)學(xué)符號(hào)），如同寫一篇文章，自上而下地寫下來，每一行（或幾行）表示一個(gè)基本操作。偽代碼不使用圖形符號(hào)，因此書寫方便、格式緊湊，也比較易懂，便于向計(jì)算機(jī)語言程序轉(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）計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算結(jié)構(gòu)。2.常用的數(shù)據(jù)結(jié)構(gòu)（1）數(shù)組（Array）在程序設(shè)計(jì)算法中，為了處理方便，把具有相同類型的若干變量有序地組織起來，這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。數(shù)組是n（n>1）個(gè)相同類型的數(shù)據(jù)元素a0，a1，…，an-1構(gòu)成的有限序列，該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中，可以把它看作一種長度固定的線性表。（2）棧（Stack）棧是只能在某一端插入和刪除數(shù)據(jù)的特殊線性表。它按照“先入后出”的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后進(jìn)入的數(shù)據(jù)在棧頂，讀取數(shù)據(jù)時(shí)從棧頂開始彈出數(shù)據(jù)（最后進(jìn)入的數(shù)據(jù)第一個(gè)被讀?。鐖D2-11所示。特點(diǎn)：先入后出、后入先出；除了頭、尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)后繼和一個(gè)前驅(qū)。2.常用的數(shù)據(jù)結(jié)構(gòu)（3）隊(duì)列（Queue）隊(duì)列是一種特殊的線性表，它只允許在表的前端（Front）進(jìn)行刪除操作，以及在表的后端（Rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列是按照“先入先出”和“后入后出”的原則組織數(shù)據(jù)的。隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。特點(diǎn)：先入先出，后入后出；除了尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)后繼；除了頭節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)。（4）鏈表（LinkedList）鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，它既可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。每個(gè)節(jié)點(diǎn)包括兩部分，一是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，二是存儲(chǔ)下個(gè)節(jié)點(diǎn)地址的指針域。2.常用的數(shù)據(jù)結(jié)構(gòu)（5）樹（Tree）樹是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合，若n=0，稱為空樹；若n>0，則滿足以下兩個(gè)條件。①有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)，它只有直接后繼，但沒有直接前驅(qū)。②除根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)可以劃分為m（m≥0）個(gè)互不相交的有限集合（T0,T1,…,Tm-1），集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹。（6）圖（Graph）圖由節(jié)點(diǎn)的有窮集合V和邊的集合E組成。為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常將節(jié)點(diǎn)稱為頂點(diǎn)，邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。圖被廣泛應(yīng)用于各個(gè)領(lǐng)域，可以解決很多實(shí)際問題。圖的應(yīng)用有求最短路徑、拓?fù)渑判?、關(guān)鍵路徑等。06算法評(píng)價(jià)PARTSIX1.算法的評(píng)價(jià)標(biāo)準(zhǔn)（1）正確性：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足規(guī)定的功能和性能要求。（2）可讀性：算法應(yīng)當(dāng)思路清晰、層次分明、簡單明了、易讀易懂。（3）健壯性：算法應(yīng)具有對(duì)不合理數(shù)據(jù)的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。。（4）高效性：算法應(yīng)有較高的時(shí)間效率。（5）低存儲(chǔ)量需求：存儲(chǔ)量是指算法執(zhí)行過程中需要的最大存儲(chǔ)空間，即有效使用存儲(chǔ)空間。2.時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度（TimeComplexity）是指算法運(yùn)行的時(shí)間，是算法所求解的問題規(guī)模n的函數(shù)，通常記為T(n)。時(shí)間復(fù)雜度是算法的時(shí)間代價(jià)，用執(zhí)行算法所需的基本操作（原操作）次數(shù)來描述，以基本操作重復(fù)執(zhí)行的次數(shù)（稱為頻度）作為算法的時(shí)間度量。許多時(shí)候，要精確地計(jì)算T(n)是困難的。一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的函數(shù)F(n)。例如，一個(gè)算法的運(yùn)行時(shí)間為35n+102，當(dāng)n≥4時(shí)，35n對(duì)算法的運(yùn)行時(shí)間有更大的影響。隨著n逐漸增大，n成為影響算法運(yùn)行的主要因素。但是，n趨于無窮大時(shí)，35n+102就可以寫作O(n)，意味著算法運(yùn)行時(shí)間與輸入規(guī)模呈線性關(guān)系。3.空間復(fù)雜度算法的空間復(fù)雜度（SpaceComplexity）是算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間，記作S(n)=O(f(n))。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般用復(fù)雜度的漸近性來表示。個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間包括以下三個(gè)方面。①存儲(chǔ)算法本身所占用的存儲(chǔ)空間。②算法輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間。③算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。4.時(shí)間復(fù)雜度與空間復(fù)雜度的比較對(duì)于一個(gè)算法，其時(shí)間復(fù)雜度和空間復(fù)雜度往往是相互影響的。追求較好的時(shí)間復(fù)雜度時(shí)，可能會(huì)使空間復(fù)雜度的性能變差，即可能占用較多的存儲(chǔ)空間；追求較好的空間復(fù)雜度時(shí)，可能會(huì)使時(shí)間復(fù)雜度的性能變差，即可能占用較長的運(yùn)行時(shí)間。另外，算法的性能之間存在著或多或少的相互影響。因此，設(shè)計(jì)一個(gè)算法（特別是大型算法）時(shí)，要綜合考慮算法的各項(xiàng)性能（算法的使用頻率、算法處理的數(shù)據(jù)量的大小、算法描述語言的特性、算法運(yùn)行的機(jī)器系統(tǒng)環(huán)境等），才能設(shè)計(jì)出較好的算法。5.提高算法效率的方法①降低程序復(fù)雜度。程序復(fù)雜度主要是指模塊內(nèi)部程序的復(fù)雜度，往往采用McCabe度量法計(jì)算程序模塊中的環(huán)路個(gè)數(shù)。②選用高效率的算法。對(duì)算法的空間復(fù)雜度和時(shí)間復(fù)雜度進(jìn)行優(yōu)化，選擇高效的算法。謝謝觀看第三章典型算法介紹浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01枚舉算法PARTONE1.算法定義枚舉算法（ExhaustAlgorithm）又叫窮舉法，也稱為暴力破解法，是指針對(duì)要解決的問題，列舉出所有可能的情況，逐個(gè)判斷哪些符合問題所要求的約束條件，從而得到問題的解。2.算法特點(diǎn)這種算法充分利用計(jì)算機(jī)語言的循環(huán)結(jié)構(gòu)，其優(yōu)點(diǎn)是思路簡單，程序編寫和調(diào)試都很方便。如果問題規(guī)模不是很大，要在規(guī)定的時(shí)間與空間內(nèi)求出解，那么枚舉算法是最直接、簡單的選擇。這種算法的缺點(diǎn)是運(yùn)算量比較大、解題效率不高。如果枚舉范圍太大（超過2000000次），會(huì)花費(fèi)大量時(shí)間。3.算法思路這種算法的基本思想是根據(jù)問題的條件確定大致范圍，并在該范圍內(nèi)進(jìn)行窮舉并驗(yàn)證，直到問題得到解決。這種算法一般用于決策最優(yōu)化問題，適合那些很難找到大、小規(guī)模之間的關(guān)系，也不易進(jìn)行分解的問題。第一步確定解題范圍，枚舉出所有可能的解。第三步使可能解的范圍降至最小，以便提高解題效率。第二步判斷是否符合正解的條件。4.算法案例【例】“百雞百錢”問題中國古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出了著名的“百雞百錢”問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，問雞翁、雞母、雞雛各幾何？（已知公雞每只5元，母雞每只3元，小雞1元3只。要求用100元正好買100只雞，問公雞、母雞、小雞各買多少只？）題目分析：設(shè)買x只公雞、y只母雞、z只小雞，則問題轉(zhuǎn)化為三元一次方程組，即x+y+z=100（百雞），5x+3y+z/3=100（百錢），1個(gè)方程無法解出3個(gè)變量，只能將各種可能的取值代入，求出能使兩個(gè)方程成立的解。雞和錢的總數(shù)都是100，因此可以確定x、y、z的取值范圍。x的取值范圍為1～20（100/5=20），y的取值范圍為1～33（100/3≈33），z的取值范圍為1～99，求解流程圖如圖3-1所示。02遞歸算法PARTTWO1.算法定義遞歸算法（RecursionAlgorithm）把問題轉(zhuǎn)化為同類問題的子問題，然后通過遞歸調(diào)用過程（或函數(shù)）表示問題的解。一個(gè)程序過程（或函數(shù)）直接或間接調(diào)用自己本身，這種過程（或函數(shù)）稱為遞歸過程（或函數(shù)）。

遞歸調(diào)用分為直接遞歸和間接遞歸。直接遞歸是指在過程中調(diào)用方法本身，間接遞歸是指間接地調(diào)用一個(gè)過程。一般來說，遞歸算法需要有邊界條件、遞歸前進(jìn)段、遞歸返回段。不滿足邊界條件時(shí)，遞歸前進(jìn)；滿足邊界條件時(shí)，遞歸返回。2.算法特點(diǎn)遞歸過程一般通過函數(shù)或子過程來實(shí)現(xiàn)，在函數(shù)或子過程的內(nèi)部直接或間接地調(diào)用自身，常用于一些有明顯遞推性質(zhì)的問題。遞歸算法的優(yōu)點(diǎn)

代碼簡潔、清晰、可讀性好。遞歸算法的缺點(diǎn)

遞歸形式比非遞歸形式的運(yùn)行速度慢。如果遞歸層次太深，會(huì)導(dǎo)致堆棧溢出。雖然算法代碼通常顯得很簡潔，但遞歸算法的運(yùn)行效率較低。所以，如果有別的算法可行，一般不提倡用遞歸算法設(shè)計(jì)程序。3.算法思路遞歸

把一個(gè)問題歸結(jié)為一個(gè)或多個(gè)規(guī)模更小的子問題，然后用同樣的方法求解規(guī)模更小的子問題，要求子問題與原問題是同一類型，以保證可用同樣的方法求解。如此下去，直到子問題的規(guī)模小到可以直接求解。遞歸算法有以下三個(gè)基本要求。①每次循環(huán)都必須使問題規(guī)模變小。②遞歸操作中相鄰的兩步是緊密關(guān)聯(lián)的，在返回到上一層的操作中，前一次的輸出信息是后一次的輸入信息。③當(dāng)子問題的規(guī)模足夠小時(shí)，能直接求出該子問題的解，也就是說必須具備結(jié)束遞歸的初始條件。4.算法案例【例】階乘問題階乘（Factorial）是指1到n之間的所有自然數(shù)相乘的結(jié)果。在進(jìn)行問題求解前，首先分析下面的分段函數(shù)。f(n)=1，n=1f(n)=nf(n-1)，n>1編寫程序時(shí)，以fact()函數(shù)的調(diào)用過程為例，遞歸調(diào)用分為遞推和回歸兩個(gè)階段，如圖3-2所示。遞歸調(diào)用4.算法案例【例】漢諾塔（Hanoi）問題漢諾塔問題是一個(gè)古典數(shù)學(xué)問題，只能用遞歸算法來解決。有一個(gè)漢諾塔，塔內(nèi)有A、B、C三個(gè)座。開始時(shí)A上有64個(gè)盤子，盤子的大小不同，大的在下面，小的在上面，如圖3-3所示?，F(xiàn)有一個(gè)和尚想將這64個(gè)盤子從A移動(dòng)到C上，但他每次只能移動(dòng)一個(gè)盤子。在移動(dòng)過程中，必須保持A、B、C上的盤子是大盤在下、小盤在上的狀態(tài)。在移動(dòng)過程中可以利用B，請(qǐng)分析移動(dòng)過程。漢諾塔4.算法案例首先考慮A上最下面的盤子，如果能將它上面的63個(gè)盤子移動(dòng)到C上，則完成任務(wù)，具體步驟如下。①將A最上面的63個(gè)盤子移動(dòng)到B上。②將A上剩下的一個(gè)盤子移動(dòng)到C上。③將B上的63個(gè)盤子移動(dòng)到C上。如果能完成上述三步，則完成任務(wù)，這種方法就是遞歸的思考方法。為了將A最上面的63個(gè)盤子移動(dòng)到B上，還需要做以下工作。①將A最上面的62個(gè)盤子移動(dòng)到C上。②將A上剩下的一個(gè)盤子移動(dòng)到B上。③將C上的62個(gè)盤子移動(dòng)到B上。03分治算法PARTTHREE1.算法定義分治算法

將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題（這些子問題相互獨(dú)立且與原問題的性質(zhì)相同），再把子問題分成更小的子問題，直到子問題可以直接進(jìn)行求解，原問題的解即為子問題解的合并。任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易求解，所需的計(jì)算時(shí)間也越少?！胺侄沃奔记墒呛芏喔咝惴ǖ幕A(chǔ)，如排序算法（快速排序、歸并排序等）、傅里葉變換（快速傅里葉變換）等。由分治算法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。2.算法特點(diǎn)當(dāng)問題的規(guī)?？s小到一定程度時(shí)，就可以容易地解決。如果問題可以分解為若干個(gè)規(guī)模較小的相同問題，則該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。利用子問題的解可以合并出問題的最終解。所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。010203043.算法思路（1）分解將要解決的問題劃分成若干規(guī)模較小的同類問題。（2）求解當(dāng)子問題劃分得足夠小時(shí)，用較簡單的方法解決。（3）合并按原問題的要求，將子問題的解逐層合并，構(gòu)成原問題的解。4.算法案例【例】在有序數(shù)據(jù)數(shù)列中查找給定的數(shù)設(shè)n個(gè)有序數(shù)（從小到大排序）存放在數(shù)組a[0]～a[n-1]中，要查找的數(shù)為x。用變量bot、top、mid分別表示所查找的數(shù)據(jù)范圍的底部（序列的下界）、頂部（序列的上界）、中間（mid=(bot+top)/2），算法如下。（1）如果x=a[mid]，則已找到給定的數(shù)，退出循環(huán)，否則進(jìn)行下面的判斷。（2）如果x<a[mid]，則x必定在bot～mid-1范圍內(nèi)，即top=mid-1。（3）如果x>a[mid]，則x必定在mid+1～top范圍內(nèi)，即bot=mid+1。（4）確定了新的查找范圍后，重復(fù)進(jìn)行以上比較，直到找到給定的數(shù)或top≤bot。04遞推算法PARTFOUR1.算法定義遞推算法一種簡單的算法，即通過已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果。順推法從已知條件出發(fā)，逐步推算出要解決的問題。逆推法從已知問題的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問題的開始條件，即順推法的逆過程。3.算法思路遞推算法的本質(zhì)按規(guī)律逐次推出（計(jì)算）下一步的結(jié)果，所以更多用于計(jì)算。遞推算法是計(jì)算序列的一種常用算法，其思想是把一個(gè)復(fù)雜的、龐大的計(jì)算過程轉(zhuǎn)化為簡單過程的多次重復(fù)，利用了計(jì)算機(jī)速度快和“不知疲倦”的特點(diǎn)。第一步確定問題的數(shù)據(jù)信息之間存在著特定的遞推關(guān)系，并用數(shù)學(xué)公式描述出來。第三步盡量使用簡單變量，使計(jì)算的過程值暫用的空間量少，以便提高解題效率。第二步確定由已知的基礎(chǔ)數(shù)據(jù)可以遞推出后面的數(shù)據(jù)。4.算法案例【例】斐波那契數(shù)列（FibonacciSequence）問題斐波那契數(shù)列是：1，1，2，3，5，8，13，21，34，55，89，144…，求第n項(xiàng)的值。設(shè)它的函數(shù)為F(n)，已知F(1)=1、F(2)=1，那么F(n)=F(n-1)+F(n-2)(n≥3)，則通過順推可以知道，F(xiàn)(3)=F(1)+F(2)=2、F(4)=F(2)+F(3)=3……只要配合循環(huán)控制序列項(xiàng)編號(hào)，就很容易得到想要的項(xiàng)值。05貪心算法PARTFIVE1.算法定義貪心算法將問題的求解過程看作一系列選擇，它所作的每一個(gè)選擇都是當(dāng)前狀態(tài)下某種意義上的最優(yōu)解（即貪心選擇），并期望通過每次所作的貪心選擇（局部最優(yōu)解）導(dǎo)致最終結(jié)果是問題的一個(gè)最優(yōu)解或近似最優(yōu)解。2.算法特點(diǎn)有一個(gè)以最優(yōu)方式解決的問題。為了構(gòu)造問題的解決方案，有一個(gè)候選的對(duì)象的集合。隨著算法的進(jìn)行，將積累起其他兩個(gè)集合，一個(gè)包含已經(jīng)被考慮過并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過但被丟棄的候選對(duì)象。有一個(gè)函數(shù)來檢查一個(gè)候選對(duì)象的集合是否提供了問題的解答，該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。選擇函數(shù)可以指出哪個(gè)剩余的候選對(duì)象最有希望構(gòu)成問題的解。01020304053.算法思路貪心算法的主要思路如下。①建立數(shù)學(xué)模型來描述問題。②把求解的問題分成若干個(gè)子問題。③對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。④把子問題的局部最優(yōu)解合成原來問題的一個(gè)解。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對(duì)某問題選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪心算法求解特別有效。4.算法案例【例】背包問題（KnapsackProblem）假設(shè)有n個(gè)物品和一個(gè)背包，物品i的重量是Wi，價(jià)值為Pi，背包的載荷能力為M。對(duì)于任一物品，該物品只能裝入一次，并且不能只裝入物品的一部分（要么整體裝入背包，要么不裝入）。請(qǐng)問：如何選擇物品，才能使裝入背包中的物品的總價(jià)值最大？將該問題轉(zhuǎn)化成數(shù)學(xué)語言。給定M>0、Wi>0、Pi>0（1≤i≤n），要求找出一個(gè)n元向量（X1，X2，…，Xn），使得∑WiXi≤M，而且∑PiXi最大。4.算法案例【例】旅游路徑的選擇貪心算法也很適合用于旅游路徑的選擇，如圖所示，假如要從節(jié)點(diǎn)5走到節(jié)點(diǎn)3，最短的路徑是什么呢？以貪心算法來說，當(dāng)然是先走到節(jié)點(diǎn)1，接著走到節(jié)點(diǎn)2，最后走到節(jié)點(diǎn)3，這樣的距離是28?？墒菑膱D中我們發(fā)現(xiàn)直接從節(jié)點(diǎn)5走到節(jié)點(diǎn)3才是最短的距離，也就是說，在這種情況下無法用貪心算法找到最佳的解決方案。旅游路徑的選擇06回溯算法PARTSIX1.算法定義回溯算法（Back-TrackingAlgorithm）一種“選優(yōu)”的搜索方法，按照“選優(yōu)”的條件向前搜索，以達(dá)到目標(biāo)；如果搜索到某一步時(shí)，發(fā)現(xiàn)原先的選擇并不“優(yōu)”或達(dá)不到目標(biāo)，就退一步重新選擇，這種走不通就退回再走的技術(shù)就是回溯算法。2.算法特點(diǎn)回溯算法

沿著一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試?；厮菟惴ㄔ诿詫m搜索中很常見，如果某條路走不通，就返回前一個(gè)路口，繼續(xù)探尋下一條路?；厮菟惴ㄆ鋵?shí)就是一種枚舉算法。不過回溯算法使用剪枝函數(shù)，剪去一些不可能到達(dá)最終狀態(tài)（即答案）的節(jié)點(diǎn)，從而減少狀態(tài)空間樹的節(jié)點(diǎn)。3.算法思路通過對(duì)問題的分析，找出一個(gè)解決問題的線索，然后沿著這個(gè)線索向前試探，若試探成功，就得到解；若試探失敗，就逐步往回退，換別的路線再向前試探?；厮菟惴▽?shí)際上是廣度與深度結(jié)合的搜索方法，深度搜索過程中碰到條件不滿足的情況，則退回上一層，進(jìn)行全面的搜索。4.算法案例【例】老鼠走迷宮一只老鼠在一個(gè)n×n迷宮的入口處，它想吃迷宮出口處放著的奶酪，這只老鼠能否吃到奶酪？如果可以吃到，請(qǐng)給出一條從入口到奶酪的路徑。老鼠在迷宮的入口處，迷宮中有許多墻，使大部分路徑都被擋住而無法前進(jìn)。老鼠可以采用嘗試錯(cuò)誤的方法找到出口。不過，這只老鼠必須能在走錯(cuò)路時(shí)重來一次并把走過的路記下來，避免下次走同樣的路，直到找到出口。老鼠行進(jìn)時(shí)，必須遵守以下三個(gè)原則。①一次只能走一格。②遇到墻無法往前走時(shí)，退回一步找找看是否有其他路可以走。③走過的路不會(huì)再走第二次。4.算法案例在編寫走迷宮程序之前，我們先來了解如何在計(jì)算機(jī)中表現(xiàn)一個(gè)仿真迷宮。這時(shí)可以使用二維數(shù)組，并符合以下規(guī)則。maze[i][j]=1表示[i][j]處有墻，無法通行。maze[i][j]=0表示[i][j]處無墻，可通行。一個(gè)10×10的迷宮如圖所示，灰色部分是墻，白色部分是可以走的路。迷宮的入口在上面，出口在右側(cè)。4.算法案例這個(gè)迷宮其實(shí)是由10×10=100個(gè)格子組成的，灰色格子代表墻，白色格子代表路，如圖(a)所示?！盎疑褡哟韷?，白色格子代表路”是用語言形式描述的，需要轉(zhuǎn)換成數(shù)學(xué)形式，用1和0分別定義灰色格子和白色格子，如圖(b)所示。4.算法案例從數(shù)學(xué)的角度分析老鼠走迷宮的過程。假設(shè)老鼠從左上角的maze[0][3]進(jìn)入，從右下角的maze[7][9]出來，老鼠的當(dāng)前位置用maze[x][y]表示，如圖所示。老鼠可以選擇的方向共有四個(gè)，分別是東、南、西、北。但是，并非每個(gè)位置都有四個(gè)方向可以選擇，必須視情況而定，例如“T”形路口就只有三個(gè)方向可以選擇。4.算法案例我們可以使用鏈表來記錄走過的位置，并將走過的位置對(duì)應(yīng)的數(shù)組元素內(nèi)容標(biāo)記為2，然后將這個(gè)位置放入棧，再進(jìn)行下一次選擇。如果走到死胡同還沒有扺達(dá)終點(diǎn)，那么就退回上一個(gè)岔路口，再選擇其他路。每次新加入的位置必定在棧的頂端，因此棧頂端指針?biāo)傅姆礁窬幪?hào)便是當(dāng)前老鼠所在的位置。重復(fù)這些動(dòng)作，直到走到出口。07迭代算法PARTSEVEN1.算法定義迭代算法在數(shù)學(xué)上也稱為“遞推法”，是一種不斷用舊值遞推新值的過程，在解決問題時(shí)，總是重復(fù)利用一種方法。2.算法特點(diǎn)迭代算法利用計(jì)算機(jī)運(yùn)算速度快、適合重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)重復(fù)執(zhí)行一組指令（或一定步驟），每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。使用迭代算法解決問題時(shí)，需要做以下三個(gè)工作。①確定迭代變量。②建立迭代關(guān)系式。③對(duì)迭代過程進(jìn)行控制，確定在什么時(shí)候結(jié)束迭代過程。3.算法思路對(duì)于要求解的值，由一個(gè)給定的初值，通過某一算法（迭代公式）可求得新值，通常該新值比初值更接近要求解的值，再由新值按照同樣的算法求得另一個(gè)新值，這樣經(jīng)過有限次迭代即可求得其解。4.算法案例

謝謝觀看實(shí)驗(yàn)0Python環(huán)境配置浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01Python開發(fā)環(huán)境的建立過程PARTONE從Python官網(wǎng)下載適合操作系統(tǒng)的安裝包1枚舉算法（ExhaustAlgorithm）又叫窮舉法，也稱為暴力破解法，是指針對(duì)要解決的問題，列舉出所有可能的情況，逐個(gè)判斷哪些符合問題所要求的約束條件，從而得到問題的解。運(yùn)行安裝包，根據(jù)安裝向?qū)нM(jìn)行安裝2在自定義安裝界面中，勾選“Addpython.exetoPath”選項(xiàng)，將Python解釋器的路徑添加到系統(tǒng)路徑中。如果需要第三方庫，可以在cmd命令行窗口中運(yùn)行“pipinstall庫名”命令，安裝第三方庫。3Python的安裝包自帶命令行交互環(huán)境和IDLE集成開發(fā)環(huán)境，如果需要其他集成開發(fā)環(huán)境（如PyCharm、Anaconda等），可自行下載、安裝。402Python解釋器及其使用PARTTWOIDLE（IntegratedDevelopmentandLearningEnvironment）

Python的集成開發(fā)和學(xué)習(xí)環(huán)境，有兩種使用模式，即交互模式和文件模式。

（1）進(jìn)入命令行窗口，輸入“Python”，看到“>>>”提示符就說明處于交互模式。（2）打開IDLE開發(fā)環(huán)境，依次選擇“File”→“NewFile”選項(xiàng)，可以輸入代碼，也可以通過文件模式編寫Python程序。在編輯框中輸入代碼，按下“F5”鍵，或在菜單中依次選擇“Run”→“RunModule”選項(xiàng)，觀察運(yùn)行結(jié)果。03第三方庫的安裝與配置PARTTHREE包管理器一種可以簡化安裝過程、高效管理依賴關(guān)系、進(jìn)行版本控制的工具。Pip管理Python第三方庫的重要工具，它不僅可以查看已安裝的Python第三方庫列表，還可以安裝、升級(jí)、卸載Python第三方庫。04其他主流開發(fā)環(huán)境的安裝與配置PARTFOUR1.AnacondaAnaconda是一款方便的Python包管理和環(huán)境管理軟件，預(yù)裝了許多常用的Python庫，包括numpy、pandas等。同時(shí)，Anaconda捆綁了兩個(gè)好用的交互式代碼編輯器Spyder和JupyterNotebook。JupyterNotebook是基于網(wǎng)頁的用于交互計(jì)算的應(yīng)用程序，可被應(yīng)用于全過程計(jì)算、開發(fā)、編寫文檔、運(yùn)行代碼、展示結(jié)果等。2.PyCharmPyCharm是一款功能強(qiáng)大的Python編輯器，具有集成單元測(cè)試、代碼檢測(cè)、集成版本控制、代碼重構(gòu)、突出顯示等功能，同時(shí)具有跨平臺(tái)性。Professional表示專業(yè)版，需要付費(fèi)使用；Community表示社區(qū)版，可以免費(fèi)使用。謝謝觀看實(shí)驗(yàn)1數(shù)據(jù)的輸入和輸出浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01輸入函數(shù)PARTONEinput()函數(shù)

用于獲取用戶輸入的數(shù)據(jù)，并存儲(chǔ)在指定的變量中，其基本格式如下。prompt參數(shù)用于提示的文字。需要說明的是，在支持在線判題的程序設(shè)計(jì)類實(shí)驗(yàn)輔助教學(xué)平臺(tái)（PTA）上，編寫輸入函數(shù)時(shí)一般不加prompt參數(shù)，以免干擾評(píng)判；但在實(shí)際項(xiàng)目開發(fā)過程中，一般會(huì)加上提示性信息，使程序具有更好的用戶友好性。input()函數(shù)默認(rèn)接收字符串類型，可以利用eval()函數(shù)轉(zhuǎn)換成數(shù)值類型。另外，可以利用map()、split()等函數(shù)的組合將多個(gè)數(shù)據(jù)分別賦給多個(gè)變量。內(nèi)置函數(shù)map(func,序列)可以把一個(gè)函數(shù)依次映射到序列或迭代器對(duì)象的每個(gè)元素上，并返回一個(gè)map對(duì)象作為結(jié)果，map對(duì)象中的每個(gè)元素是原序列中的對(duì)應(yīng)元素經(jīng)函數(shù)處理后的結(jié)果。02輸出函數(shù)PARTTWOprint()函數(shù)的基本格式如下。1用“%”格式化輸出內(nèi)容的基本格式如下。2搭配format()函數(shù)進(jìn)行格式化輸出。3Python3.8之后的版本支持用f-string格式輸出。4謝謝觀看實(shí)驗(yàn)2turtle繪圖浙江省普通本科高校“十四五”重點(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程Python的標(biāo)準(zhǔn)庫很多，主要有math庫、turtle庫、random庫、time庫等。下面主要介紹turtle庫的含義和作用。turtle（海龜）庫用于獲取用戶輸入的數(shù)據(jù)，并存儲(chǔ)在指定的變量中，其基本格式Python語言中一個(gè)很流行的繪制圖形的函數(shù)庫，用于繪制線、圓及其他形狀?？梢园延胻urtle庫繪圖理解成一只海龜在坐標(biāo)系統(tǒng)中爬行，其爬行軌跡形成了繪制的圖形。用戶可以控制海龜?shù)奈恢?、方向，以及畫筆的狀態(tài)、寬度、顏色等，圖形繪制的過程十分直觀。。turtle庫需要先導(dǎo)入才能使用，導(dǎo)入和使用的方式如下。（1）先用“importturtle”語句導(dǎo)入庫，之后可以用“turtle.函數(shù)名()”的形式使用庫。（2）先用“fromturtleimport*”語句導(dǎo)入庫，然后可以直接用“函數(shù)名()”的形式使用庫，無須加庫名。（3）先用“importturtleast”語句導(dǎo)入庫，此時(shí)為庫準(zhǔn)備了別名t，故可以用“t.函數(shù)名()”的形式使用庫。01畫布設(shè)置PARTONE

setup()函數(shù)的4個(gè)參數(shù)分別表示窗口寬度、窗口高度、窗口左上角在計(jì)算機(jī)屏幕中的橫坐標(biāo)和縱坐標(biāo)。02畫筆的基本參數(shù)設(shè)置函數(shù)PARTTWO方法功能pensize(width)設(shè)置畫筆寬度；單位是像素pencolor(color)設(shè)置畫筆顏色；若無參數(shù)，則返回當(dāng)前的畫筆顏色penup()提起畫筆，用于移動(dòng)畫筆位置；與pendown()配合使用pendown()放下畫筆，移動(dòng)畫筆將繪制圖形speed(speed)設(shè)置畫筆移動(dòng)速度；speed為0～10的整數(shù)03畫筆運(yùn)動(dòng)命令函數(shù)PARTTHREE方法功能forward(distance)向當(dāng)前方向移動(dòng)distance像素backward(distance)向相反方向移動(dòng)distance像素right(angle)向右（順時(shí)針方向）轉(zhuǎn)動(dòng)angle角度left(angle)向左（逆時(shí)針方向）轉(zhuǎn)動(dòng)angle角度goto(x,y)將畫筆移動(dòng)到坐標(biāo)為(x,y)的位置circle(radius,extent,steps)畫圓?。籸adius參數(shù)用于設(shè)置半徑；extent參數(shù)（可選）用于設(shè)置弧的角度（缺省則繪制整圓）；steps參數(shù)（可選）用于確定繪制的正多邊形邊數(shù)，若steps=3，則繪制正三角形setx(x)將x軸移動(dòng)到指定位置；單位為像素sety(y)將y軸移動(dòng)到指定位置；單位為像素setheading(angle)設(shè)置當(dāng)前方向?yàn)閍ngle角度home()將當(dāng)前的畫筆位置設(shè)置為原點(diǎn)dot(r)繪制一個(gè)指定直徑和顏色的圓點(diǎn)04畫筆控制命令函數(shù)PARTFOUR方法功能fillcolor(colorstring)設(shè)置填充顏色；若無參數(shù)，則返回當(dāng)前的填充顏色color(color1,color2)同時(shí)設(shè)置pencolor=color1，fillcolor=color2方法功能filling()返回當(dāng)前是否在填充狀態(tài)begin_fill()開始填充end_fill()結(jié)束填充hideturtle()隱藏畫筆showturtle()顯示畫筆05其他命令函數(shù)PARTFIVE方法功能clear()清空窗口，但畫筆的位置和狀態(tài)不會(huì)改變r(jià)eset()清空窗口，重置為起始狀態(tài)write(s)寫文本mainloop()或done()啟動(dòng)事件循環(huán)謝謝觀看實(shí)驗(yàn)3運(yùn)算符與表達(dá)式浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01計(jì)算機(jī)程序要處理的數(shù)據(jù)必須放入內(nèi)存中，Python中的所有數(shù)據(jù)都是對(duì)象PARTONE變量是指向?qū)ο蟮囊茫窃诔绦蜻\(yùn)行過程中值會(huì)發(fā)生變化的量。02Python標(biāo)識(shí)符通常用作變量、函數(shù)、類及其他對(duì)象的名稱PARTTWOPython標(biāo)識(shí)符一般由字母、數(shù)字、下畫線構(gòu)成，且不能以數(shù)字開頭。例如，a、A、_s、py_1等是合法的標(biāo)識(shí)符，而1a、ab、a.b等是非法的標(biāo)識(shí)符。標(biāo)識(shí)符區(qū)分字母的大小寫。例如，max、Max是兩個(gè)不同的標(biāo)識(shí)符。注意：用戶自定義標(biāo)識(shí)符不能與關(guān)鍵字同名。關(guān)鍵字可通過調(diào)用內(nèi)置函數(shù)help()查看。03表達(dá)式是可以進(jìn)行計(jì)算的代碼片段，由操作數(shù)和運(yùn)算符構(gòu)成PARTTH