第1章算法初步 1 1算法的含義 學(xué)習(xí)目標(biāo)1 了解算法的特征 2 初步建立算法的概念 3 會用自然語言表述簡單的算法 題型探究 問題導(dǎo)學(xué) 內(nèi)容索引 當(dāng)堂訓(xùn)練 問題導(dǎo)學(xué) 思考1 知識點(diǎn)一算法的概念 有一碗醬油 一碗醋和一個空碗 現(xiàn)要把兩碗盛的物品交換過來 試用自然語言表述你的操作辦法 先把醋倒入空碗 再把醬油倒入原來盛醋的碗 最后把倒入空碗中的醋倒入原來盛醬油的碗 就完成了交換 答案 思考2 某笑話有這樣一個問題 把大象裝進(jìn)冰箱總共分幾步 答案是分三步 第一步 把冰箱門打開 第二步 把大象裝進(jìn)去 第三步 把冰箱門關(guān)上 這是一個算法嗎 是 答案 梳理 算法概念 計(jì)算機(jī)程序 算術(shù)運(yùn)算 機(jī)械 統(tǒng)一 思考1 知識點(diǎn)二算法的特征 設(shè)想一下電腦程序需要計(jì)算無限多步 會怎么樣 若有無限步 必將陷入死循環(huán) 解決不了問題 故算法必須在有限步內(nèi)解決問題 答案 梳理 算法特征 有窮性 可行性 順序性 不唯一性 普遍性 思考2 求解某一個問題的算法是不是唯一的 解決一個問題的算法可以有多個 只是有優(yōu)劣之分 結(jié)構(gòu)簡單 步驟少 速度快的算法就是好算法 答案 思考3 任何問題都可以設(shè)計(jì)算法解決嗎 不可以 只有能按照一定規(guī)則解決的 明確的 有限的操作步驟的問題才可以設(shè)計(jì)算法 其他的問題一般是不可以的 答案 梳理 算法的設(shè)計(jì)要求 1 寫出的算法 必須能解決一類問題 并且能夠重復(fù)使用 2 要使算法盡量簡單 通俗易懂 3 要保證算法正確 且計(jì)算機(jī)能夠執(zhí)行 題型探究 例1一個大人和兩個小孩一起渡河 渡口只有一條小船 每次只能渡1個大人或兩個小孩 他們?nèi)硕紩澊?但都不會游泳 試問他們怎樣渡過河去 請寫出一個渡河方案 解答 類型一算法的特征 第一步兩個小孩同船過河去 第二步一個小孩劃船回來 第三步一個大人劃船過河去 第四步對岸的小孩劃船回來 第五步兩個小孩同船渡過河去 算法的特點(diǎn) 1 有窮性 一個算法應(yīng)包括有限的操作步驟 能在執(zhí)行有窮的操作步驟之后結(jié)束 2 確定性 算法的計(jì)算規(guī)則及相應(yīng)的計(jì)算步驟必須是確定的 3 可行性 算法中的每一個步驟都是可以在有限的時間內(nèi)完成的基本操作 并能得到確定的結(jié)果 反思與感悟 跟蹤訓(xùn)練1某人帶著一只狼和一只羊及一捆青菜過河 只有一條船 船僅可載重此人和狼 羊及青菜中的一種 沒有人在的時候 狼會吃羊 羊會吃青菜 請?jiān)O(shè)計(jì)安全過河的算法 解答 第一步人帶羊過河 第二步人自己返回 第三步人帶青菜過河 第四步人帶羊返回 第五步人帶狼過河 第六步人自己返回 第七步人帶羊過河 例2下面算法要解決的問題是 第一步輸入三個數(shù) 并分別用a b c表示 第二步比較a與b的大小 如果a b 則交換a與b的值 第三步比較a與c的大小 如果a c 則交換a與c的值 第四步比較b與c的大小 如果b c 則交換b與c的值 第五步輸出a b c 類型二算法的閱讀理解 答案 解析 輸入三個數(shù)a b c 并按從大到小的順 序輸出 第一步是給a b c賦值 第二步運(yùn)行后a b 第三步運(yùn)行后a c 第四步運(yùn)行后b c 所以a b c 第五步運(yùn)行后 顯示a b c的值 且從大到小排列 一個算法的作用往往并不顯然 這需要我們結(jié)合具體數(shù)值去執(zhí)行一下才知道 反思與感悟 跟蹤訓(xùn)練2下面給出了一個問題的算法 第一步輸入a 第二步若a 4 則執(zhí)行第三步 否則執(zhí)行第四步 第三步輸出2a 1 第四步輸出a2 2a 3 這個算法解決的問題是 答案 函數(shù)值f a 例3設(shè)計(jì)一個算法 判斷7是否為質(zhì)數(shù) 類型三算法的步驟設(shè)計(jì) 解答 第一步用2除7 得到余數(shù)1 所以2不能整除7 第二步用3除7 得到余數(shù)1 所以3不能整除7 第三步用4除7 得到余數(shù)3 所以4不能整除7 第四步用5除7 得到余數(shù)2 所以5不能整除7 第五步用6除7 得到余數(shù)1 所以6不能整除7 因此 7是質(zhì)數(shù) 設(shè)計(jì)一個具體問題的算法 通常按以下步驟 1 認(rèn)真分析問題 找出解決此題的一般數(shù)學(xué)方法 2 借助有關(guān)變量或參數(shù)對算法加以表述 3 將解決問題的過程劃分為若干步驟 4 用簡練的語言將這個步驟表示出來 反思與感悟 跟蹤訓(xùn)練3設(shè)計(jì)一個算法 判斷35是否為質(zhì)數(shù) 解答 第一步用2除35 得到余數(shù)1 所以2不能整除35 第二步用3除35 得到余數(shù)2 所以3不能整除35 第三步用4除35 得到余數(shù)3 所以4不能整除35 第四步用5除35 得到余數(shù)0 所以5能整除35 因此 35不是質(zhì)數(shù) 當(dāng)堂訓(xùn)練 1 下列不是算法的是 填序號 解方程2x 6 0的過程是移項(xiàng)和系數(shù)化為1 從濟(jì)南到溫哥華要先乘火車到北京 再轉(zhuǎn)乘飛機(jī) 解方程2x2 x 1 0 利用公式S r2計(jì)算半徑為3的圓的面積 不是算法 沒有給出解這個方程的步驟 答案 解析 2 3 4 1 2 下列對算法的理解正確的是 填序號 算法有一個共同特點(diǎn)就是對一類問題都有效 而不是個別問題 算法要求是一步步執(zhí)行 每一步都能得到唯一的結(jié)果 算法一般是機(jī)械的 有時要進(jìn)行大量重復(fù)計(jì)算 它的優(yōu)點(diǎn)是一種通法 任何問題都可以用算法來解決 由于算法要求必須在有限步驟內(nèi)求解某類問題 所以并不是任何問題都可以用算法解決 答案 解析 2 3 4 1 3 已知一個學(xué)生的語文成績?yōu)?9 數(shù)學(xué)成績?yōu)?6 外語成績?yōu)?9 求他的總分和平均成績的一個算法為 第一步取A 89 B 96 C 99 第二步 第三步 第四步輸出計(jì)算的結(jié)果 求三個數(shù)的平均數(shù)必須是先計(jì)算三個數(shù)的總和 再被3除 答案 解析 計(jì)算x A B C 2 3 4 1 2 3 4 1 4 已知算法 第一步 輸入n 第二步 判斷n是不是2 若n 2 則n滿足條件 若n 2 則執(zhí)行第三步 第三步 依次檢驗(yàn)從2到n 1的整數(shù)能不能整除n 若不能整除n 滿足條件 該算法的功能是 因?yàn)?是質(zhì)數(shù) 且大于2的任何數(shù) 只要它不能被2 3 n 1 整除 則n一定為質(zhì)數(shù) 故上述步驟是判斷n是否為質(zhì)數(shù)的算法 答案 解析 判斷所給的數(shù)是否為質(zhì)數(shù) 規(guī)律與方法 1 算法的特點(diǎn) 有限性 確定性 邏輯性 不唯一性 普遍性 2 算法設(shè)計(jì)的要求 1