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