广东省汕头市高中数学 第一章 算法初步 1.3 秦九韶算法与进位制课件 新人教A版必修3.ppt

1 3秦九韶算法与进位制 1 求两个数的最大公约数的两种方法分别是 和 2 两个数21672 8127的最大公约数是 a 2709b 2606c 2703d 2706 一 秦九韶算法 问题 怎样求多项式f x x5 x4 x3 x2 x 1当x 5时的值呢 计算多项式 当x 5的值 算法1 因为 所以 5 5 5 5 5 5 3125 625 125 25 5 3906 算法2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 分析 两种算法中各用了几次乘法运算 和几次加法运算 算法1 算法2 共做了1 2 3 4 10次乘法运算 5次加法运算 共做了4次乘法运算 5次加法运算 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 这是怎样的一种改写方式 最后的结果是什么 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考 在求多项式的值上 这是怎样的一个转化 算法步骤 第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为1 第三步 输入i次项的系数an i 第四步 v vx an i i i 1 第五步 判断i是否小于或等于n 若是 则返回第三步 否则 输出多项式的值v 程序框图 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 特点 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做n次乘法和n次加法即可 例2已知一个五次多项式为 用秦九韶算法求这个多项式当x 5的值 解 将多项式变形 按由里到外的顺序 依此计算一次多项式当x 5时的值 所以 当x 5时 多项式的值等于17255 2 你从中看到了怎样的规律 怎么用程序框图来描述呢 程序框图 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 练习 已知多项式f x x5 5x4 10 x3 10 x2 5x 1用秦九韶算法求这个多项式当x 2时的值 二 进位制 进位制是人们为了计数和运算方便而约定的计数系统 比如 满二进一 就是二进制 满十进一 就是十进制 满十二进一 就是十二进制 满六十进一 就是六十进制 满几进一 就是几进制 几进制的基数就是几 基数 式中1处在百位 第一个3所在十位 第二个3所在个位 5和9分别处在十分位和百分位 十进制数是逢十进一的 我们最常用最熟悉的就是十进制数 它的数值部分是十个不同的数字符号0 1 2 3 4 5 6 7 8 9来表示的 十进制 例如133 59 它可用一个多项式来表示 133 59 1 102 3 101 3 100 5 10 1 9 10 2 实际上 十进制数只是计数法中的一种 但它不是唯一记数法 除了十进制数 生产生活中还会遇到非十进制的记数制 如时间 60秒为1分 60分为1小时 它是六十进制的 两根筷子一双 两只手套为一副 它们是二进制的 其它进制 二进制 七进制 八进制 十二进制 六十进制 二进制只有0和1两个数字 七进制用0 6七个数字 十六进制有0 9十个数字及abcdef六个字母 为了区分不同的进位制 常在数的右下角标明基数 十进制一般不标注基数 例如十进制的133 59 写成133 59 10 七进制的13 写成13 7 二进制的10 写成10 2 a 注意书写及读法 其它进制数化成十进制数公式 在电子计算机中 数是以二进制的形式表示的 二进制数每个数位只可能取两个不同的数码 和 二进制数与十进制数的转换 二进制 例4把二进制数110011 2 化为十进制数 51 1 二进制数化为十进制数 上述方法可以推广为把k进制数化为十进制数的算法 2 十进制数化为二进制数 例5把89化为二进制数 把上式各步所得的余数从下到上排列 得到89 1011001 2 除2取余法 可以推广为把十进制数化为k进制数的算法 称为除k取余法 解 例6把89化为五进制数 89 324 5 小结 1 秦九韶算法的方法和步骤2 秦九韶算法