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

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