程序設(shè)計(jì)導(dǎo)論(講解如何畫算法流程圖)PPT課件

程序設(shè)計(jì)導(dǎo)論 一 算法概述二 程序流程圖與算法的基本邏輯結(jié)構(gòu) 一個(gè)程序主要包括以下兩方面的信息 對(duì)數(shù)據(jù)的描述 在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式 這就是數(shù)據(jù)結(jié)構(gòu) datastructure 2 對(duì)操作的描述 即要求計(jì)算機(jī)進(jìn)行操作的步驟也就是算法 algorithm 第一部分 算法概述 數(shù)據(jù) 是操作的對(duì)象操作的目的 是對(duì)數(shù)據(jù)進(jìn)行加工處理 以得到期望的結(jié)果著名計(jì)算機(jī)科學(xué)家沃思 NikiklausWirth 提出一個(gè)公式 算法 數(shù)據(jù)結(jié)構(gòu) 程序 算法是解決 做什么 和 怎么做 的問題程序中的操作語(yǔ)句代碼 是算法的體現(xiàn)不了解算法就談不上程序設(shè)計(jì) 1 什么是算法 廣義地說 為解決一個(gè)問題而采取的方法和步驟 就稱為 算法 對(duì)同一個(gè)問題 可以有不同的解題方法和步驟為了有效地進(jìn)行解題 不僅需要保證算法正確 還要考慮算法的質(zhì)量 選擇合適的算法 計(jì)算機(jī)算法可分為兩大類別 數(shù)值運(yùn)算算法非數(shù)值運(yùn)算算法數(shù)值運(yùn)算的目的是求數(shù)值解非數(shù)值運(yùn)算包括的面十分廣泛 最常見的是用于事務(wù)管理領(lǐng)域 2 簡(jiǎn)單的算法舉例 例 1求1 2 3 4 5可以用最原始的方法進(jìn)行 步驟1 先求1 2 得到結(jié)果2 步驟2 將步驟1得到的乘積2再乘以3 得到結(jié)果6 步驟3 將6再乘以4 得24 步驟4 將24再乘以5 得120 這就是最后的結(jié)果 例 1求1 2 3 4 5 1000 太繁瑣 改進(jìn)的算法 設(shè)變量p為被乘數(shù)變量i為乘數(shù)用循環(huán)算法求結(jié)果 S1 使p 1 或?qū)懗? pS2 使i 2 或?qū)懗? iS3 使p與i相乘 乘積仍放在變量p中 可表示為 p i pS4 使i的值加1 即i 1 iS5 如果i不大于5 返回重新執(zhí)行S3 否則 算法結(jié)束最后得到p的值就是5 的值 若是1000 求什么 例 判定2000 2500年中的每一年是否閏年 并將結(jié)果輸出 閏年的條件 1 能被4整除 但不能被100整除的年份都是閏年 如2008 2012 2048年 2 能被400整除的年份是閏年 如2000年不符合這兩個(gè)條件的年份不是閏年例如2009 2100年 設(shè)year為被檢測(cè)的年份 算法表示如下 S1 2000 yearS2 若year不能被4整除 則輸出year的值和 不是閏年 然后轉(zhuǎn)到S6S3 若year能被4整除 不能被100整除 則輸出year的值和 是閏年 然后轉(zhuǎn)到S6S4 若year能被400整除 則輸出year的值和 是閏年 然后轉(zhuǎn)到S6S5 其他情況輸出year的值和 不是閏年 S6 year 1 yearS7 當(dāng)year 2500時(shí) 轉(zhuǎn)S2 否則停止 year不能被4整除 非閏年 year被4整除 但不能被100整除 閏年 year被100整除 又能被400整除 閏年 其他 非閏年 逐漸縮小判斷的范圍 例 給出一個(gè)大于或等于3的正整數(shù) 判斷它是不是一個(gè)素?cái)?shù) 所謂素?cái)?shù) prime 是指除了1和該數(shù)本身之外 不能被其他任何整數(shù)整除的數(shù)例如 13是素?cái)?shù) 因?yàn)樗荒鼙? 3 4 12整除 判斷一個(gè)數(shù)n n 3 是否素?cái)?shù) 將n作為被除數(shù) 將2到 n 1 各個(gè)整數(shù)先后作為除數(shù) 如果都不能被整除 則n為素?cái)?shù)S1 輸入n的值S2 i 2 i作為除數(shù) S3 n被i除 得余數(shù)rS4 如果r 0 表示n能被i整除 則輸出n 不是素?cái)?shù) 算法結(jié)束 否則執(zhí)行S5S5 i 1 iS6 如果i n 1 返回S3 否則輸出n 是素?cái)?shù) 然后結(jié)束 可改為n 2 十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù) 整數(shù)部分 方法 除2取余 14 0 7 0 3 1 1 1 1 0 28 余數(shù) 你能用算法步驟將此算法描述出來(lái)嗎 S1 S2 3 算法的特性 一個(gè)有效算法應(yīng)該具有以下特點(diǎn) 1 有窮性 一個(gè)算法應(yīng)包含有限的操作步驟 而不能是無(wú)限的 2 確定性 算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的 而不應(yīng)當(dāng)是含糊的 模棱兩可的 一個(gè)有效算法應(yīng)該具有以下特點(diǎn) 3 有零個(gè)或多個(gè)輸入 所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息 4 有一個(gè)或多個(gè)輸出 算法的目的是為了求解 解 就是輸出 沒有輸出的算法是沒有意義的 5 有效性 算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行 并得到確定的結(jié)果 對(duì)于一般最終用戶來(lái)說 他們并不需要在處理每一個(gè)問題時(shí)都要自己設(shè)計(jì)算法和編寫程序可以使用別人已設(shè)計(jì)好的現(xiàn)成算法和程序只需根據(jù)已知算法的要求給予必要的輸入 就能得到輸出的結(jié)果 輸入3個(gè)數(shù) 黑箱子 3個(gè)數(shù)中最大數(shù) 求3個(gè)數(shù)的最大數(shù) 4 怎樣表示一個(gè)算法 常用的方法有 自然語(yǔ)言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖偽代碼 1 用自然語(yǔ)言表示算法 2 用流程圖表示算法 3 用N S流程圖表示算法 4 用偽代碼表示算法 5 用計(jì)算機(jī)語(yǔ)言表示算法 1 用自然語(yǔ)言表示算法 以上幾個(gè)方面介紹的算法是用自然語(yǔ)言表示的用自然語(yǔ)言表示通俗易懂 但文字冗長(zhǎng) 容易出現(xiàn)歧義性用自然語(yǔ)言描述包含分支和循環(huán)的算法 不很方便除了很簡(jiǎn)單的問題外 一般不用自然語(yǔ)言 2 用流程圖表示算法 例 將以下算法用流程圖表示 求1 2 3 4 5如果需要將最后結(jié)果輸出 1 t i 5 開始 2 i t i t i 1 i 結(jié)束 N Y 4 用偽代碼表示算法 偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法用偽代碼寫算法并無(wú)固定的 嚴(yán)格的語(yǔ)法規(guī)則 可以用英文 也可以中英文混用 例 求5 begin 算法開始 1 t2 iwhilei 5 t i ti 1 i printtend 算法結(jié)束 5 用計(jì)算機(jī)語(yǔ)言表示算法 要完成一項(xiàng)工作 包括設(shè)計(jì)算法和實(shí)現(xiàn)算法兩個(gè)部分 設(shè)計(jì)算法的目的是為了實(shí)現(xiàn)算法 不僅要考慮如何設(shè)計(jì)一個(gè)算法 也要考慮如何實(shí)現(xiàn)一個(gè)算法 例 求5 用C語(yǔ)言表示 includeintmain inti t t 1 i 2 while i 5 t t i i i 1 printf d n t return0 二 程序流程圖與算法的基本邏輯結(jié)構(gòu) 1 流程圖表示算法 例 判斷素?cái)?shù)的算法用流程圖表示 對(duì)一個(gè)大于或等于3的正整數(shù) 判斷它是不是一個(gè)素?cái)?shù) N Y 2 i n i r i 1 i Y N 通過以上例子可以看出流程圖是表示算法的較好的工具一個(gè)流程圖包括以下幾部分 1 表示相應(yīng)操作的框 2 帶箭頭的流程線 3 框內(nèi)外必要的文字說明流程線不要忘記畫箭頭 否則難以判定各框的執(zhí)行次序 2 三種基本結(jié)構(gòu)和改進(jìn)的流程圖的畫法 1 傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序 對(duì)流程線的使用沒有嚴(yán)格限制使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去 使人難以理解算法的邏輯 2 三種基本結(jié)構(gòu) 1 順序結(jié)構(gòu) A B 2 選擇結(jié)構(gòu) A B Y N A Y N 3 循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu) A Y N Y N 0 x x 1 x 輸出1 2 3 4 5 直到型循環(huán)結(jié)構(gòu) A Y N Y N 0 x x 1 x 輸出1 2 3 4 5 以上三種基本結(jié)構(gòu) 有以下共同特點(diǎn) 1 只有一個(gè)入口 2 只有一個(gè)出口一個(gè)判斷框有兩個(gè)出口一個(gè)選擇結(jié)構(gòu)只有一個(gè)出口 3 結(jié)構(gòu)