程序設(shè)計思想與方法.ppt

程序設(shè)計思想與方法 課程信息 教材 程序設(shè)計思想與方法 問題求解與計算思維 陸朝俊 高教出版社 2013參考書PythonProgramming AnIntroductiontoComputerScience 電子版 HowtoThinkLikeaComputerScientist LearningwithPython 電子版 2 課程信息 下載python軟件的地址https www python org PurdueUniversity的課件地址 http secant cs purdue edu cs190c textsoft09 3 教學方式 課堂教學 每星期四3 4節(jié)講課 演示機房上機單周 3 15周 共7次 周一1 2節(jié) 電院4號樓313教室完成當天上機作業(yè)并提交答疑 4 考核方式 期末考試筆試 占最終成績的50 平時作業(yè)上機作業(yè) 章節(jié)后的作業(yè)ftp上傳給助教 占最終成績的40 自選作業(yè)編一個大程序 期末提交 占最終成績的10 5 第1章計算與計算思維 問題的提出 當今時代 計算機幾乎無處不在 企業(yè)管理產(chǎn)品設(shè)計氣象預報電影制作工業(yè)控制游戲 寫文章 上網(wǎng) 問題 計算機究竟是什么 怎么能做這么多不同的事情 7 計算機 硬件 1 8 計算機 硬件 2 中央處理器 CPU 執(zhí)行指令每條指令只能完成簡單的操作 例如 加法 比較 移動 etc 但按一定的次序執(zhí)行大量簡單指令能完成復雜任務 存儲器 存儲信息 程序和數(shù)據(jù) 主存 CPU能直接訪問 速度快但易失次級存儲器 速度慢但持久輸入 輸出設(shè)備 人機交互 9 9 10 10 10 計算機 軟件 計算機是信息處理機器 信息處理過程由預定的程序控制 單條指令是做不了什么事情的 需要大量指令組成一個逐步執(zhí)行的指令序列 即程序 各種程序統(tǒng)稱為計算機軟件 沒有軟件的計算機毫無用處 10 計算 計算 利用計算機執(zhí)行程序來解決問題 不是狹義的數(shù)學計算 程序使得簡單指令能完成復雜任務 問 只會加法的小學生能完成乘法運算任務嗎 答 能 關(guān)鍵是編寫合適的程序在紙上寫下0 記住結(jié)果 給所記結(jié)果加上第1個n 記住結(jié)果 給所記結(jié)果加上第2個n 記住結(jié)果 給所記結(jié)果加上第m個n 記住結(jié)果 報告結(jié)果 即m n 11 11 12 12 12 通用計算機 計算機是具有如下特征的機器 能夠存儲和處理信息輸入 處理 輸出信息處理由程序控制計算機程序是一個詳細的逐步執(zhí)行的指令序列 告訴計算機該做什么程序可改變 不同的程序完成不同的處理任務計算機執(zhí)行一個程序即可實現(xiàn)一個功能 換著執(zhí)行不同的程序即可實現(xiàn)不同的功能 人們造了各種各樣的計算機 但 所有計算機具有相同的能力 計算機科學 并非研究計算機 計算機之于計算機科學家正如望遠鏡之于天文學家 E W Dijkstra CS研究計算的基礎(chǔ) 實現(xiàn)與應用 例如 CS的一個基本問題 什么是可計算的 本課程的目標 像計算機科學家一樣思考 13 13 程序設(shè)計 計算的關(guān)鍵是程序設(shè)計 編程 給定一個問題 利用計算機支持的簡單操作 設(shè)計出一個操作步驟的序列 計算機執(zhí)行這個序列從而解決問題 學習程序設(shè)計的好處 做計算機的主人提高問題求解能力本身是很有樂趣的智力活動 14 程序設(shè)計語言 問 用什么語言告訴計算機做什么 答 用精確無歧義的程序設(shè)計語言 精確的語法和語義 形式和意義 15 15 程序設(shè)計語言 有不同層次的程序設(shè)計語言計算機的 母語 機器語言例如 0000010000000001 是Intel8086能理解的一條指令將機器語言用助憶符表示 匯編語言上例即 ADDAL 1 需要匯編器處理后機器才懂適合人用的語言 高級語言如 x y 1 需要編譯器或解釋器翻譯后機器才懂 16 16 高級語言 高級程序設(shè)計語言有很多種 據(jù)說2008年網(wǎng)上被引用最多的10個語言是 按字母順序 C C C Java JavaScript Perl PHP Python Ruby SQL 17 程序設(shè)計語言 高級語言的翻譯編譯源代碼編譯成目標代碼 再執(zhí)行一次編譯 多次執(zhí)行 解釋源代碼直接被解釋執(zhí)行每次執(zhí)行都要重新解釋 18 18 編譯vs解釋 思考 為什么高級語言程序具有可移植性 即同一個程序可以在不同廠商的計算機上執(zhí)行 19 Python Python采用編譯 解釋混合方式先編譯成字節(jié)碼 再解釋執(zhí)行安裝Python2 x與新的Python3 x有不兼容的地方啟動Python 20 算法與編碼實現(xiàn) 程序設(shè)計先用非形式化的語言將問題求解步驟表達出來 算法 偽代碼再用形式化的編程語言將上述算法實現(xiàn) 程序代碼 21 算法例 歐幾里德算法 歐幾里德算法 求最大公約數(shù) 輸入 自然數(shù)a b輸出 a b的最大公約數(shù)步驟 第1步 令r為a除以b所得余數(shù)第2步 若r 0 則算法結(jié)束 b即為答案否則置a b b r 轉(zhuǎn)到第1步 22 對算法的要求 算法的每個步驟必須是明確的 可行的 不明確 在菜中放點鹽 不可行 用青菜豆腐做出龍肝鳳髓的美味 每個步驟不必是最底層的瑣細步驟 可以是組合的高級步驟 如 焯水 算法的所有步驟必須在有限時間內(nèi)完成 我們說的計算 即是指 算法計算 用明確可行的基本步驟組成的序列來解決問題 23 24 計算思維 計算思維 computationalthinkin計算機科學家利用計算機 計算過程 解決問題時的思想和方法計算機科學 CS 是關(guān)于 計算 的科學如何像計算機科學家一樣思考 24 25 真的有計算思維嗎 人們在解決不同問題時有不同的思考方式數(shù)學思維 解數(shù)學問題工程思維 工程設(shè)計形象思維 文學創(chuàng)作 計算思維 建立在計算機的能力與局限之上 由于計算機的廣泛應用 計算思維未來會成為人們的基本能力 與閱讀 書寫 算術(shù)能力一樣 計算思維例 問題表示 問題的表示 建模 抽象 將現(xiàn)實中的各種數(shù)量關(guān)系 空間關(guān)系 處理過程抽象為計算機的數(shù)據(jù)結(jié)構(gòu)和控制結(jié)構(gòu)例如 溫度數(shù)據(jù)抽象為數(shù)值還是文字 不同抽象層次問題表示得合適與否直接影響問題的解法的發(fā)現(xiàn)和效率 26 計算思維例 算法設(shè)計 化難為易 分解 約簡 嵌入 轉(zhuǎn)換 模擬 分治法 遞歸法 貪心法 動態(tài)規(guī)劃 遞歸地思考并行處理 27 計算思維例 編程實現(xiàn) 類型系統(tǒng)與類型檢查結(jié)構(gòu)化與模塊化的思考編程范型 過程式 面向?qū)ο?函數(shù)式 程序美學 系統(tǒng)設(shè)計的簡潔與優(yōu)雅 28 計算思維例 計算理論 算法復雜度分析問題的解法是有效率差別的有些問題是難解的尋求近似解問題的可計算性有些問題是不可計算的 29 計算思維例 其他 預取和緩存對最壞情況的預防 保護 恢復啟發(fā)式推理時空等不可兼得要素的權(quán)衡 30 計算思維的特點 是概念化思考 而非編程是基本思考能力 而非機械的套用是人的思考 而非計算機與數(shù)學思維和工程思維相結(jié)合是思想 而非人造物人人皆有 處處皆是 31 生活中的計算思維 算法 最大公約數(shù)查找方法 查黃頁是順序翻找還是借助索引排序 整理撲克牌排隊 先來先處理預取與緩存 書包存放當天上課用的書并行處理 燒菜 32 計算 X 計算數(shù)學 計算幾何 自動定理證明計算物理學計算化學計算生物學 生物信息學計算經(jīng)濟學計算機藝術(shù) 電影特效 計算機作曲繪畫書法 33 計算 X 十二五863計劃 征集重大應用軟件課題聚變與裂變能源數(shù)值模擬真實飛機外型全流場和優(yōu)化設(shè)計數(shù)值模擬航天飛行器全飛行流域數(shù)值模擬新藥研發(fā)與蛋白質(zhì)折疊數(shù)值模擬真實感動漫渲染與創(chuàng)作大型工程設(shè)備結(jié)構(gòu)力學分析復雜電磁環(huán)境數(shù)值模擬新型材料設(shè)計與性能評估 34 2013年諾貝爾化學獎 多尺度復雜化學系統(tǒng)模型 在多尺度模型的輔助下 化學家們讓計算機 做幫手 來揭示化學過程 諾貝爾化學獎評選委員會 對化學家來說 計算機是同試管一樣重要的工具 計算機對真實生命的模擬已為化學領(lǐng)域大部分研究成果的取得立下了 汗馬功勞 35 本課程的定位 學習利用計算機解決問題的思想方法 應用于其他專業(yè)領(lǐng)域不是程序設(shè)計語言課程 編程是計算思維的實踐壞消息 學習編程語言需要掌握非常繁瑣的細節(jié)好消息 Python語言非常簡單 易學易用不是算法和數(shù)據(jù)結(jié)構(gòu)課程 會學習一些基本的知識 36 本課程的定位 續(xù) 計算機科學 程序設(shè)計語言 算法設(shè)計與分析 數(shù)據(jù)結(jié)構(gòu) 理 化 生 經(jīng) 管 金融 工程 數(shù)學 藝術(shù) 計算思維 可計算性理論 37 Python語言 荷蘭人GuidovanRossum于1980年代發(fā)明通用 跨平臺 開源 自由 免費 簡單易學 高度的可讀性支持多種編程范型編譯 解釋源代碼先編譯成字節(jié)碼 再解釋執(zhí)行 38 Python語言 流行編程語言前10名之一 39 Python安裝與運行 版本 教材和上課都采用Python2 7與最新的Python3 x有不兼容的地方 安裝后 啟動Python解釋器命令行GUI 40 第一個程序 HelloWorld 交互方式 print Hello World Hello World 本課程的教學中常用交互方式演示新語句實際上很少用交互方式執(zhí)行程序多次執(zhí)行同一程序需要多次輸入程序多行語句無法一次性執(zhí)行 41 第一個程序 HelloWorld 程序文件將語句保存在純文本文件hello py中四種執(zhí)行方式在IDLE中用RunModule菜單執(zhí)行雙擊hello py文件圖標 importhelloC Python27 pythonhello py print Hello World 42 程序構(gòu)件 數(shù)據(jù) 數(shù)據(jù)是被處理的信息有不同類型的數(shù)據(jù)字符串數(shù)據(jù) print Hello World 數(shù)值數(shù)據(jù) print3 1415 43 程序構(gòu)件 變量 和數(shù)學類似 用一個名字表示可變的數(shù)據(jù)數(shù)學中多用單字母 程序中多用單詞 詞組標識符 Python命名以字母或下劃線開頭 后跟0個或多個字母 數(shù)字 下劃線 區(qū)分大小寫字母 合法 xxYzx 123 w3非法 3qx 123firstname良好的命名風格 有意義 風格一致 44 程序構(gòu)件 表達式 表達式 能計算出一個值 字面值 3 14 hello 變量數(shù)據(jù) 運算符 如 2 3 4 5運算符不同類型的數(shù)據(jù)有不同運算運算符有優(yōu)先級良好編程風格 用空格 括號增加表達式的可讀性 45 程序構(gòu)件 語句 輸出語句我們用語句模板來給出正確用法printprint 賦值語句 x 3 14 printx