算法的基本思想

1、中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 教學(xué)目標(biāo)：體會算法的思想，了解算法的含義教學(xué)目標(biāo)：體會算法的思想，了解算法的含義 體會一個(gè)問題多個(gè)算法的優(yōu)劣體會一個(gè)問題多個(gè)算法的優(yōu)劣 體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的 貢獻(xiàn)，增強(qiáng)民族自豪感貢獻(xiàn)，增強(qiáng)民族自豪感教學(xué)難點(diǎn)：算法的思想和含義教學(xué)難點(diǎn)：算法的思想和含義中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 例：猜一件例：猜一件1000元以內(nèi)的物品的價(jià)格問題元以內(nèi)的物品的價(jià)格問題算法的基本思想：通過一系列步驟解決一個(gè)問題算法的基本思想：通過一系列步驟解決一個(gè)問題 的方法就稱為一個(gè)算法的方法就

2、稱為一個(gè)算法.中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 算法的自然語言描述算法的自然語言描述例例1、在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將、在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936 分解成素?cái)?shù)的乘積分解成素?cái)?shù)的乘積.例例2、設(shè)計(jì)一個(gè)算法，求、設(shè)計(jì)一個(gè)算法，求840與與1764的最大公因數(shù)的最大公因數(shù).中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 練習(xí)：練習(xí)：1、設(shè)計(jì)一個(gè)算法，求、設(shè)計(jì)一個(gè)算法，求324，440，556的最大的最大 公因數(shù)公因數(shù).2、設(shè)計(jì)算法，求、設(shè)計(jì)算法，求1356何何2400的最小公倍數(shù)的最小公倍數(shù).中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHu

3、a.Net 概括：概括：“對一個(gè)數(shù)的素因數(shù)的分解對一個(gè)數(shù)的素因數(shù)的分解”算法是設(shè)計(jì)求算法是設(shè)計(jì)求 兩個(gè)或多個(gè)數(shù)的最大公因數(shù)、最小公倍數(shù)的兩個(gè)或多個(gè)數(shù)的最大公因數(shù)、最小公倍數(shù)的 算法的基礎(chǔ)，為解決其他問題提供了一個(gè)算法的基礎(chǔ)，為解決其他問題提供了一個(gè) “平臺平臺”，這也是算法設(shè)計(jì)中的一個(gè)最基本的，這也是算法設(shè)計(jì)中的一個(gè)最基本的 思想思想.中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 例例3、有黑和藍(lán)兩個(gè)墨水瓶，但卻錯(cuò)把黑墨水裝在、有黑和藍(lán)兩個(gè)墨水瓶，但卻錯(cuò)把黑墨水裝在 了藍(lán)墨水瓶子里，而藍(lán)墨水錯(cuò)裝在了黑墨水瓶了藍(lán)墨水瓶子里，而藍(lán)墨水錯(cuò)裝在了黑墨水瓶 子里，要求將其互換，試描述其算法

4、子里，要求將其互換，試描述其算法.例例4、a3，b4，設(shè)計(jì)算法把兩個(gè)數(shù)值互換，設(shè)計(jì)算法把兩個(gè)數(shù)值互換.中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝立下了漢馬功勞謀超群，為漢朝立下了漢馬功勞.據(jù)說他在點(diǎn)兵的據(jù)說他在點(diǎn)兵的時(shí)候，為了保住軍事機(jī)密，不讓敵人知道自己部隊(duì)時(shí)候，為了保住軍事機(jī)密，不讓敵人知道自己部隊(duì)的實(shí)力，采用下述點(diǎn)兵方法：先令士兵從的實(shí)力，采用下述點(diǎn)兵方法：先令士兵從13報(bào)數(shù)報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)，結(jié)果最后一個(gè)士

5、兵報(bào)2；再令士兵從；再令士兵從15報(bào)數(shù)，報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)結(jié)果最后一個(gè)士兵報(bào)3；又令士兵從；又令士兵從17報(bào)數(shù)，結(jié)報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)果最后一個(gè)士兵報(bào)4.這樣，韓信很快就算出了自己這樣，韓信很快就算出了自己部隊(duì)士兵的總?cè)藬?shù)。請?jiān)O(shè)計(jì)一個(gè)算法，求出士兵部隊(duì)士兵的總?cè)藬?shù)。請?jiān)O(shè)計(jì)一個(gè)算法，求出士兵至少有多少人至少有多少人.中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 韓信點(diǎn)兵問題韓信點(diǎn)兵問題最早記載類似問題的是最早記載類似問題的是孫子算經(jīng)孫子算經(jīng)：“今有物，今有物， 不知其數(shù)。三三數(shù)之剩二，五五數(shù)之剩三，七不知其數(shù)。三三數(shù)之剩二，五五數(shù)之剩三，七 七數(shù)之剩二。問物幾何？七數(shù)之剩

