高中数学 1.3 算法案例课件2 新人教A版必修3.ppt

第一章算法初步1 3算法案例 例 求下面两个正整数的最大公约数 1 求25和35的最大公约数 2 求49和63的最大公约数 所以 25和35的最大公约数为5 所以 49和63的最大公约数为7 思考 除了用这种方法外还有没有其它方法 例 如何算出8251和6105的最大公约数 辗转相除法与更相减损术 一 辗转相除法 欧几里得算法 1 定义 所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时较小的数就是原来两个数的最大公约数 2 步骤 以求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 例 用辗转相除法求225和135的最大公约数 225 135 1 90 135 90 1 45 90 45 2 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 思考 从上面的两个例子中可以看出计算的规律是什么 s1 用大数除以小数 s2 除数变成被除数 余数变成除数 s3 重复s1 直到余数为0 辗转相除法是一个反复执行直到余数等于0才停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mmodn m n n r r 0 是 否 思考 辗转相除法中的关键步骤是哪种逻辑结构 程序框图 思考 你能把辗转相除法编成一个计算机程序吗 程序 input m n m ndor mmodnm nn rloopuntilr 0printmend 1 定义 所谓更相减损术 就是对于给定的两个数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 再用较大的数减去较小的数 反复执行此步骤直到差数和较小的数相等 此时相等的两数便为原来两个数的最大公约数 二 更相减损术 2 方法 例 用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所以 98和63的最大公约数等于7 inputm nifmnifd nthenm d elsem nn dendifd m nwendd 2k dprintdend 思考 你能根据更相减损术设计程序 求两个正整数的最大公约数吗 1 设计求多项式 当x 5时的值的算法 并写出程序 2 有没有更高效的算法 能否探求更好的算法 来解决任意多项式的求解问题 三 秦九韶算法 引导学生把多项式变形为 思考 从内到外 如果把每一个括号都看成一个常数 那么变形后的式子中有哪些 一次式 x的系数依次是什么 3 若将x的值代入变形后的式子中 那么求值的计算过程是怎样的 将变形前x的系数乘以x的值 加上变形前的第2个系数 得到一个新的系数 将此系数继续乘以x的值 再加上变形前的第3个系数 又得到一个新的系数 继续对新系数做上面的变换 直到与变形前的最后一个系数相加 得到一个新的系数为止 这个系数即为所求多项式的值 这种算法即是 秦九韶算法 4 用秦九韶算法求多项式的值 与多项式组成有直接关系吗 用秦九韶算法计算上述多项式的值 需要多少次乘法运算和多少次加法运算 数书九章 秦九韶算法 对该多项式按下面的方式进行改写 思考 当知道了x的值后该如何求多项式的值 这是怎样的一种改写方式 最后的结果是什么 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 这种将求一个n次多项式f x 的值转化成求n个一次多项式的值的方法 称为秦九韶算法 思考 在求多项式的值上 这是怎样的一个转化 程序框图 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 输入ai 秦九韶算法的特点 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只需做n次乘法和n次加法即可 程序 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 四 进位制 1 什么是进位制 进位制是人们为了计数和运算方便而约定的记数系统 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 可使用数字符号的个数称为基数 基数为n 即可称n进位制 简称n进制 比如 满二进一 就是二进制 满十进一 就是十进制 满十二进一 就是十二进制 满六十进一 就是六十进制 基数 满几进一 就是几进制 几进制的基数就是几 2 最常见的进位制是什么 除此之外还有哪些常见的进位制 请举例说明 最常见的进位制应该是我们数学中的十进制 比如一般的数值计算 但是并不是生活中的每一种数字都是十进制的 古人有半斤八两之说 就是十六进制与十进制的转换 比如时间和角度的单位用六十进位制 计算 一打 数值时是12进制的 电子计算机用的是二进制 式中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 十进制的构成 十进制由两个部分构成 例如 3721 其它进位制的数又是如何的呢 用10个数字来记数 称基数为10 表示有 1个1 2个十 7个百即7个10的平方 3个千即3个10的立方 其它进制数化成十进制数公式 二进制 二进制是用0 1两个数字来描述的 如11001 二进制的表示方法 区分的写法 11001 2 或者 11001 2 八进制呢 如7342 8 k进制呢 anan 1an 2 a1 k 二进制与十进制的转换 1 二进制数转化为十进制数 例1 将二进制数110011 2 化成十进制数 解 根据进位制的定义可知 所以 110011 2 51 例2 设计一个算法 将k进制数a 共有n位 转换为十进制数b 1 算法步骤 第一步 输入a k和n的值 第二步 将b的值初始化为0 i的值初始化为1 第三步 b b ai ki 1 i i 1 第四步 判断i n是否成立 若是 则执行第五步 否则 返回第三步 第五步 输出b的值 2 程序框图 3 程序 input a k n a k nb 0i 1t amod10dob b t k i 1 a a 10t amod10i i 1loopuntili nprintbend 上面的程序如采用get函数 可简化为 备注 get函数用于取出a的右数第i位数 方法 除2取余法 即用2连续去除89或所得的商 然后取余数 例 把89化为二进制数 解 根据 逢二进一 的原则 有 89 2 44 1 2 2 22 0 1 2 2 2 11 0 0 1 2 2 2 2 5 1 0 0 1 5 2 2 1 2 2 2 2 22 1 1 0 0 1 89 1 26 0 25 1 24 1 23 0 22 0 21 1 20 所以 89 1011001 2 2 2 2 23 2 1 0 0 1 2 2 24 22 2 0 0 1 2 25 23 22 0 0 1 26 24 23 0 0 20 89 2 44 1 44 2 22 0 22 2 11 0 11 2 5 1 2 2 2 2 2 2 1 1 0 0 1 所以89 2 2 2 2 2 2 1 1