大學(xué)計(jì)算機(jī)基礎(chǔ).ppt

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