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

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