必修三(算法案例).ppt

算法案例 辗转相除法更相减损术秦九韶算法进位制 辗转相除法 1 求两个正整数的最大公约数 1 求25和35的最大公约数 2 求49和63的最大公约数 2 求8251和6105的最大公约数 所以 25和35的最大公约数为5 辗转相除法 欧几里得算法 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 为什么呢 完整的过程 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 思考1 从上面的两个例子可以看出计算的规律是什么 S1 用大数除以小数 S2 除数变成被除数 余数变成除数 S3 重复S1 直到余数为0 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mMODn m n n r r 0 是 否 思考2 辗转相除法中的关键步骤是哪种逻辑结构 九章算术 更相减损术 算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给顶两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数就是所求的最大公约数 例3用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所以 98和63的最大公约数等于7 秦九韶算法 这种算法用了几次乘法 几次加法 这种算法用了几次乘法 几次加法 5次乘法 5次加法 进位制是人们为了计数和运算便而约定的记数系统 满十进一 就是十进制 满二进一 就是二进制 满k进一 就是k进制 因此k进制需数k个数字 进位制 一般地 若k是一个大于1的整数 那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 3721 3 103 7 102 2 101 1 100 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 7342 8 7 83 3 82 4 81 2 80 将k进制数转为十进制数 例 把二进制数110011 2 化为十进制数 解 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 51 练习 把下列数化为十进制数 1 1011010 2 2 10212 3 3 2376 3 将十进制数转为k进制数 除k取余法 例 把89化为二进制数 例 把89化为五进制数 除2取余法 除5取余法 2 十进制转换为二进制 例2把89化为二进制数 5 2 2 2 1 2 0 1 0 余数 11 22 48 89 2 2 2 2 0 1 1 0 1 注意 1 最后一步商为0 2 将上式各步所得的余数从下到上排列 得到 89 1011001 2 练习 将下面的十进制数化为二进制数 1 10 2 20 3 128 4 256 例 把89化为五进制数 3 十进制转换为其它进制 解