1.1 算法與程序框圖算法的概念.ppt

算法的概念 先去括號(hào) 再乘除 后加減 1 什么是算法呢 2 兩個(gè)大人和兩名兒童一起渡河 渡口只有一條小船 一次只能渡過(guò)一個(gè)大人或兩名兒童 他們四人都會(huì)劃船 但都不會(huì)游泳 請(qǐng)你幫他們?cè)O(shè)計(jì)一個(gè)渡河方案 什么是算法呢 什么是算法呢 算法 algorithm 簡(jiǎn)單地說(shuō) 算法就是解決某一類問(wèn)題的程序或步驟 這些程序或步驟必須是明確和有效的 而且能在有限步之內(nèi)完成 什么是算法呢 算法的特征明確性 算法對(duì)每一個(gè)步驟都有確切的 非二義性的規(guī)定 即每一步對(duì)于利用算法解決問(wèn)題的人或計(jì)算機(jī)來(lái)說(shuō)都是可讀的 可執(zhí)行的 而不需要計(jì)算者臨時(shí)動(dòng)腦筋 有效性 算法的每一個(gè)步驟都能夠通過(guò)基本運(yùn)算有效地進(jìn)行 并得到確定的結(jié)果 對(duì)于相同的輸入 無(wú)論誰(shuí)執(zhí)行算法 都能夠得到相同的最終結(jié)果 有限性 算法應(yīng)由有限步組成 至少對(duì)某些輸入 算法應(yīng)在有限多步內(nèi)結(jié)束 并給出計(jì)算結(jié)果 輸入 輸出信息可以表示 第一步 第二步 第三步 消元 解一元一次方程 2 得 解 得 帶入求解 將代入 得 寫(xiě)一寫(xiě) 寫(xiě)出解第二個(gè)方程組的算法 第一步 第二步 第三步 解 得 將 帶入 得 變一變 第一步 第二步 第三步 解 得 將 帶入 得 解 得 這兩個(gè)解方程組算法的適用范圍有何不同 你對(duì)以下的 算法 如何理解 要把大象裝冰箱 分幾步 答 分三步 第一步 打開(kāi)冰箱門(mén) 第二步 把大象裝冰箱 第三步 關(guān)上冰箱門(mén) 問(wèn) 一位商人有9枚金幣 其中有一枚略輕的假幣 你能用天平 無(wú)砝碼 將假幣找出來(lái)嗎 寫(xiě)出解決這一問(wèn)題的算法 第一步 把9枚金幣平均分成三組 每組三枚 先將其中的兩組放在天平的兩邊 如果天平不平衡 那么假金幣就在輕的那一組 如果天平左右平衡 則假金幣就在未稱量的那一組里 取出含假幣的那一組 從中任取兩枚金幣放在天平兩邊進(jìn)行稱量 如果天平不平衡 則假金幣在輕的那一邊 若平衡 則未稱的那一枚就是假幣 第二步 第三步 有人對(duì)歌德巴赫猜想 任何大于4的偶數(shù)都能寫(xiě)成兩個(gè)奇質(zhì)數(shù)之和 設(shè)計(jì)了如下操作步驟 第一步 檢驗(yàn)6 3 3 第二步 檢驗(yàn)8 3 5 利用計(jì)算機(jī)無(wú)窮地進(jìn)行下去 請(qǐng)問(wèn) 利用這種程序能夠證明猜想的正確性嗎 第三步 檢驗(yàn)10 5 5 這是一種算法嗎 現(xiàn)在你對(duì)算法有了新的認(rèn)識(shí)了嗎 說(shuō)一說(shuō) 你能就生活中的某些事件描述一下算法嗎 做一做 藍(lán)墨水瓶里錯(cuò)裝了紅墨水 紅墨水瓶里錯(cuò)裝了藍(lán)墨水 請(qǐng)你設(shè)計(jì)一個(gè)算法將它們改正過(guò)來(lái) 做一做 第一步 第二步 第三步 判斷是否等于1 若是 則既不是質(zhì)數(shù) 也不是合數(shù) 若 1 則執(zhí)行第二步 判斷是否等于2 若 2 則是質(zhì)數(shù) 若 2 則執(zhí)行第三步 任意給定一個(gè)正整數(shù) 試設(shè)計(jì)一個(gè)算法對(duì)是否為質(zhì)數(shù)做出判斷 依次檢驗(yàn)的結(jié)果是否為整數(shù) 若有 則不是質(zhì)數(shù) 若沒(méi)有 則是質(zhì)數(shù) 用二分法設(shè)計(jì)一個(gè)求方程x2 2 0 x 0 的近似根的算法 精確度為0 005 令f x x2 2 因?yàn)閒 1 0 所以設(shè)x1 1 x2 2 令m x1 x2 2 判斷f m 是否為0 若是 則m為所求 若否 則繼續(xù)判斷f x1 f m 大于0還是小于0 若f x1 f m 0 則令x1 m 否則 令x2 m 判斷 x1 x2 0 005是否成立 若是 則x1 x2之間的任意取值均為滿足條件的近似根 若否 則返回第二步 第一步 第二步 第三步 第四步 做一做 現(xiàn)有有限個(gè)實(shí)數(shù) 怎樣從中找出最大值 你能設(shè)計(jì)一個(gè)算法嗎 思考 現(xiàn)有有限個(gè)實(shí)數(shù) 怎樣從中找出最大值 先假定這些實(shí)數(shù)中的第一個(gè)數(shù)為 最大值 將這些實(shí)數(shù)中的下一個(gè)數(shù)與 最大值 比較 如果它大于此 最大值 這時(shí)就假定 最大值 是這個(gè)實(shí)數(shù) 如果還有其他實(shí)數(shù) 重復(fù)第二步 一直到?jīng)]有可比的數(shù)為止 這時(shí)假定的 最大值 就是這有限個(gè)實(shí)數(shù)的最大值 第一步 第二步 第三步 第四步 思考 算法1 第二步 計(jì)算101 50 第三步 寫(xiě)出運(yùn)算結(jié)果 算法2 第一步 取n 100 第二步 計(jì)算 第三步 寫(xiě)出運(yùn)算結(jié)果 寫(xiě)出求1 2 3 100的一個(gè)算法 1 100 2 99 50 51 第一步 將原式變形為 你會(huì)了嗎 在數(shù)學(xué)中 現(xiàn)代意義上的算法通常是指可以用計(jì)算機(jī)來(lái)解決的某一類問(wèn)題的程序或步驟 這些程序或步驟必須是明確的和有效的 而且能夠在有限步之內(nèi)完成 算法是這樣的 1 任意給定一個(gè)大于1的整數(shù)n 怎樣判斷其是否為質(zhì)數(shù) 第一步 判斷n是否等于2 若n 2 則n是質(zhì)數(shù) 若n 2 則執(zhí)行第二步 第二步 依次從2至 n 1 檢驗(yàn)是不是n的因數(shù) 即整除n的數(shù) 若有這樣的數(shù) 則n不是質(zhì)數(shù) 若沒(méi)有這樣的數(shù) 則n是質(zhì)數(shù) 練一練 2 就你一天的生活或某一個(gè)片段說(shuō)出一個(gè)算法 算法的基本思想 探求解決問(wèn)題的一般性方法 并將解決問(wèn)題的步驟用具體化 程序化的語(yǔ)言加以表述 2 現(xiàn)有有限個(gè)正整數(shù) 怎樣從中找出最大值 課