程序設(shè)計(jì)與問題求解.ppt

程序設(shè)計(jì)與問題求解 第1章 程序設(shè)計(jì)概述 繆裕青 2011.9.20 1 程序設(shè)計(jì)與問題求解I 本章主要內(nèi)容 問題求解與程序設(shè)計(jì) 算法及其描述方法 程序設(shè)計(jì)語言的故事 C/C+語言程序組成 程序設(shè)計(jì)方法 程序風(fēng)格 Visual C+開發(fā)環(huán)境與上機(jī)指導(dǎo) 2 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 問題求解 w例：求1+2+100的和。 解:(1)分析問題特征。連續(xù)的100個整數(shù)求和。 (2)設(shè)計(jì)解決方案。 100個數(shù)連加：1+2+100 采用等差數(shù)列求和公式計(jì)算： (1+100)*100/2 擁有高斯的創(chuàng)造力,直接使用50*101 (3)優(yōu)化解決方案。三種方案比較選擇最好( 優(yōu))的，計(jì)算量最小、計(jì)算速度最快。 (4)描述解決方案?？捎脭?shù)學(xué)算式50*101來描 述。 (5)執(zhí)行解決方案。計(jì)算50*101結(jié)果。 分 析 設(shè) 計(jì) 優(yōu) 化 描 述 執(zhí) 行 3 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 問題求解過程 分 析 設(shè) 計(jì) 優(yōu) 化 描 述 執(zhí) 行 計(jì)算機(jī)做？計(jì)算機(jī)做？ 4 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 計(jì)算機(jī)有 智能嗎？ 5 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 計(jì)算機(jī)行業(yè)的夢想 w讓計(jì)算機(jī)（Computer）能像人 一樣地思考，與人自然交流， w人工智能AI （Artificial Intelligence） 圖靈（1912-1954）電子計(jì)算 機(jī)理論和模型的奠基人 w1946年誕生世界上第一臺電子計(jì) 算機(jī)ENIAC w1936年圖靈發(fā)表論文“論可計(jì)算 數(shù)及其在判定問題中的應(yīng)用” w1966年ACM設(shè)立“圖靈獎” 6 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 1997年，IBM公司研制的深藍(lán)超級計(jì)算機(jī)在 一場“人機(jī)大戰(zhàn)”中打敗了國際象棋大師卡斯 帕羅夫 w被譽(yù)為“人工智能的一大勝利” 深藍(lán)的主要研制者之一許峰雄博士： w勝利靠的只是不知疲倦地高速運(yùn)算，并不是 什么智能 7 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 計(jì)算機(jī)是用來延伸人能力的工具，具有高 速運(yùn)算的能力。 我們的目標(biāo)是控制計(jì)算機(jī)按照人的意愿去 工作，執(zhí)行解決方案。 完成這一目標(biāo)的手段就是“編程（ Programming）”。 8 程序設(shè)計(jì)與問題求解I 問題是豐富多彩 的 人具有思維 人 計(jì)算機(jī)只認(rèn)識0和1 計(jì)算機(jī)沒有思維 計(jì)算機(jī) 人和計(jì)算機(jī)通過程序進(jìn)行溝通 程序 需要解決問題的人沒有思維的計(jì)算機(jī) 問題求解與程序設(shè)計(jì) 9 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 問題求解過程 分 析 設(shè) 計(jì) 優(yōu) 化 描 述 執(zhí) 行 計(jì)算機(jī)可以做只能人做 算法設(shè)計(jì)編寫程序/算法實(shí)現(xiàn) 問題思路算法程序 程序設(shè)計(jì) 10 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 計(jì)算機(jī)組成 w硬件：整個過程的執(zhí)行者是硬件，但硬件 是受軟件控制的 w軟件：編程，就是編寫軟件，使硬件按照 人的意圖工作 電腦的“腦”體現(xiàn)在軟件 硬件受軟件控制的執(zhí)行者 程序和數(shù)據(jù) 執(zhí)行結(jié)果 11 程序設(shè)計(jì)與問題求解I 問題求解與程序設(shè)計(jì) 輸入/輸出 設(shè)備 存儲器運(yùn)算器 控制器 源程序 和輸入數(shù)據(jù) 輸出結(jié)果 取出數(shù)據(jù) 存入數(shù)據(jù) 操作命令存取命令 取出 程序指令 輸入輸出 命令 計(jì)算結(jié)果 CPU 計(jì)算機(jī)基本工作過程 “馮諾依曼機(jī)”結(jié)構(gòu) 大腦 記憶 裝置 眼睛、耳 朵、嘴、 手 12 程序設(shè)計(jì)與問題求解I 程序與編寫程序 程序：能夠?qū)崿F(xiàn)特定功能的指令序列，這些指令指 示計(jì)算機(jī)完成特定的操作。 編寫程序：編寫指令序列的過程。指令往往以某種 程序設(shè)計(jì)語言的語句形式給出。 問題求解與程序設(shè)計(jì) 13 程序設(shè)計(jì)與問題求解I 例：哥尼斯堡七橋問題 【問題】17世紀(jì)的東普魯士有一座哥尼斯堡城（現(xiàn)在叫加里 寧格勒，在波羅的海南岸），普雷格爾河流過城中，在河中 有兩座小島，全城共有七座橋?qū)?個城區(qū)連接起來，于是，產(chǎn) 生了一個有趣的問題：一個人是否能在一次步行中穿越全部 的七座橋后回到起點(diǎn)，且每座橋只經(jīng)過一次。 算法及其描述方法 14 程序設(shè)計(jì)與問題求解I 例：哥尼斯堡七橋問題 東區(qū) 北區(qū) 島區(qū) 南區(qū) C A D B 抽象 【想法抽象模型】可以用A、B、C、D表示4個城區(qū)，用 7 條線表示 7 座橋，將七橋問題抽象為一個圖模型。 算法及其描述方法 15 程序設(shè)計(jì)與問題求解I 例：哥尼斯堡七橋問題 【想法基本思路】是否存在歐拉回路的判定規(guī)則是： （1）如果通奇數(shù)橋的地方多于兩個，則不存在歐拉回路； （2）如果只有兩個地方通奇數(shù)橋，可以從這兩個地方之一出 發(fā)，找到歐拉回路； （3）如果沒有一個地方通奇數(shù)橋，則無論從哪里出發(fā)，都能 找到歐拉回路。 由上述判定規(guī)則得到求解七橋問題的基本思路：依次計(jì)算 圖中與每個節(jié)點(diǎn)相關(guān)聯(lián)的邊的個數(shù)（稱為節(jié)點(diǎn)的度），根據(jù)度 為奇數(shù)的節(jié)點(diǎn)個數(shù)判定是否存在歐拉回路。 算法及其描述方法 16 程序設(shè)計(jì)與問題求解I 算法及其描述方法 例：哥尼斯堡七橋問題 【算法】設(shè)函數(shù)EulerCircuit求解七橋問題，算法描述如下： 輸入：二維數(shù)組mat44 功能：計(jì)算七橋問題中奇數(shù)橋的結(jié)點(diǎn)個數(shù) 輸出：通奇數(shù)橋的結(jié)點(diǎn)個數(shù)count step1:count 初始化為0; step2:下標(biāo)i從0到n-1重復(fù)執(zhí)行下列操作; step2.1:計(jì)算第i行元素之和degree; step2.2:如果degree為奇數(shù)，則;count step3:返回count 17 程序設(shè)計(jì)與問題求解I 算法：對特定問題求解步驟的一種描述。 算法必須滿足下列五個重要特性： 1. 輸入; 2. 輸出; 3. 有窮性 ; 4. 確定性; 5. 可行性。 解決問題的方法 算 法（y = f (x)） 有窮性：在合理時間內(nèi)結(jié)束； 確定性：不存在二義性； 可行性：機(jī)器可執(zhí)行； 輸入 輸出 算法及其特性 算法及其描述方法 18 程序設(shè)計(jì)與問題求解I w描述算法：算法設(shè)計(jì)者在構(gòu)思和設(shè)計(jì) 了一個算法之后，必須清楚準(zhǔn)確地將所設(shè) 計(jì)的求解步驟記錄下來。 w使用算法：算法使用者知道如何調(diào)用 算法。 算法描述 算法及其描述方法 nf=n! 求階乘算法 19 程序設(shè)計(jì)與問題求解I w自然 語言 算法描述的方法 算法及其描述方法 步驟1：輸入數(shù)據(jù)n; 步驟2：將1保存到f中； 步驟3：將1保存到i中； 步驟4：若i大于n，則f為最后結(jié)果，算法執(zhí)行步驟7； 否則執(zhí)行步驟5 步驟5：i加1，將i*f的值放在f中； 步驟6：重新執(zhí)行步驟4； 步驟7：輸出數(shù)據(jù)f. 不直觀，書寫繁瑣 20 程序設(shè)計(jì)與問題求解I N 開始 輸入n f=1;i=1 in i=i+1；f=i*f 輸出f 結(jié)束 Y 圖形 符號 名 稱 含 義 起止框 表示算法的開始或結(jié)束 處理框 表示處理或運(yùn)算等功能 輸入/ 輸出框 表示進(jìn)行輸入/輸出操作 判斷框 根據(jù)給定的條件是否滿足決定 執(zhí)行兩條路徑中的某一條路徑 控制流 表示算法執(zhí)行的路徑，箭頭代 表方向 算法及其描述方法 算法描述的方法 w程序流程圖直觀，流程線無約束 21 程序設(shè)計(jì)與問題求解I w程序流 程圖 算法及其描述方法 規(guī)定只能使用三種基本結(jié)構(gòu) A B 條件表達(dá)式 AB FT 條件表達(dá)式 A B T F 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu) 算法描述的方法 22 程序設(shè)計(jì)與問題求解I wN-S 圖 算法及其描述方法 只能使用一些基本結(jié)構(gòu)，不允許 使用帶箭頭的流程線 A B 條件表達(dá)式 A 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu) AB 條件表達(dá)式 TF 算法描述的方法 23 程序設(shè)計(jì)與問題求解I wPAD 圖 算法及其描述方法 只能使用一些基本結(jié)構(gòu)，不允許 使用帶箭頭的流程線 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu) A B A B 條件表達(dá)式 whileA 算法描述的方法 24 程序設(shè)計(jì)與問題求解I w程序設(shè)計(jì) 語言 算法及其描述方法 int i,n; cinn; int f=1; for (i=1; in結(jié)束 4.1 f=i*f; 4.2 i=i+1; 5.輸出f; 介于自然語言和程序設(shè)計(jì)語言之間 算法描述的方法 26 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言（Programming Language） 是人與計(jì)算機(jī)進(jìn)行交流的語言 計(jì)算機(jī)直接能讀懂的語言 w機(jī)器語言（Machine Code），也叫機(jī)器 代碼 w一種純粹的二進(jìn)制語言 程序設(shè)計(jì)語言的故事 27 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言的故事 計(jì)算機(jī)為什么用二進(jìn)制呢？ 為什么不用我們?nèi)粘Ｊ煜さ氖M(jìn)制呢？ w二進(jìn)制在電器元件中容易實(shí)現(xiàn) w計(jì)算機(jī)進(jìn)行二進(jìn)制運(yùn)算比進(jìn)行十進(jìn)制運(yùn)算 要簡單得多 45678 +56789 10101 +11011 28 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言的故事 程序設(shè)計(jì)語言的發(fā)展 w機(jī)器語言(Machine Code) w匯編語言(Assemble Language) w面向過程的高級語言 w面向?qū)ο蟮母呒壵Z言 29 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言的故事 機(jī)器語言編寫的1+1程序 w執(zhí)行效率高。 w不同計(jì)算機(jī)使用不同 的機(jī)器語言，程序不能通 用。 w在人類的自然語言和 計(jì)算機(jī)編程語言之間存在 著巨大的鴻溝。 匯編語言編寫的1+1程序 w不能直接識別和執(zhí)行 。 w仍然依賴于機(jī)器。 w編程語言與人類自然 語言間的鴻溝略有縮小， 但仍與人類的思維相差甚 遠(yuǎn)。 10111000 00000001 00000000 00000101 00000001 00000000 MOV AX, 1 ADD AX, 1 匯編語言程序機(jī)器代碼 翻譯程序 30 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言的故事 高級語言（面向過程的） wBASIC語言編寫的1+1程序 wC語言編寫的1+1程序 PRINT 1+1 printf(“%dn“, 1+1); 高級語言源程序目標(biāo)程序 翻譯程序 高級語言源程序執(zhí)行程序 解釋程序 31 程序設(shè)計(jì)與問題求解I 程序設(shè)計(jì)語言的故事 高級語言（面向?qū)ο蟮模?wC+語言編寫的1+1程序 cout double a; void fun1() a=18; static int b=10; cout int a(int x, int y) if (x=y) return x; else return y; void main() int x,y; printf(“%dn“, a(5,8); scanf(“%d%d“, printf(“%dn“,a(x,y); 下面C程序完成什么功能？ 51 程序設(shè)計(jì)與問題求解I 程序風(fēng)格 良好的程序風(fēng)格 ： s命名規(guī)則 s注釋 s縮進(jìn) s適當(dāng)空行、空格 s適當(dāng)打印提示 目的是增加程序的可讀性 52 程序設(shè)計(jì)與問題求解I Visual C+開發(fā)環(huán)境與上機(jī)指導(dǎo) 程序?qū)崿F(xiàn)過程： 編輯 w將源程序輸入到計(jì)算機(jī)中，生成后綴為 .cpp的磁盤文件。 編譯 w將程序的源代碼轉(zhuǎn)換為機(jī)器語言代碼。 連接 w將多個源程序文件以及庫中的某些文件連 在一起，生成一個后綴為exe的可執(zhí)行文件。 運(yùn)行調(diào)試 53 程序設(shè)計(jì)與問題求解I 編輯源程序 進(jìn)入Visual C+6.0開發(fā)環(huán)境（1） 54 程序設(shè)計(jì)與問題求解I 編輯源程序 進(jìn)入Visual C+6.0開發(fā)環(huán)境（2） 55 程序設(shè)計(jì)與問題求解I 編輯源程序 創(chuàng)建一個Visual C+項(xiàng)目（1） 56 程序設(shè)計(jì)與問題求解I 編輯源程序 創(chuàng)建一個Visual C+項(xiàng)目（2） 57 程序設(shè)計(jì)與問題求解I 編輯源程序 創(chuàng)建一個Visual C+項(xiàng)目（3） 58 程序設(shè)計(jì)與問題求解I 編輯源程序 創(chuàng)建一個Visual C+項(xiàng)目（4） 59 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（1） 60 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（2） 61 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（3） 62 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（4） 63 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（5） 64 程序設(shè)計(jì)與問題求解I 編輯源程序 建立并編輯Visual C+源程序（6） 65 程序設(shè)計(jì)與問題求解I 編譯源程序 66 程序設(shè)計(jì)與問題求解I 連接程序 67 程序設(shè)計(jì)與問題求解I 運(yùn)行程序（1） 68 程序設(shè)計(jì)與問題