1．4　算法案例.ppt
page1
数学·必修3（苏教版）
page2
第1章　算法初步
1．4　算法案例
page3
情景切入             
           韩信是秦末汉初的著名军事家．据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的人数．
           韩信先令士兵排成3列纵队，结果有2人多余；接着立即下令将队形成为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这次又剩下2人无法成整行． 
             在场的人都哈哈大笑，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵2 333人．众人听了一愣，不知道韩信用什么方法这么快就能得出正确的结果的．同学们，你知道吗？

page4

1．理解辗转相除法与更相减损术求最大公约数的方法．
2．理解中国剩余定理在数学中的应用．
3．理解二分法求方程的近似解的算法．
page5
        栏目链接
page6
自   主学   习
1．孙子剩余定理即______________，在近代数学和电子计算机程序设计中有着广泛的应用．
2．公元前3世纪，欧几里得在《原本》中介绍的求两个正整数的最大公约数的方法，称为__________________．
3．63与231的最大公约数是__________．
中国剩余定理
欧几里得辗转相除法
21
        栏目链接
page7
        栏目链接
page8
一、中国剩余定理
要   点导   航
            中国剩余定理，也称为孙子剩余定理．该定理在近代数学和电子计算机程序设计中有着广泛的应用．
         (1)剩余问题．
         在整数除法里，一个数分别除以几个数，得到整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题．

        栏目链接
page9
要   点导   航
         (2)两个性质．
         性质1：几个数相加，如果只有一个加数不能被数a整除，而其他加数均能被数a整除，那么它们的和就不能被数a整除．
         如：10能被5整除，15能被5整除，但7不能