高中数学 几种常见的算法案例分析 新人教A版必修3

用心 爱心 专心1 几种常见的算法案例分析几种常见的算法案例分析 算法不仅是数学及其应用的重要的组成部分 也是计算机科学的重要基础 其中算法 的重要思想在几种常见的算法例案中得以较好的体现 本文从几种常见算法案例出发 来 探究一下算法的内涵 一 辗转相除法 所谓辗转相除法 就是对于给定的两个数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时的 较小的数就是原来两个数的最大公约数 例例 1 写出求两个正数写出求两个正数 a b ab 的最大公约数的一个算法 的最大公约数的一个算法 算法设计 第一步 输入两个正整数 a b ab 第二步 把ab 的余数赋予r 第三步 如果0r 那么把b赋予a 把r赋予b 转到第二步 否则转 到第四步 第四步 输入最大公约数b 程序框图下图所示 用伪代码表示 input a b a b do r mod a b a b b r loop until r 0 print b end 二 更相减损术 所谓更相减术 就是对于给定的两个数 以其中较大的数减去较小的数 然后将差和 较小的数构成一对新数 再用较大的数减去较小的数 反复执行此步骤 直到差数和较小 的数相等 此时相等的两个数就是原两个数的最大公约数 在我国古代的 中 有这样的描述 约分术曰 可半者半之 不可半者会置分母分子之数 以少减多 更相损 减 求其等也 以等数约之 意思是说如果分母 分子都是偶数 那么先除以 2 如果不 全是偶数 便将分子与分母互减 以少减多 直到得出最大公约数为止 用最大公约数约 分子与分母 便可使分数最简 如果两个数都是偶数 也不除以 2 直接求最大公约数 这是一种多么奇妙的方法啊 我们古代人在许多方面都比西方先进 这是值得我们自豪的 以上题为例 算法可以这样来设计 以上题为例 算法可以这样来设计 第一步 输入两个正整数 a b ab 第二步 若a不等于b 则执行第三步 否则执行第五步 第三步 把ab 的差赋予r 第四步 如果br 则把b的值赋予a 否则把r的值赋予a 执行第二步 第五步 输出最大公约数b Y N 开始 输入 a b r mod a b a b b r r 0 输出b 结束 用心 爱心 专心2 程序框图如图 2 所示 用伪代码表示 input a b while ab r a b if b r then a b b r else a r end if wend print b end 三 秦九韶算法 例 2 写出23x 求多项式 32 73511xxx 的值的一个算法 算法 1 input x x p 32 73511xxx print p p end 算法 2 input x x p 73 5 11xxx print p p end 比较上述两种算法 我们可以看出算法 2 是较为方便的 这种算法就是 秦九韶算法 其 特点是 通过一次式的反复计算 逐步得出高次多项式的值 对于一个n次多项式 只要 做n次乘法和n次加法即可 例 3 试描述给定x的值 求多项式 2 012 n n p xaa xa xa x 值的算法 分析 我们先看给定一个定值x 求 5 次多项式 25 0125 p xaa xa xa x 函数值 的例子 首先可以把多项式一步一步的改写 432 543210 p xa xa xa xa xa xa 32 543210 a xa xa xaxa xa 2 543210 a xa xa xaxa xa 543210 a xaxa xaxa xa 上面分层计算 第一步 计算最内层 54 a xa 的值 把 54 a xa 的值赋给一个变量 1 v 用心 爱心 专心3 第二步 计算 543 a xaxa 的值 可以改写为 13 v xa 四 直接插入排序法