6、二。問物幾何？” 又名又名“鬼谷算鬼谷算”、“秦王暗點(diǎn)兵秦王暗點(diǎn)兵”、“隔墻算隔墻算”、 “大衍求一術(shù)大衍求一術(shù)”等等.解法：著名的解法：著名的“中國剩余定理中國剩余定理”（孫子定理）（孫子定理）特殊解法：列舉法特殊解法：列舉法中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為漢朝立下了漢馬功勞謀超群，為漢朝立下了漢馬功勞.據(jù)說他在點(diǎn)兵的據(jù)說他在點(diǎn)兵的時(shí)候，為了保住軍事機(jī)密，不讓敵人知道自己部隊(duì)時(shí)候，為了保住軍事機(jī)密，不讓敵人知道自己部隊(duì)的實(shí)力，采用下述點(diǎn)兵方法：先令士兵從的實(shí)力，采用下述點(diǎn)

7、兵方法：先令士兵從13報(bào)數(shù)報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)，結(jié)果最后一個(gè)士兵報(bào)2；再令士兵從；再令士兵從15報(bào)數(shù)，報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)結(jié)果最后一個(gè)士兵報(bào)3；又令士兵從；又令士兵從17報(bào)數(shù)，結(jié)報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)果最后一個(gè)士兵報(bào)4.這樣，韓信很快就算出了自己這樣，韓信很快就算出了自己部隊(duì)士兵的總?cè)藬?shù)。請?jiān)O(shè)計(jì)一個(gè)算法，求出士兵部隊(duì)士兵的總?cè)藬?shù)。請?jiān)O(shè)計(jì)一個(gè)算法，求出士兵至少有多少人至少有多少人.比較一下兩個(gè)算法，你得到什么啟示？比較一下兩個(gè)算法，你得到什么啟示？中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 一位商人有一位商人有9枚銀元，其中有一枚略輕的假銀元，枚銀元，其中有一枚略輕的假

8、銀元，你能用天平（沒有砝碼）將假銀元找出來嗎你能用天平（沒有砝碼）將假銀元找出來嗎 ？比較一下兩個(gè)算法，你得到什么啟示？比較一下兩個(gè)算法，你得到什么啟示？中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 概括：同一個(gè)問題可能存在著多種算法，其中一概括：同一個(gè)問題可能存在著多種算法，其中一 些可能比另一些好些可能比另一些好.在實(shí)際問題和算法理論在實(shí)際問題和算法理論 中，找出好的算法是一項(xiàng)重要的工作中，找出好的算法是一項(xiàng)重要的工作.作業(yè)：作業(yè)：P91 練習(xí)練習(xí)1、2中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net P94 A1：1、從、從3個(gè)數(shù)個(gè)數(shù)a、b、c鐘任意抽出一個(gè)數(shù)鐘任

9、意抽出一個(gè)數(shù)a 2、將、將a與與b比較，如比較，如ab 3、再將、再將b與與c比較，如比較，如bc 4、則得出結(jié)論：、則得出結(jié)論：abcP94 A5：），）、（，方方程程的的正正整整數(shù)數(shù)解解為為（時(shí)時(shí)，時(shí)時(shí)，要要求求正正整整數(shù)數(shù)解解解解：62146y2x 1y4x4321x 101,2,3y522x 25x-22y 11 05222 yyx中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 二分法求方程的近似解的算法二分法求方程的近似解的算法例例1、求方程、求方程 f(x)=x3+x2-10在在 0,1 上的近似解，上的近似解， 精確到精確到0.01.思考：思考：根據(jù)例根據(jù)例1寫出求一般方程寫出求一般方程 f(x)=0 在區(qū)間在區(qū)間 a,b上的上的近似解的二分法求近似解的算法近似解的二分法求近似解的算法.中學(xué)數(shù)理化新課標(biāo)系列資料 WWW.ShuLiHua.Net 3、總結(jié)算法的特點(diǎn)：、總結(jié)算法的特點(diǎn)： 2、敘述起來很繁瑣，步驟很多，計(jì)算量大、敘述起來很繁瑣，步驟很多，計(jì)算量大;但但 正是計(jì)算機(jī)的優(yōu)點(diǎn)，它能不厭其煩地準(zhǔn)確完正是計(jì)算機(jī)的優(yōu)點(diǎn)，它能不厭其煩地準(zhǔn)確完 成這些繁瑣的的工作成這些繁瑣的的工作.1、一個(gè)算法可以作為其他算法的一個(gè)基礎(chǔ)或提供、一個(gè)算法可以作為其他算法的一個(gè)基礎(chǔ)或提供 “平臺平臺”，這是算法的基本思想之一，這是算法的基本思想之一.2、同一個(gè)問題可