算法.ppt

算法初步 1 1 2程序框圖與算法的基本邏輯結(jié)構(gòu) 程序框圖基本概念 程序框圖又稱流程圖 是一種用規(guī)定的圖形 指向線及文字說明來準(zhǔn)確 直觀地表示算法的圖形 起止框 表示一個(gè)算法的開始或結(jié)束 輸入 輸出框 框內(nèi)標(biāo)明輸入 輸出的內(nèi)容 處理框 框內(nèi)標(biāo)明所進(jìn)行的處理 判斷框 框內(nèi)標(biāo)明條件 并在框外標(biāo)明條件成立或不成立時(shí)的兩種不同流向 流程線 表示從某一框到另一框的流向 設(shè)計(jì)算法 求一元二次方程ax2 bx c 0 a 0 b2 4ac 0 的根 畫出相應(yīng)的流程圖 輸入系數(shù)a b c 輸出X1 X2 結(jié)束 開始 計(jì)算 計(jì)算 順序結(jié)構(gòu) 算法有三種基本邏輯結(jié)構(gòu) 課本第7頁 順序結(jié)構(gòu) 條件結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 順序結(jié)構(gòu) 順序結(jié)構(gòu)是最簡(jiǎn)單的算法結(jié)構(gòu) 語句與語句之間 框與框之間是按從上到下的順序進(jìn)行的 它是由若干個(gè)依次執(zhí)行的處理步驟組成的 它是任何一個(gè)算法都離不開的一種基本算法結(jié)構(gòu) 順序結(jié)構(gòu)在程序框圖中的體現(xiàn)就是用流程線將程序框自上而下地連接起來 按順序執(zhí)行算法步驟 如在示意圖中 A框和B框是依次執(zhí)行的 只有在執(zhí)行完A框指定的操作后 才能接著執(zhí)行B框所指定的操作 i 2 輸入n 示意圖 課本圖1 1 3 例 寫出圖1 圖2中程序框圖的運(yùn)行結(jié)果 1 圖中輸出S 5 2 2 圖中輸出a 2 練習(xí)1 寫出下列算法的功能 右圖算法的功能是 求兩數(shù)的和 練習(xí)冊(cè) 題組一例1 2題組二例1 基礎(chǔ)檢驗(yàn)1 2 3 4 能力提升5 6 7 8 9 條件結(jié)構(gòu) 1 條件結(jié)構(gòu)是指在算法中通過對(duì)條件的判斷 根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu) 它的一般形式是 2 此結(jié)構(gòu)中包含一個(gè)判斷框 根據(jù)給定的條件P是否成立而選擇執(zhí)行A框或B框 無論P(yáng)條件是否成立 只能執(zhí)行A框或B框之一 不可能既執(zhí)行A框又執(zhí)行B框 也不可能A框 B框都不執(zhí)行 4 在許多算法中 需要對(duì)問題的條件作出邏輯判斷 判斷后依據(jù)條件是否成立而進(jìn)行不同的處理方式 這就需要用條件結(jié)構(gòu)來實(shí)現(xiàn)算法 如上面的問題 不能用順序結(jié)構(gòu)來表示算法 必須用條件結(jié)構(gòu)來表示 3 一個(gè)條件結(jié)構(gòu)可以有多個(gè)判斷框 設(shè)計(jì)算法 求一元二次方程ax2 bx c 0 a 0 的根 畫出相應(yīng)的流程圖 輸入系數(shù)a b c 輸出X1 X2 結(jié)束 開始 計(jì)算 計(jì)算 順序結(jié)構(gòu) b2 4ac 0 設(shè)計(jì)算法 求一元二次方程ax2 bx c 0 的根 畫出相應(yīng)的流程圖 a 0 輸出x1 x2 結(jié)束 開始 0 輸入系數(shù)a b c 否 是 輸出無實(shí)數(shù)解 條件結(jié)構(gòu) 計(jì)算 練習(xí)冊(cè) 題組一例1題組二例1 2基礎(chǔ)檢驗(yàn)1 2 3 4能力提升5 6 7 8 程序框圖又稱流程圖 是一種用規(guī)定的圖形 指向線及文字說明來準(zhǔn)確 直觀地表示算法的圖形 小結(jié) 1 順序結(jié)構(gòu)是任何一個(gè)算法都不可缺少的基本結(jié)構(gòu) 它由若干個(gè)依次執(zhí)行的處理步驟組成 2 條件結(jié)構(gòu)的特點(diǎn)是需要根據(jù)對(duì)條件的判斷結(jié)果來決定后面的步驟的結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu) 滿足條件 循環(huán)體 Y N 當(dāng)型循環(huán)結(jié)構(gòu)在每次執(zhí)行循環(huán)體前對(duì)控制循環(huán)條件進(jìn)行判斷 當(dāng)條件滿足時(shí)執(zhí)行循環(huán)體 不滿足則停止 2 循環(huán)結(jié)構(gòu)的算法流程圖 直到型循環(huán)結(jié)構(gòu) 條件 循環(huán)體 Y N 直到型循環(huán)執(zhí)行了一次循環(huán)體之后 對(duì)控制循環(huán)條件進(jìn)行判斷 當(dāng)條件不滿足時(shí)執(zhí)行循環(huán)體 滿足則停止 3 循環(huán)結(jié)構(gòu)的設(shè)計(jì)步驟 1 確定循環(huán)結(jié)構(gòu)的循環(huán)變量和初始條件 2 確定算法中需要反復(fù)執(zhí)行的部分 即循環(huán)體 3 確定循環(huán)的終止條件 4 循環(huán)結(jié)構(gòu)的三要素 循環(huán)變量 循環(huán)體 循環(huán)的終止條件 當(dāng)型循環(huán)與直到循環(huán)的區(qū)別 當(dāng)型循環(huán)可以不執(zhí)行循環(huán)體 直到循環(huán)至少執(zhí)行一次循環(huán)體 當(dāng)型循環(huán)先判斷后執(zhí)行 直到型循環(huán)先執(zhí)行后判斷 對(duì)同一算法來說 當(dāng)型循環(huán)和直到循環(huán)的條件互為反條件 1 循環(huán)結(jié)構(gòu)不是永無終止的 死循環(huán) 一定要在某個(gè)條件下終止循環(huán) 這就需要用條件結(jié)構(gòu)來判斷 因此 循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu) 2 循環(huán)結(jié)構(gòu)在程序框圖中也是利用判斷框來表示 判斷框內(nèi)寫上條件 兩個(gè)出口分別對(duì)應(yīng)著條件成立和條件不成立時(shí)執(zhí)行的不同指令 其中一個(gè)指向循環(huán)體 然后再?gòu)难h(huán)體回到判斷框的入口處 3 在循環(huán)結(jié)構(gòu)中都有一個(gè)計(jì)數(shù)變量或累加變量 計(jì)數(shù)變量用于記錄循環(huán)次數(shù) 累加變量用于輸出結(jié)果 計(jì)數(shù)變量和累加變量一般是同步執(zhí)行的 累加一次 計(jì)數(shù)一次 例1 設(shè)計(jì)一個(gè)計(jì)算1 2 3 100的值的算法 并畫出程序框圖 算法如下 第一步 i 1 第二步 sum 0 第三步 sum sum i 第四步 i i 1 第五步 如果i不大于100 返回重新執(zhí)行第三步 第四步 第五步 否則 算法結(jié)束 最后得到的sum值就是1 2 3 100的值 例1 設(shè)計(jì)一個(gè)計(jì)算1 2 3 100的值的算法 并畫出程序框圖 例1 設(shè)計(jì)一個(gè)計(jì)算1 2 3 100的程序框圖 開始 i 100 否 是 輸出s 結(jié)束 i 1 S 0 i i 1 S S i 解 由于加數(shù)較多 采用逐個(gè)相加的方法程序太長(zhǎng) 是不可取的 因此應(yīng)采取引入變量應(yīng)用循環(huán)的辦法 例1 設(shè)計(jì)一個(gè)計(jì)算1 2 3 100的程序框圖 開始 i 100 否 是 輸出S 結(jié)束 i 1 S 0 S S i i i 1 最后的結(jié)果 思考 將步驟A和步驟B交換位置 結(jié)果會(huì)怎樣 能達(dá)到預(yù)期結(jié)果嗎 為什么 答 達(dá)不到預(yù)期結(jié)果 當(dāng)i 100時(shí) 退出循環(huán) i的值未能加入到Sum中 左圖輸出的x 1 2 3 6 7 課堂練習(xí) 1 畫出求T 1 2 3 100問題的程序框圖 第一步 設(shè)i 1 T 1 第二步 如果i 100執(zhí)行第三步 否則執(zhí)行第五步 第三步 計(jì)算T i并將結(jié)果代替T 第四步 將i 1代替i 轉(zhuǎn)去執(zhí)行第二步 第五步 輸出T 課堂練習(xí) 開始 i 100 否 是 輸出T 結(jié)束 i 1 T 1 i i 1 T T i 開始 i 100 否 是 輸出S 結(jié)束 i 1 S 0 i i 1 S S i2 書本P 21A2 2 設(shè)計(jì)一個(gè)計(jì)算12 22 32 1002的一個(gè)程序框圖 練習(xí)冊(cè) 題組一例1題組二例2基礎(chǔ)檢驗(yàn)2 3能力提升4 6 7 8 1 本節(jié)課主要講述了算法的循環(huán)結(jié)構(gòu) 算法的基本邏輯結(jié)構(gòu)有三種 即順序結(jié)構(gòu) 條件結(jié)構(gòu)和循環(huán)結(jié)構(gòu) 其中順序結(jié)構(gòu)是最簡(jiǎn)單的結(jié)構(gòu) 也是最基本的結(jié)構(gòu) 循環(huán)結(jié)構(gòu)必然包含條件結(jié)構(gòu) 所以這三種基本邏輯結(jié)構(gòu)是相互支撐的 它們共同構(gòu)成了算法的基本結(jié)構(gòu) 無論怎樣復(fù)雜的邏輯結(jié)構(gòu) 都可以通過這三種結(jié)構(gòu)來表達(dá) 2 循環(huán)結(jié)構(gòu)要在某個(gè)條件下終止循環(huán) 這就需要條件結(jié)構(gòu)來判斷 因此 循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu) 但不允許 死循環(huán) 課堂小