3算法案例第一课时辗转相除法与更相减损术秦九韶算､法自学导引1
理解辗转相除法与更相减损术的含义,了解执行过程
掌握秦九韶算法的计算过程,了解它在数学计算中的应用
进一步体会算法的基本思想
辗转相除法是用于求_____________________的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫________
所谓辗转相除法,就是对于给定的两个数,用________除以________,若余数不为零,则将___________构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时________就是原来两个数的最大公约数
两个正整数的最大公约数欧几里得算法较大的数较小的数除数与余数除数3
更相减损术是我国古代数学专著__________中介绍的一种求两数最大公约数的方法
其基本过程是:对于给定的两数,用___________,接着把所得的________与________比较,并以大数减小数,继续这个操作,直到所得的数________为止,则这个数就是所求的最大公约数
秦九韶算法是我国南宋数学家________在他的代表作___________中提出的一种用于计算一元n次多项式的值的方法
《九章算术》大数减小数差减数相等秦九韶《数书九章》名师讲解1
辗转相除法(1)辗转相除的原理
设m,n是两个整数(不妨设m>n),用m除以n,若商为q1,余数为r1(0≤r1r1>r2>…,所以到某一步必然有ri=ri+1·qi+2,即ri恰能被ri+1整除,这时ri+1是ri和ri+1的公约数,它也必然是ri-1和ri,ri-2和ri-1,…,r1与r2,n和r1,m和n的最大公约数
(2)辗转相除法的算法分析
由以上辗转相除法的原理可以发现,辗转相除法的基本步骤是用较大的数除以较小的数,考虑到算法中的赋值语句可以对同一变量多
