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