算法案例王丽.ppt

1 3算法案例 1 奎屯市三中王丽 基本算法语句 输入语句输出语句赋值语句条件语句循环语句 一 输入语句 INPUT 提示内容 变量 例 INPUT x x 二 输出语句 PRINT 提示内容 表达式 例 PRINT y y 变量 表达式 例 A 10A A 15PRINTA 三 赋值语句 四 条件语句 IF条件THEN语句1ELSE语句2ENDIF 满足条件 步骤1 步骤2 是 否 IF条件THEN语句ENDIF 满足条件 步骤 是 否 满足条件 循环体 是 否 2 当型 1 直到型 满足条件 循环体 是 否 五 循环语句 1 求49和63的最大公约数 49 2 短除法 7 7 63 9 所以 49和63的最大公约数为7 课前复习 2 求225和135的最大公约数 1 列举法49的约数 1 7 49 所以 49与63的最大公约数为7 63的约数 1 3 7 9 21 63 5 45 27 3 15 9 3 3 5 所以 225和135的最大公约数为 5 3 3 45 3 求8251和6105的最大公约数 辗转相除法与更相减损术 欧几里得的五大公设 公设一 任两点必可用直线连接公设二 直线可以任意延长公设三 可以任一点为圆心 任意长为半径画圆公设四 所有的直角皆相同公设五 过线外一点 恰有一直线与已知直线平行欧几里德几何学全部公理 点是没有部分的线是平面上只有长度 没有宽度的直线是可以相两边无限延伸的过两点有且只有一条直线平面内过一点可以任何半径画圆两直线平行 同位角相等等量 等量和相等等量 等量差相等能重合的图形全等整体大于部分 目录 第一卷几何基础第二卷几何与代数第三卷圆与角第四卷圆与正多边形第五卷比例第六卷相似第七卷数论 一 第八卷数论 二 第九卷数论 三 第十卷无理量第十一卷立体几何第十二卷立体的测量第十三卷建正多面体 2146 1813 1 333 148 37 4 0 333 148 2 37 1813 333 5 148 8251 6105 1 2146 6105 2146 2 1813 m r n q 辗转相除法中的关键步骤是什么逻辑结构 r mMODn m n n r r 0 是 否 反复执行直到余数等于0 知识探究 一 辗转相除法 求8251和6105的最大公约数 对于给定的两个数 用较大的数除以较小的数 若余数不为0 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽 则这时候较小的数就是原来那两个数的最大公约数 思考 一般地 用辗转相除法求两个正整数m n m n 的最大公约数 其算法步骤如何设计 板书 算法步骤 程序框图 程序 辗转相除法 例1 利用辗转相除法求两数153与119的最大公约数 练习 课本45页 第1题 思考 设两个正整数m n 若m n k 则m与n的最大公约数和n与k的最大公约数是否相等 反复利用这个原理 求98与63的最大公约数 98 63 35 14 7 7 21 7 14 28 7 21 35 28 7 63 35 28 知识探究 二 更相减损术 上述求两个正整数的最大公约数的方法称为更相减损术 对于给定的两个正整数 用较大的数减去较小的数然后将差和较小的数构成新的数对 再用较大的数减去较小的数 反复执行此步骤 直到差和较小的数相等 此时相等的两数就是原来两个数的最大公约数 更相减损术 练习 利用更相减损术求两数81与135的最大公约数 答案 27 思考 一般地 用更相减损术求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 思考4 该程序框图对应的程序如何表述 INPUTm n WHILEmn k m n IFn kTHEN m n n k ELSE m k ENDIF WEND PRINTm END k m n 是 否 更相减损术 在中国古代数学专著 九章算术 中记述为 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 作者 刘徽 三国时代魏国人 例2分别用辗转相除法和更相减损术求168与93的最大公约数 辗转相除法 168 93 1 7593 75 1 1875 18 4 3 18 3 6 更相减损术 168 93 75 93 75 18 75 18 57 57 18 39 39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 所以 168与93的最大公约数是3 比较辗转相除法与更相减损术的区别与联系 例2求325 130 270三个数的最大公约数 答案 5 1 辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽为止 这时的较小的数即为原来两个数的最大公约数 2 更相减损术 就是对于给定的两个正整数 用较大的