算法知识结构 基本概念 算法 基本结构 表示方法 应用 自然语言 程序框图 基本算法语句 顺序结构 条件结构 循环结构 辗转相除法和更相减损数 秦九韶算法 进位制 赋值语句 条件语句 循环语句 输入 输出语句 算法的定义 通常指可以用计算机来解决的某一类 问题的程序或步骤 这些程序或步骤必 须是明确和有效的 而且能够在有限步 之内完成 算法最重要的特征 1 有序性 2 确定性 3 有限性 算法的基本特点 1 有穷性 一个算法应包括有限的操作步骤 能在执 行有穷的操作步骤之后结束 2 确定性 算法的计算规则及相应的计算步骤必须是唯 一确定的 既不能含糊其词 也不能有二义 性 3 有序性 算法中的每一个步骤都是有顺序的 前一步 是后一步的前提 只有执行完前一步后 才 能执行后一步 有着很强逻辑性的步骤序列 用程序框 流程线及文字说明来表示算 法的图形称为程序框图 它使算法步骤显得 直观 清晰 简明 终端框 起止框 输入 输出框 处理框 执行框 判断框 流程线 连接点 二 程序框图 程序框图又称流程图 是一种用规定的图形 指向线及 文字说明来准确 直观地表示算法的图形 程序框名称功能 终端框 起 止框 表示一个算法的起始和结束 输入 输出 框 表示算法的输入和输出的信 息 处理框 执 行框 赋值 计算 判断框判断一个条件是否成立 用 是 否 或 Y N 标明 二 程序框图 l1 顺序结构 l 2 条件结构 l 3 循环结构 步骤n 步骤n 1 满足条件 步骤A步骤B 是 否 满足条件 步骤A 是 否 循环体 满足条件 否 是 循环体 满足条件 是 否 先做后判 否去循环 先判后做 是去循环 二 程序框图 l1 顺序结构 设计一算法 求和1 2 3 100 并画出程序框图 算法 第一步 取n 100 第二步 计算 第三步 输出结果 开始 结束 输入n 100 s n 1 n 2 输出s 二 程序框图 l2 条件结构 算法 第一步 输入x 第二步 如果x 0 则输出x 否则输出 x 设计一个算法 求数x的绝对值 并画出程序框图 Y N 结束 x 0 输入x 开始 输出x输出 x 算法分析 实数X的绝对值 二 程序框图 l3 循环结构 A P 是 否 否 是 A P A A P 否 是 C 是 否 A P B D 直到型循环结构对应的程序框图是 当型循环结构对应的程序框图是 直到型循环结构 当型循环结构 A D 设计一个计算1 2 3 100的值的算法 并画出程序框图 算法 第一步 令i 1 s 0 第二步 s s i 第三步 i i 1 第四步 直到i 100时 输出S 结束算法 否则返回第二步 程序框图如下 i 100 i 1 开始 输出s 结束 否 是 s 0 i i 1 s s i 否 是 循环体 条件 循环结构 直到型循环结构 设计一个计算1 2 3 100的值的算法 并画出程序框图 算法 第一步 令i 1 s 0 第二步 若i 100成立 则执行第三步 否则 输出s 结束算法 第三步 s s i 第四步 i i 1 返回第二步 i 0 THEN PRINT X ELSE PRINT X END IF 程序 INPUT X END 条件语句 i 1i 1 S 0S 0 WHILEWHILE i 100 i100i 100 PRINTPRINT S S ENDEND 开始开始 结束结束 输出输出S S 直到型循环语句直到型循环语句 直到型循环语句 否 是 否 是 循环体 条件 DODO 循循环环环环体体 LOOP UNTILLOOP UNTIL 条件条件 直到型循环结构直到型循环结构 一 辗转相除法 欧几里得算法 1 定义 所谓辗转相除法 就是对于给定的两个 数 用较大的数除以较小的数 若余数不为 零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则 这时较小的数就是原来两个数的最大公约数 1 算法步骤 第一步 输入两个正整数 m n m n 第二步 计算m除以n所得的余 数r 第三步 m n n r 第四步 若r 0 则m n的最大 公约数等于m 否则 转到第二步 第五步 输出最大公约数m 以求8251和6105的最大公约数的过程为例 步骤 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的最大公 约数 更相减损术 可半者半之 不可半者 副置分母 子之数 以少减多 更 相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断他们是否都是偶数 若 是 则用2约简 若不是则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的 数比较 并以大数减小数 继续这个操作 直到所得的减数 和差相等为止 则这个等数就是所求的最大公约数 1 九章算术 中的更相减损术 1 背景介绍 2 现代数学中的更相减损术 2 定义 所谓更相减损术 就是对于给定的两个 数 用较大的数减去较小的数 然后将差和 较小的数构成新的一对数 再用较大的数减 去较小的数 反复执行此步骤直到差数和较 小的数相等 此时相等的两数便为原来两个 数的最大公约数 例 用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 35 63 35 28 35 28 7 28 7 21 21 7 21 14 7 7 所以 98和63的最大公约数等于7 3 方法 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除 法以除法为主 更相减损术以减法为主 计算次数 上辗转相除法计算次数相对较少 特别当两个数字 大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果 是以相除余数为0则得到 而更相减损术则以减数与 差相等而得到 1 用更相减损术求两个正数84与72的最大公约数 练习 思路分析 先约简 再求21与18的最大公约数 然后乘以两次约简的质因数4 2 求324 243 135这三个数的最大公约数 思路分析 求三个数的最大公约数可以先求出两个 数的最大公约数 第三个数与前两个数的最大公约 数的最大公约数即为所求 数书九章 秦九韶算法 设是一个n 次的多项式 对该多项式按下面的方式进行改写 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 这种将求一个n次多项式f x 的值转化成求n个一 次多项式的值的方法 称为秦九韶算法 通过一次式的反复计算 逐步得出高次多 项式的值 对于一个n次多项式 只需做n次乘 法和n次加法即可 秦九韶算法的特点 在秦九韶算法中反复执行的步骤 可用循环结 构来实现 例 用秦九韶算法求多项式 f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法一 首先将原多项式改写成如下形式 f x 2x 5 x 4 x 3 x 6 x 7 v0 2 v1 v0 x 5 2 5 5 5 v2 v1x 4 5 5 4 21 v3 v2x 3 21 5 3 108 v4 v3x 6 108 5 6 534 v5 v4x 7 534 5 7 2677 所以 当x 5时 多 项式的值是2677 然后由内向外逐层计算一次多项式的值 即 2 5 4 3 6 7 x 5 10 5 25 21 105 108 540 534 2670 2677 所以 当x 5时 多项式的值是2677 原多项式 的系数 多项式 的值 例 用秦九韶算法求多项式 f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值 解法二 列表 2 一 进位制一 进位制 进位制是人们为了计数和运算方便而约定的记数系统 进位制是一种记数方式 用有限的数字在不同的位 置表示不同的数值 可使用数字符号的个数称为基 数 基数为n 即可称n进位制 简称n进制 满几进一 就是几进制 几进制的基数就是几 基数 二进制 七进制 八进制 十二进制 六十进制等 二进制只有0和1两个数字 七进制用0 6七个数字 十六进制有0 9十个数字及ABCDEF六个字母 式中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 为了区分不同的进位制 常在数的右下角标明基数 十进制一般不标注基数 例如十进制的133 59 写成133 59 10 七进制的13 写成13 7 二进制的10 写成10 2 一般地 若k是一个大于1的整数 那么以k 为基数的k进制可以表示为一串数字连写在一起 的形式 二进制与十进制的转换 1 二进制数转化为十进制数 例1 将二进制数110011 2 化成十进制数 解 根据进位制的定义可知 所以 110011 2 51 把其他进位制的数化为十进制数的公式是什么 方法 除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 0 0 1 十进制转换为二进制 注意 1 最后一步商为0 2 将上式各步所得的余数从下到上排列 得到 89 1011001 2 另解 除2取余法的另一直观写法 5 2 2 2 1 2 0 1 0 余数 11 22 44 89 2 2 2 2 0 1 1 0 1 练习 将下面的十进制数化为二进制数 1 10 2 20 例 把89化为五进制数 解 根据除k取余法 以5作为除数 相应的除法算式为 所以 89 324 5 89 5 175 3 5 0 4 2 3 余数 除k取余法 十进制数转化为k进制数的方法 用k连续去除该十进制数或所得的商 直 到商为零为止 然后把每次所得的余数倒着 排成一个数 就是相应的k进制数 考题剖析 点评 本小题考查程序框图中的循环结构 主 要是根据框图 找到规律 解 由程序知 s 2 1 2 2 2 50 2550 故选 C 例 2007海南 宁夏 如果执行下面的程序框图 那么输出的 s A 2450 B 2500 C 2550 D 2652 输出 结束 开始 否 是 s s 2 k k k k 1 k 50 考题剖析 点评 本题考查条件结构的程 序框图 求解时 对字母比较难理解 可以取一些特殊的数值 代进去 方 便理解 解 由程序框图可知第一个判断框 作用是比较x与b的大小 故第二个 判断框的作用应该是比较x与c的 大小 故选 A 例 2008海南 宁夏 右面的程序框图 如果输入三个 实数a b c 要求输出这三个数中最大的数 那么在空白 的判断框中 应该填入下面四个选项中的 A c x B x c C c b D b c 结束 输出x x c 否 是 x b b x 输入a b c 开始 x a 是 否 2010安徽理数 如图所示 程序框图 算法流程图 的输出值 解析 程序运行如下 输出12 例 如图给出了一个算法流程图 该算法流程 图的功能是 A 求a b c三数的最大数 B 求a b