学年最新高中数学苏教版必修三教学案第1章 14 算法案例含答案.docx

学年最新高中数学苏教版必修三教学案第1章 14 算法案例含答案.docx

《学年最新高中数学苏教版必修三教学案第1章 14 算法案例含答案.docx》由会员分享，可在线阅读，更多相关《学年最新高中数学苏教版必修三教学案第1章 14 算法案例含答案.docx（3页珍藏版）》请在冰点文库上搜索。

学年最新高中数学苏教版必修三教学案第1章14算法案例含答案

问题1：

如何求12与20的最大公约数？

提示：

短除法．一般情况下数字不应过大．

问题2：

若求6750与3492的最大公约数，上述方法还奏效吗？

提示：

数值很大时短除法不方便用．

问题3：

对于问题1中12与20的最大公约数是4.若用20除以12余8，再用8去除12余4，再用4去除8余数为0，也可求得最大公约数为4.若对较大两数可否用此法求公约数？

提示：

可以．

1．孙子问题

（1）问题名称：

人们将“韩信点兵——孙子问题”这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理”．

（2）问题思想：

“孙子问题”相当于求关于x，y，z的不定方程组

2．欧几里得辗转相除法

（1）含义：

公元前3世纪，欧几里得在《原本》第七篇中介绍了求两个正整数a，b（a＞b）的最大公约数的方法，这种方法称为“欧几里得辗转相除法”．

（2）步骤：

计算出a÷b的余数r，若r＝0，则b即为a，b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为a，b的最大公约数．

3．两个常用函数

（1）Mod（a，b）表示a除以b所得的余数．

（2）Int（x）表示不超过x的最大整数．

1．由除法和减法的性质可知，对于任意两个正整数，辗转相除法或更相减损术总可以在有限步之后完成，故总能用这两种方法求出任意两个正整数的最大公约数．

2．辗转相除法的理论依据是：

由a＝nb＋r⇒r＝a－nb得a、b与b、r有相同的公约数．

[例1]　有3个连续的正整数，其中最小的能被15整除，中间的能被17整除，最大的能被19整除，画出求满足要求的一组三个连续正整数的流程图，并写出伪代码．

[思路点拨]　设这三个数分别为m，m＋1，m＋2，则m满足的条件是Mod（m,15）＝0且Mod（m＋1,17）＝0且Mod（m＋2,19）＝0.

[精解详析]　流程图：

伪代码：

m←2

WhileMod（m,15）≠0　or

Mod（m＋1,17）≠0　or

Mod（m＋2,19）≠0

m←m＋1

EndWhile

Printm，m＋1，m＋2

[一点通]