【文章內(nèi)容簡介】 東南大學 1）算法及其描述 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 算法 是一個有窮的指令集，這些指令為解決某一個特定任務(wù)規(guī)定了一個運算序列。 算法 具有如下特點： 有 0個或多個輸入 、有一個或多個輸出 、 具有確定性 、 具有有窮性 、 具有有效性 。 東南大學 算法與程序的區(qū)別： 算法與程序是不同的，程序可以不滿足有窮性特點。 算法與數(shù)據(jù)組織密切相關(guān)，它是在某種數(shù)據(jù)組織結(jié)構(gòu)上的一種解決問題的計算方法。 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 算法的特點： 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 針對同一個問題，會有不同的數(shù)據(jù)組織方式和不同的算法。衡量一個算法的好壞，主要是通過該算法執(zhí)行時所耗費的 時間 和 空間 來比較，這種比較是一種相對比較 ，一般只給出 量級關(guān)系 。 一般而言，算法的量級有 O（ 1） 、 O（ n） 、 O（ log2n） 、 O（ nlog2n） 、 O（ n2） 、 O（ n3） 等。 O（ m+n）與 O（ n）屬于同一量級，即線性級； O（ 100）和 O（ 1）屬于同一量級，即常量級（其中，對于空間耗費而言， m、 n表示算法執(zhí)行時耗費的空間大小，一般以字節(jié)為單位計數(shù)；對于時間耗費而言， m、 n表示算法中指令執(zhí)行的次數(shù)）。 東南大學 算法的抽象本質(zhì)在于算法與它的表示之間的區(qū)別。也就是說，算法本身是 抽象 的，它只是反映一種解決問題的方法。但這種方法必須通過某種形式展示出來，這就是具體的 算法表示和描述 。 算法的描述可以有多種形式，可以有 語言方式 、 圖形方式 和 表格方式 。每一種形式還可以有多種不同的形態(tài)。比如，語言方式就有自然語言、類計算機語言和計算機語言三種描述。圖形方式有流程圖、 NS圖、 PAD圖等多種方式。 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） NS圖 是一種 結(jié)構(gòu)化 的流程圖，通過一個矩形框表達一個對數(shù)據(jù)的基本處理，并定義三種基本的元素框（元素框內(nèi)可以包含基本處理矩形框），通過三種基本的元素框可以按需要進行任意邏輯組合，實現(xiàn)處理邏輯的控制策略，從而表達一個完整的處理問題的算法。 NS圖 很容易映射為所要求的某種具體的計算機語言。 合P成立？是 否A B當 P成立直到P 成立ABCCA處 理 順序結(jié)構(gòu)元素 分支結(jié)構(gòu)元素循環(huán)結(jié)構(gòu)元素A、B、C是處理名（可以是基本處理或基本處理集）；P是條件；C是循環(huán)體東南大學 NS圖 描述方法，體現(xiàn)了由大到小、由粗到細的逐步求精的分析和設(shè)計方法，這種方法比較符合人類的思維習慣。這種方法的核心在于用少量的幾個符號，可以描述無限的問題，呈現(xiàn)出 遞歸 的分析思想。 NS圖 應(yīng)用的技巧在于深刻領(lǐng)悟這種富有哲理的遞歸思想，從外到內(nèi)，逐層運用，在外層時不要看內(nèi)層，在內(nèi)層時不要看外層，始終保持當前只看到一個層次，這樣無論多復雜的問題，都可以看得相當簡單。 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 【 例 31】 給定一個正整數(shù) N，如果 N大于 0，輸出 “ 大于 0！ ” ；否則，輸出 “ 小于等于 0！ ” 。 輸入:整數(shù) NN0?輸出:大于0 !輸出:小于等于0 !T F輸入:正整數(shù) N輸出: 輸出:T FN0?大于0 ! 小于等于0 !程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 【 例 32】 輸入 10個整數(shù)，求它們的和。 輸入:整數(shù) NS 0，I 0S S + NI I + 1當I =1 0時輸出: SS 0，I 0I I + 1I I + 1當I =1 0時輸入:整數(shù) NS S + N輸出: SS S + N輸入:整數(shù) N采用簡單數(shù)據(jù)組織方式，用 S存放和， I記錄輸入數(shù)據(jù)的個數(shù)。初始時，S=0， I=0。每輸入一個數(shù)， I增加 1，并將該數(shù)加入到 S中。 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 素數(shù) 的特征是除 1和該數(shù)本身之外，不能被其他任何整數(shù)整除。算法的基本思想是：將 N分別被 …… 、N1除，如果都除不盡，則 N是一個素數(shù)。否則， N不是一個素數(shù)。根據(jù)此思路，算法的自然語言描述如下： ① 設(shè)除數(shù)為 I， I的值從 2變化到 N1； ② 用 I除 N，得到余數(shù) R； ③ 如果 R=0，則表示 N能夠被 I整除， N不是素數(shù)，算法結(jié)束；否則，表示 N不能被 I整除，可能為素數(shù)，繼續(xù)判斷； ④ 使 I的值增加 1； ⑤ 如果 I?N1，則返回（ 2）繼續(xù)；否則，表示 N已被 2到 N1除且都不能被整除。因此， N為素數(shù)，算法結(jié)束。 東南大學 判斷 N是否是素數(shù)的 NS圖 輸入:正整數(shù) NW 0，I 2R N/I的余 數(shù)R=0T FW 1I I+1直到I N 1或W =1W=0輸出:N 是素數(shù)!輸出:N 不是素數(shù)!T F輸入:正整數(shù) NW 0，I 2R N/I的余 數(shù)R=0T FW 1I I+1直到I N 1或W =1W=0輸出:N 是素數(shù)!輸出:N 不是素數(shù)!T FR N/I的余 數(shù)R=0T FW 1I I+1 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 常用數(shù)據(jù)處理算法 排 序 查 找 遞 歸 回 溯 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 15 18 9 5 23 10 13 7 16 15 18 9 5 23 10 13 7 16 當前需要冒泡的位置 從后向前冒泡 不需要交換 需要交換 需要交換 7 13 7 107 2397不需要交換 需要交換 5 18 5 15從后向前冒泡 原始數(shù)據(jù)排列 冒泡排序 程序構(gòu)造的基本方法 （數(shù)據(jù)處理） 東南大學 程序設(shè)計三要素 環(huán)境 是指程序作用的范圍，不同的環(huán)境對程序的構(gòu)造有不同的要求。 應(yīng)用 是指對具體問題的解決方法，應(yīng)用與環(huán)境是分不開的，環(huán)境是應(yīng)用賴以存在的基礎(chǔ)。 語言 是一種粘合劑，將應(yīng)用和環(huán)境連接起來。一方面，語言必須將應(yīng)用中的各種應(yīng)用模式、及其邏輯組合描述清楚，也就是將人的思維形式化，并記錄下來。另一方面，語言本身又考慮了環(huán)境的特征，將應(yīng)用問題過度到具體環(huán)境，實現(xiàn)最終的應(yīng)用問題求解。 東南大學 程序設(shè)計語言 （也稱程序描述語言、程序語言等）是計算機語言。它用于人與計算機的交流。 程序設(shè)計三要素（語言） 環(huán)境 語言 應(yīng)用 東南大學 計算機語言的基本體系結(jié)構(gòu) 基本符號常量、變量保留字、運算符等表達式語 句函 數(shù)類、包程序基本符號詞 匯短 語句 子段 落描 寫文 章語言的基本體系結(jié)構(gòu) 程序設(shè)計三要素（語言） 東南大學 計算機程序設(shè)計語言中， 數(shù)據(jù)類型 的概念特別重要，它類似于自然語言中的 詞性 。 在計算機程序設(shè)計語言中，不同的數(shù)據(jù)類型定義不同的詞性，用于指明該類詞匯所表達的 數(shù)據(jù)的性質(zhì) 、 數(shù)據(jù)的大小范圍 ，以及在該類數(shù)據(jù)上可以 施加的基本運算 。 程序設(shè)計三要素（語言） 東南大學 數(shù)據(jù)類型 一般有 基本類型 和 復合類型 兩大類，復合類型是由基本類型合成的。 數(shù)據(jù)類型基本類型復合類型算術(shù)類型字符類型枚舉類型整型實型單精度雙精度數(shù)組類型指針類型……用戶自定義類型 程序設(shè)計三要素（語言） 東南大學 計算機語言中的表達式一般有 算術(shù)表達式 （用于運算） 、 關(guān)系表達式 （用于表達基本條件）和 邏輯表達式 （用于表達復合條件） 三種。 計算機語言中的語句一般有 注釋語句 、 計算賦值語句 、 輸入 /輸出語句 和 流程控制語句 四種。 函數(shù) 是某種處理邏輯的抽象，也就是解決問題的方法的抽象，這種方法獨立于具體的處理對象。 程序設(shè)計三要素（語言） 東南大學 類 是將某個數(shù)據(jù)集、