算法的基本思想

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

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

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

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

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

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

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

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

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