15-16高中数学必修31.3-算法案例-第1课时省名师优质课赛课获奖课件市赛课一等奖课件.pptVIP

成才之路·数学;算法初步;1.3算法案例;高效课堂;;鸡兔同笼问题是中国古代数学名著《孙子算法》中一道名题，题目是这么：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”书中给出解法是：鸡有两只脚，兔有四只脚，把脚数除以2，共有47对脚．因为鸡有1对脚，兔有2对脚，所以从47中减去25，得12即为兔子数．因为如要笼子里动物每只都只有1对脚，就会多出12对脚来，把这12对脚分别加到有2对脚动物身上，就有12只脚动物，即兔子数．整个解题过程能够简单地写作：;第7页;1．辗转相除法与更相减损术

(1)辗转相除法．

①算法步骤：

第一步，给定两个正整数m，n.

第二步，计算m除以n所得余数r.

第三步，m＝n，n＝r.

第四步，若r＝___，则m，n最大条约数等于m；不然返回第___步．;②程序框图如图所表示．;③程序：

INPUTm，n

DO

r＝mMODn

m＝n

n＝r

LOOPUNTIL_______

PRINT___

END;(2)更相减损术．

算法步骤：

第一步，任意给定两个正整数，判断它们是否都是______．若是，用___约简；若不是，执行第二步．

第二步，以较大数___去较小数，接着把所得差与较小数比较，并以___数减___数．继续这个操作，直到所得差与减数相等为止，则这个数(等数)或这个数与约简数乘积就是所求最大条约数．;2．秦九韶算法

(1)概念：求多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0值时，惯用秦九韶算法，这种算法运算次数较少，是多项式求值比较先进算法，其实质是转化为求n个______多项式值，共进行___次乘法运算和___次加法运算．其过程是：

改写多项式为：

f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0

＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0

＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝…

＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.

设v1＝____________，;

v2＝v1x＋an－2，

v3＝v2x＋an－3，

…，

vn＝___________.;(2)算法步骤：

第一步，输入多项式次数n、最高次项系数an和x值．

第二步，将v值初始化为an，将i值初始化为n－1.

第三步，输入i次项系数ai.

第四步，v＝vx＋ai，i＝________.

第五步，判断i是否大于或等于___.若是，则返回第三步；不然，输出多项式值___.;(3)程序框图如图所表示．;(4)程??：

INPUT“n＝”；n

INPUT“an＝”；a

INPUT“x＝”；x

v＝a

i＝n－1

WHILE___________

PRINT“i＝”；i

INPUT“ai＝”；a;

v＝_________

i＝i－1

WEND

PRINT___

END;1．用辗转相除法求36与134最大条约数，第一步是()

A．134－36＝98

B．134＝36×3＋26

C．先除以2，得到18与67

D．36＝26×1＋10

[答案]B

[解析]求36与134最大条约数，第一步是134＝36×3＋26，第二步是36＝26×1＋10，故选D.;2．(·河北省廊坊一中月考)用辗转相除法求294和84最大条约数时，需要做除法次数是()

A．1 B．2

C．3 D．4

[答案]B

[解析]本题考查辗转相除法过程.294＝84×3＋42,84＝42×2，故选B.;3．设计程序框图，用秦九韶算法求多项式值，所选取结构是()

A．次序结构 B．条件结构

C．循环结构 D．以上都有

[答案]D

4．用更相减损术求294和84最大条约数时，第一步是________．

[答案]用2约简

[解析]因为294和84都是偶数，先用2约简．;5．(·云南省景洪一中月考)用秦九韶算法计算多项式f(x)＝3x6＋2x5＋4x4＋5x3＋7x2＋8x＋1在x＝0.5时值，需做乘法和加法次数分别是________．

[答案]6次乘法，6次加法

[解析]将多项式改写为f(x)＝(((((3x＋2)x＋4)x＋5)x＋7)x＋8)x＋1，化为6个一次因式求解，故只做了6次乘法和6次加法．;; 用辗转相除法求80和36最大条约数，并用更相减损术检验所得结果．

[探究]1.辗转相除法与更相减损术主要区分是什么？

2．将80作为大数，36作为小数，执行辗转相除法和更相减损术步骤即可．;[解析]用辗转相除法：

80＝36×2＋8，

36＝8×4＋4，

8＝4×2＋0.

故80和36最大条约数是4.;用更相减损术检验：

80－36＝44，

44－36＝8，

36－8＝28，

28－8＝20，