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