大學計算機基礎.ppt

多媒體技術(shù) 計算機應用基礎 計算機學院王文明wenmingwang2004 studentbit 交作業(yè) 第8章程序設計基礎 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 講授提綱 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 計算機與家用電器的根本區(qū)別是什么 計算機能夠完成預定的任務是硬件和軟件協(xié)同工作的結(jié)果當今計算機之所以能夠在各行各業(yè)得以廣泛應用是因為計算機內(nèi)安裝有豐富的軟件這些豐富的軟件是人們根據(jù)社會需求隨時隨地設計編寫出來的這就是計算機比電視機 DVD機等家用電器更加靈活 功能可以隨時隨地不斷增強的原因 結(jié)論 設計出新軟件增加計算機的 能力 算法設計概述 四十年代計算機能 科學計算 六十年代計算機能 信息管理 八十年代計算機能 企業(yè)管理 新世紀計算機能 電子商務 電子政務 今后的計算機能 算法設計概述 程序 軟件 算法 程序設計 程序設計語言 程序是用計算機語言表示的一系列有序指令的集合 用來完成指定的任務軟件是計算機程序 方法和規(guī)則 相關(guān)的文檔資料以及在計算機上運行它所必需的數(shù)據(jù)的總稱注意程序和軟件是兩個不同的概念 算法設計概述 計算器程序 6 1程序設計概述 基本術(shù)語 空當接龍游戲程序 6 1程序設計概述 基本術(shù)語 聲音信息編輯程序 6 1程序設計概述 基本術(shù)語 軟件示意圖 程序設計指的是安排計算機按人們的意志去工作 程序設計往往是一個過程 這個過程主要包括 算法設計概述 程序設計是具有一種知識背景的人為具有另一種知識背景的人進行的創(chuàng)造性勞動 程序設計是運用計算機能夠理解的語言告訴計算機如何工作 算法設計概述 程序設計語言是人與計算機交流和溝通的工具 是用來編寫計算機程序的工具 又稱計算機語言 程序設計語言目前有幾百種 最常用的不過十多種 算法指為解決一個問題而采取的方法和步驟 注意 算法是解決問題的方法和步驟但它不是計算機可以直接執(zhí)行的只是人們編制程序前對問題處理思想的一種描述只有將算法轉(zhuǎn)變?yōu)槌绦虿拍茏層嬎銠C求解問題 算法設計概述 樂譜是算法 算法設計概述 乘法口訣表是算法 1 1 12 1 22 2 43 1 33 2 63 3 9 9 1 99 2 18 9 9 81 算法設計概述 規(guī)劃是算法 算法設計概述 做任何事情都必須事先想好行動步驟 然后按步驟行動做同一件事情可以有不同的行動步驟或方法 即算法 算法的優(yōu)劣直接影響完成任務 或解決問題 的好壞和效率 算法設計概述 算法設計概述 講授提綱 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 算法可用各種方法加以描述 常用下面兩種 偽代碼 英文 中文 類Pascal 類C語言 流程圖 框形 盒圖 PAD圖 算法設計概述 介于自然語言和計算機語言之間的一種語言例如介于中文和C 語言之間例如介于英語和BASIC語言之間例如介于苗族語言和FORTRAN語言之間 算法設計概述 計算1 2 1000的偽代碼算法描述如下 分析 根據(jù)數(shù)學上可以推導出計算公式 1 1000 1000 通過計算公式來求解得出結(jié)果 具體偽代碼描述如下 步驟1 計算 1 1000 1000 2 將結(jié)果再放入SUM中步驟2 輸出 或顯示 SUM的值 算法設計概述 計算任務 的另一種偽代碼算法描述如下 分析 下面按小學生的計算方法來求解 就是從1開始反復加上計算式子中后面的整數(shù) 直到加上1000停止 具體偽代碼描述如下 步驟1 使SUM 0步驟2 使I 1步驟3 計算SUM I 將和值再放入SUM中步驟4 計算I 1 將和值再放入I中步驟5 如果I 1000 則轉(zhuǎn)到步驟3 否則轉(zhuǎn)下一步步驟6 輸出 或顯示 SUM的值 算法設計概述 計算任務 還有另一種偽代碼算法描述嗎 分析 還是按小學生的計算方法來求解 就是從1000開始反復加上計算式子中前面的整數(shù) 直到加上1停止 具體偽代碼描述如下 步驟1 使SUM 0步驟2 使I 1000步驟3 計算SUM I 將和值再放入SUM中步驟4 計算I 1 將和值再放入I中步驟5 如果I 1 則轉(zhuǎn)到步驟3 否則轉(zhuǎn)下一步步驟6 輸出 或顯示 SUM的值 算法設計概述 偽代碼描述不夠形象直觀所謂流程圖是采用圖形符號來表示各種操作步驟常用流程圖符號如下表 算法設計概述 計算1 2 1000的流程圖算法描述如下 分析 根據(jù)數(shù)學上可以推導出計算公式 1 1000 1000 通過計算公式來求解得出結(jié)果 具體流程圖描述如下 SUM 1 1000 1000 2 開始 輸出SUM 結(jié)束 算法設計概述 計算任務 的另一種流程圖算法描述如下 分析 下面按小學生的計算方法來求解 就是從1開始反復加上計算式子中后面的整數(shù) 直到加上1000停止 具體流程圖描述如右面所示 開始 SUM 0 I 1 SUM SUM I I I 1 輸出SUM 結(jié)束 I 1000 成立 不成立 算法設計概述 計算任務 還有另一種流程圖算法描述嗎 分析 下面按小學生的計算方法來求解 就是從1000開始反復加上計算式子中前面的整數(shù) 直到加上1停止 具體流程圖描述如右面所示 開始 SUM 0 I 1000 SUM SUM I I I 1 輸出SUM 結(jié)束 I 1 成立 不成立 還有嗎 算法設計概述 講授提綱 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 6 5程序設計過程 用具體例子說明程序設計全過程 實際問題求任意兩個正整數(shù)中的最大公因數(shù) 6 5程序設計過程 所謂問題定義是將解決問題分析界定清楚 即計算機解決問題的可行性研究實際上就是回答下列問題 解決的是什么問題 是否能夠解決 能解決到什么程度 原始數(shù)據(jù)如何得到 最后結(jié)果如何反映 在什么軟硬件環(huán)境下解決問題 需要多少時間 經(jīng)費 人員 效益如何 6 5程序設計過程 問題定義 給定兩個正整數(shù)P和Q 求其最大公因數(shù)p和q只能是正整數(shù)的子集最大公因數(shù)的定義 能整除P Q 且是最大的除數(shù)p和q數(shù)值通過鍵盤錄入結(jié)果顯示在屏幕上普通PC機環(huán)境均可這是小問題 一個人在短時間內(nèi)即可完成值得一提 這是初學者認為最簡單而在實際程序開發(fā)工程中最難的工作 在軟件工程中被稱作 需求分析 6 5程序設計過程 問題定義 問題定義確定了未來程序的輸入 處理 輸出 IPO 即Input Process Output 等等可行性研究的相關(guān)結(jié)果根據(jù)問題定義的結(jié)果 將未來程序的具體執(zhí)行流程或步驟詳細設計出來 這就是算法設計上一節(jié)講述了兩種描述算法的方式或者說工具 流程圖 偽代碼可以采用任何一種工具進行設計問題定義回答了 做什么 而算法設計回答了 如何做 要注意算法是不能被計算機理解 執(zhí)行的 必須經(jīng)過下一步編寫程序 6 5程序設計過程 算法設計 古希臘數(shù)學家歐幾里德給出了一個著名的算法如下 步驟1 任意輸入兩個數(shù)放入p和q中步驟2 如果p q 交換p和q步驟3 求出p q的余數(shù)放入r中步驟4 如果r 0 則執(zhí)行步驟8 否則執(zhí)行下一步步驟5 令p q q r步驟6 計算p和q的余數(shù)r步驟7 執(zhí)行步驟4步驟8 q就是所求的結(jié)果 輸出結(jié)果q 6 5程序設計過程 算法設計 步驟1 任意輸入兩個數(shù)放入p和q中步驟2 如果p q 交換p和q步驟3 求出p q的余數(shù)放入r中步驟4 如果r 0 則執(zhí)行步驟8 否則 執(zhí)行下一步步驟5 令p q q r步驟6 計算p和q的余數(shù)r步驟7 執(zhí)行步驟4步驟8 q就是所求的結(jié)果 輸出結(jié)果q 編寫程序就是將上一步驟的算法描述用某一程序設計語言編寫 或表示 出來不同的程序語言其功能和特性各不相同 選擇一個適合的程序設計語言 將算法轉(zhuǎn)換成程序代碼程序語言的基本語句 又稱指令 sum1 en1 com1這是Pascal的語句sum1 en1 com1這是C 的語句程序編寫風格 命名應簡單易記程序中應該有注釋語句書寫應采用縮進格式 6 5程序設計過程 編寫程序 m int raw input Pleaseinputthefirstpositiveinteger n int raw input Pleaseinputthesecondpositiveinteger ifm n m n n mwhilen 0 r m nm nn rprintm 6 5程序設計過程 編寫程序 includevoidmain intp q r cin p q if p q r p p q q r r p q while r 0 p q q r r p q cout 最大公因數(shù)是 q endl 6 5程序設計過程 編寫程序 調(diào)試運行又稱測試程序就是將編寫的程序在計算機上運行 以便檢驗程序正確與否 任何程序員所編寫的程序都有可能出現(xiàn)兩類錯誤 語法錯誤和邏輯錯誤語法錯誤 一般指程序中不符合語言的語法 如缺少標點符號 名稱不符等等邏輯錯誤 一般指運行程序所得到的結(jié)果與預期的結(jié)果不同 6 5程序設計過程 測試程序 整理文檔就是將前面四步所產(chǎn)生的所有文檔資料進行整理特別是將程序的高級語言編寫的代碼 即源程序 文件和可執(zhí)行的程序代碼 即目標程序 整理并編寫如何運行該程序的使用說明書 即用戶手冊 所有這些文檔資料一并提交給用戶 常見文檔資料清單如下 源程序可執(zhí)行程序用戶手冊數(shù)據(jù)庫文件各種規(guī)范說明 6 5程序設計過程 整理文檔 講授提綱 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 結(jié)構(gòu)化設計方法逐步求精 分解問題 形成若干模塊 然后細化模塊任何模塊都可以由三種基本流程控制結(jié)構(gòu)組合實現(xiàn)每個模塊只有一個入口 一個出口這三種基本結(jié)構(gòu)分別是 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 結(jié)構(gòu)化設計方法概述 所謂順序結(jié)構(gòu)是指位置處在前面的操作或模塊執(zhí)行完畢才能執(zhí)行緊跟其后面的操作或模塊 順序結(jié)構(gòu)執(zhí)行流程圖示如下 操作1 操作2 操作1 操作2 模塊 模塊 結(jié)構(gòu)化設計方法概述 根據(jù)三角形三邊長計算面積 開始 s a b c 2 Area 開方 s s a s b s c 輸出Area 結(jié)束 輸入三邊長度a b c 順序結(jié)構(gòu)舉例 所謂選擇結(jié)構(gòu)是指根據(jù)設定的條件來選擇確定將要執(zhí)行的語句或模塊 這些語句或模塊位置都處在條件的后面 選擇結(jié)構(gòu)又分三種形式 一路分支 二路分支 多路分支 結(jié)構(gòu)化設計方法概述 一路分支執(zhí)行流程為當條件成立執(zhí)行模塊1 當條件不成立執(zhí)行模塊1后面的模塊一路分支結(jié)構(gòu)圖示如下 結(jié)構(gòu)化設計方法概述 一路選擇結(jié)構(gòu)舉例 根據(jù)三角形三邊長計算面積 一路分支 開始 s a b c 2 Area 開方 s s a s b s c 輸出Area 結(jié)束 輸入三邊長度a b c 任意兩邊之和大于第三邊 二路分支執(zhí)行流程為當條件成立執(zhí)行模塊1 當條件不成立執(zhí)行模塊2 兩路分支結(jié)構(gòu)圖示如下 結(jié)構(gòu)化設計方法概述 根據(jù)三角形三邊長計算面積 二路分支 二路選擇結(jié)構(gòu)舉例 在程序設計中 往往需要重復多次執(zhí)行某一段程序 模塊 這就是循環(huán)結(jié)構(gòu) 根據(jù)設定的條件來確定一段程序 模塊 重復執(zhí)行的次數(shù) 循環(huán)結(jié)構(gòu)又分兩種形式 當型循環(huán) 直到型循環(huán) 結(jié)構(gòu)化設計方法概述 當型循環(huán)執(zhí)行流程為根據(jù)條件 若成立反復執(zhí)行模塊 當條件不成立轉(zhuǎn)到下一個模塊 當型循環(huán)的結(jié)構(gòu)圖示如下 條件 成立 不成立 模塊 新模塊 結(jié)構(gòu)化設計方法概述 條件 模塊 成立 不成立 直到型循環(huán)執(zhí)行流程為根據(jù)條件 若成立反復執(zhí)行模塊 當條件不成立轉(zhuǎn)到下一個模塊 直到型循環(huán)的結(jié)構(gòu)圖示如下 條件 模塊 成立 不成立 新模塊 結(jié)構(gòu)化設計方法概述 古希臘數(shù)學家歐幾里德給出了一個著名的算法如下 步驟1 任意輸入兩個數(shù)放入p和q中步驟2 如果p q 交換p和q步驟3 求出p q的余數(shù)放入r中步驟4 如果r 0 則執(zhí)行步驟8 否則執(zhí)行下一步步驟5 令p q q r步驟6 計算p和q的余數(shù)r步驟7 執(zhí)行步驟4步驟8 q就是所求的結(jié)果 輸出結(jié)果q 當型循環(huán)結(jié)構(gòu)舉例 兩個正整數(shù)求最大公因數(shù) 當型循環(huán) 當型循環(huán)結(jié)構(gòu)舉例 案例一 百元買百雞問題的流程圖設計 案例二 計算1 3 5 7 99 案例三 分段函數(shù)計算流程圖設計值 案例四 圓周率計算流程圖設計 四個算法設計案例 算法設計案例一 設公雞每只5元 母雞每只3元 小雞3只1元用100元買雞100只問公雞 母雞 小雞各多少只 這就是百雞問題 算法設計案例二 計算1 3 5 7 99 算法設計案例三 算法設計案例四 講授提綱 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 在日常生活 學習 工作中 會遇到有序化排列物品的問題 即排序問題 你在家里書房的書柜中擺放圖書圖書館 檔案館排列圖書 期刊 檔案歐林匹克開幕式入場順序各種大會主席臺就坐人員軍隊操練站隊同學們舉一些日常生活需要有序化排列的例子 排序相關(guān)概念 排序相關(guān)概念 上堂課討論了數(shù)據(jù)查找問題 其中折半查找方法較快的原因是什么查找和排序是計算機最常用的兩種數(shù)據(jù)處理方法本堂課就是討論如何排序數(shù)據(jù)的問題在計算機中 常常是有序化展示數(shù)據(jù) 計算機中文件按名稱順序排列 排序相關(guān)概念 收發(fā)郵件按日期順序排列 排序相關(guān)概念 排序相關(guān)概念 NBA東部地區(qū)比賽成績排列 排序相關(guān)概念 同學們說說使用計算機或上網(wǎng)時遇到的排序例子 排序相關(guān)概念 排序碼 指數(shù)據(jù)元素中一個或多個數(shù)據(jù)項 排序碼就是指排序的依據(jù)職務高低 身高 體重 ISBN號 ISSN號等組合排序碼 如選舉統(tǒng)計排名 得票數(shù)量 姓氏筆畫又如圖書館書庫排列 分類號 時間 排序相關(guān)概念 排序相關(guān)概念 排序定義 假設n個數(shù)據(jù)元素分別為 R1 R2 Rn 其相應的排序碼為 K1 K2 Kn 經(jīng)過排序后n個數(shù)據(jù)元素分別為 R1 R2 Rn 其相應的排序碼為 K1 K2 Kn 滿足 K1 K2 Kn 或K1 K2 Kn 如果待排序元素中 存在多個具有相同排序碼的元素 若經(jīng)過排序這些元素的相對次序保持不變 則稱這種排序算法是穩(wěn)定的如果待排序元素中 存在多個具有相同排序碼的元素 若經(jīng)過排序這些元素的相對次序發(fā)生改變 則稱這種排序算法是不穩(wěn)定的排序算法穩(wěn)定好還是不穩(wěn)定好 評價排序方法好壞 短時間 少空間 易理解 排序相關(guān)概念 對于數(shù)字化資源進行有序化處理 并儲存主要目的是便于數(shù)據(jù)高效率管理 例如查找 排序相關(guān)概念 選擇排序方法 排序相關(guān)概念 冒泡排序方法 快速排序方法 講授提綱 選擇排序方法 同學們看書中圖3 1 如何進行選擇排序游戲 排序效率分析 用天平比較砝碼28次選擇排序視頻 選擇排序方法 假設排序碼序列是 2 7 2 2 3 1 初始狀態(tài) 272231 第1趟 i 1 1 72232 第2趟 i 2 12 7232 第3趟 i 3 122 732 第4趟 i 4 1222 37 第5趟 i 5 12223 7 哪位同學用自然語言描述選擇排序過程 第1步 在N個元素的排序表中選擇最小元素第2步 將最小元素與 首 元素交換位置第3步 N N 1第4步 若N 1 則執(zhí)行第1步 否則結(jié)束排序注意任何算法有0個以上輸入 1個以上輸出 選擇排序方法 選擇排序方法 第1步 循環(huán)輸入N個元素第2步 在N個元素的排序表中選擇最小元素第3步 將最小元素與 首 元素交換位置第4步 N N 1第5步 若N 1 則執(zhí)行第1步 否則結(jié)束排序第6步 循環(huán)輸出N個元素 思考另一種對稱的算法 采用流程圖如何描述選擇排序算法 假設待排數(shù)據(jù)為 A 1 A 2 A N 選擇排序方法 開始 循環(huán)輸入N個數(shù)據(jù) 循環(huán)N 1輪 每輪挑選最小元素 與首元素交換位置 循環(huán)輸出N個數(shù)據(jù) 結(jié)束 選擇排序方法 逐步細化求精 循環(huán)輸入N個數(shù)據(jù)框細化 循環(huán)輸出N個數(shù)據(jù)框細化 選擇排序方法 細化每輪挑選最小交換位置框 選擇排序方法 修改流程每輪挑選最大元素 講授提綱 選擇排序方法 排序相關(guān)概念 冒泡排序方法 快速排序方法 冒泡排序方法 選擇排序方法的核心是挑選最小元素還有與選擇排序原理相似的方法嗎 冒泡排序PPT 冒泡排序方法 swap的作用說明 冒泡排序改進初始狀態(tài) 65977613274958 第1趟 j 1 6 657613274958 97第2趟 j 1 5 6513274958 7697第3趟 j 1 4 13274958 657697第4趟 j 1 3 132749 58657697第5趟 j 1 2 1327 4958657697第6趟 j 1 13 274958657697 講授提綱 算法設計基礎 程序設計概述 程序設計過程實例 結(jié)構(gòu)化設計方法概述 數(shù)據(jù)排序算法設計案例 數(shù)據(jù)查找算法設計案例 數(shù)據(jù)加密算法設計案例 若存在這樣的數(shù)據(jù)元素 則稱查找是成功的 若不存在這樣的數(shù)據(jù)元素 則稱查找是不成功的 關(guān)鍵字 指數(shù)據(jù)元素中可標識該數(shù)據(jù)元素的一組數(shù)據(jù)項 例如學生記錄中的學號 姓名 公民記錄中的身份證號碼等 查找 根據(jù)給定的關(guān)鍵字值 在一組數(shù)據(jù)元素中確定一個其關(guān)鍵字值等于給定值的數(shù)據(jù)元素的過程 一組待查數(shù)據(jù)元素的集合稱為查找表 查找表是具有一定存儲結(jié)構(gòu)的數(shù)據(jù)集合 比如學生花名冊表結(jié)構(gòu) 查找相關(guān)概念 信息和材料 能源一起成為人類社會三大基本資源網(wǎng)絡不僅是技術(shù) 更是一種生活 人們已經(jīng)逐步感受到 網(wǎng)絡和生活相融則利 相離則弊 如網(wǎng)上學習 圖書館 購物 醫(yī)療 協(xié)同工作 合作設計 虛擬制造等等知識更新的速度 100年 50年 30年 20年 10年 5年 3年 人類面臨的新的挑戰(zhàn)性難題 如何應對與日俱增的海量資源 空前的 認知負載 查找相關(guān)概念 數(shù)字化資源異質(zhì) 分布 海量 良莠不齊全球數(shù)字信息量每年以1018字節(jié)的速度劇增如何從海量數(shù)據(jù)中高效獲取 合適的知識 查找相關(guān)概念 順序查找方法 查找相關(guān)概念 折半查找方法 哈希查找方法 講授提綱 順序查找方法 同學們看書中圖2 1 如何進行順序查找游戲 查找效率分析 順序查找最快1次比較 最慢26 采用流程圖如何描述順序查找算法 假設查找表為 A 1 A 2 A N 順序查找方法 順序查找方法 講授提綱 順序查找方法 查找相關(guān)概念 折半查找方法 哈希查找方法 同學們看書中圖2 2 如何進行折半查找游戲 查找效率分析 折半查找最快1次比較 最慢5 折半查找方法 分析N個數(shù)據(jù)元素的折半查找判定規(guī)律樹假設待查的關(guān)鍵字序列是 11 16 37 51 55 76 88 90 101 108 2X N 2X 1 X則為最慢比較次數(shù) 折半查找方法 采用流程圖如何描述折半查找算法 假設查找表為 A low A 2 A hig 折半查找的過程是 先確定待查元素所在區(qū)域 然后逐步縮小區(qū)域 直到查找成功為止計算