《高中數(shù)學第11課時5.4算法案例學案新人教A版必修3》由會員分享,可在線閱讀,更多相關《高中數(shù)學第11課時5.4算法案例學案新人教A版必修3(4頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、
第11課時 5.4 算法案例
重點難點
重點:通過案例分析,體會算法思想,熟練算法設計,進一步理解算法的基本思想,發(fā)展有條理的思考和表達能力,提高邏輯思維能力。
難點:在分析案例的過程中設計規(guī)范合理的算法學習要求
1.理解剩余定理的內涵
2.能利用剩余定理解決“韓信點兵—孫子問題”
【課堂互動】
歷史背景:
韓信是秦末漢初的著名軍事家,據(jù)說有一次漢高祖劉邦在衛(wèi)士的簇擁下來到練兵場,劉邦問韓信有什么辦法,不要逐個報數(shù),就能知道場上士兵的人數(shù)。
韓信先令士兵排成3列縱隊,結果有2人多余;接著他立刻下令將隊形改為5列縱隊,這一改,又多出3人;隨后他又下令改為7列縱隊,這
2、一次又剩下2人無法成整行。韓信看此情形,立刻報告共有士兵2333人。
眾人都愣了,不知韓信用什么辦法清點出準確人數(shù)的。
這個故事是否屬實,已無從查考,但這個故事卻引出一個著名的數(shù)學問題,即聞名世界的“孫子問題”。
這種神機妙算,最早出現(xiàn)在我國《算經(jīng)十書》之一的《孫子算經(jīng)》中,原文是:“今有物不知其數(shù),三三數(shù)之剩二,五五數(shù)之剩三,七七數(shù)之剩二,問物幾何?答曰:二十三。”
所以人們將這種問題的通用解法稱為“孫子剩余定理”。
【解析】
“孫子問題”相當于求關于x,y,z的不定方程組
的正整數(shù)解。
根據(jù)題意,m應該滿足三個條件:
(1)m被3除后余2,即
(2)m被5除后余3,即
3、
(3)m被7除后余2,即
在自然數(shù)中可能存在滿足條件的數(shù),首先讓m=2開始檢驗條件,若三個條件中有任何一個不滿足,則檢驗下一個數(shù),即m遞增1,如此循環(huán)下去,一直到m滿足三個條件為止。
這種解決問題的方法也稱為“窮舉法”,這種方法在利用計算機解決問題時非常有效,因為計算機最擅長重復機械的操作。
【流程圖】
N
Y
m←m+1
結束
輸出m
開始
1
m←2
【偽代碼】
m←2
End While
Print m
4、
【思考】
上述算法只能求出最小的滿足條件的數(shù),如果要求出10個滿足條件的數(shù),程序要做何修改?
你能否用數(shù)學上最小公倍數(shù)的知識分析出解決該問題的方法嗎?
可以這樣考慮:5和7的公倍數(shù)中能被3除余2的最小的公倍數(shù)是35;3和7的公倍數(shù)中能被5除余3的最小的公倍數(shù)是63;3和5的公倍數(shù)中能被7除余2的最小的公倍數(shù)是30;因此滿足條件的其中的一個數(shù)就應是35+63+30,為128,若減去3、5、7的最小公倍數(shù)105得23,23就是滿足題目要求的最小的數(shù)。
你能畫出這種算法的流程圖嗎?
【解】算法流程圖如下:
輸出
且
且
開始
結束
5、
經(jīng)典范例
例 古今中外,許多人致力于圓周率的研究與計算。我國東漢的數(shù)學家劉徽利用“割圓術”計算圓的面積及圓周率?!案顖A術”被稱為千古絕技,它的原理是用圓內接正多邊形的面積去逼近圓的面積。具體計算如下:
在單位圓內作正六邊形,其面積記為A1,邊長為a1,在此基礎上作圓內接十二邊形,面積記為A2,邊長為a2,……,一直做下去,記該圓的內接正邊形面積為,邊長為。由于所考慮的是單位圓,計算出的的值即是圓周率的一個近似值,且越大,與圓周率越接近。你能否設計一個算法,計算圓周率的近似值?
思路點撥:畫圖可知,,,
【解】算法步驟如下:
6、
【追蹤訓練】
1. 是一正整數(shù),對兩個正整數(shù),若是的倍數(shù),則稱模同余,用符號表示.則中,的取值可能為 ( )
A.11 B.22 C.27 D.32
2.有一堆圍棋子,五個五個地數(shù),最后余下2個;七個七個地數(shù),最后余下3個;九個九個地數(shù),最后余下4個.請設計一種算法,求出這堆棋子至少有多少個.
【解】 算法如下:
3.(李白買酒)無事街上走,提壺去買酒,遇店加一倍,見花喝一斗,三遇店和花,喝光壺中酒.設計求酒壺中原有多少酒的一個算法并寫出偽代碼.
【解】 算法如下:
4.求方程(其中為自然數(shù))的所有小于100的的正整數(shù)解.
【解】 算法如下:
4
用心 愛心 專心