算法公开课PPT课件.ppt

1 算法的基本思想 颍上一中 2 一 情景引入 引例1 填中考报名表 拿到准考证 参加考试 填志愿 得到录取通知书 到高中报名注册 引例2 小品 钟点工 片段 要把大象装冰箱 分几步 问 2020 3 18 3 2020 3 18 4 答 分三步 第一步 打开冰箱门 第二步 把大象装冰箱 第三步 关上冰箱门 2020 3 18 5 引例3 一个猎人带一条狗 一只鸡 一袋米过河 每次只能带一样东西过河 如果鸡狗被剩在一起 狗就会吃鸡 如果鸡米被剩在一起 鸡就会吃米 求猎人带这三样东西过河的顺序 2020 3 18 6 引例4 解方程组 第二步 解 得 第一步 2 得5y 3 第三步 将代入 得 2020 3 18 7 二 新课研探 1 定义 算法 algorithm 一词出现于12世纪 指的是用阿拉伯数字进行算术运算的过程 在数学中 算法 通常是指按照一定规则来解决某一类问题的明确和有限的步骤 现在算法通常可以编成计算机程序 让计算机执行并解决问题 2020 3 18 8 2 算法的特点 明确性 算法中的每一个步骤都是确切的 能有效的执行且得到确定的结果 不能模棱两可 有限性 算法应由有限步组成 必须在有限操作之后停止 并给出计算结果 有人对歌德巴赫猜想 任何大于4的偶数都能写成两个奇质数之和 设计了如下操作步骤 第一步 检验6 3 3第二步 检验8 3 5第三步 检验10 5 5 利用计算机无穷地进行下去 请问 利用这种程序能够证明猜想的正确性吗 这是一种算法吗 2020 3 18 9 2 算法的特点 明确性 算法中的每一个步骤都是确切的 能有效的执行且得到确定的结果 不能模棱两可 有序性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 不唯一性 求解某一个问题的解法不一定是唯一的 对于同一个问题可以有不同的解法 但算法有优劣之分 好的算法是我们追求的目标 普适性 写出的算法必须能解决一类问题 并且能重复使用 这是设计算法的一条基本原则 这样才能使算法更有价值 有限性 算法应由有限步组成 必须在有限操作之后停止 并给出计算结果 2020 3 18 10 例 对于一般的二元一次方程组试写出解该方程组的步骤 2020 3 18 11 写出解第二个方程组的算法 第一步 第二步 第三步 解 得 将 代入 得 变一变 第四步 得到方程组的解 2020 3 18 12 例1 在给定素数表的条件下 将60分解成素因数的乘积 4000以内的素数表见附录1 解 算法步骤如下 1 判断60是否为素数 否 2 确定60的最小素因数 2 60 2 30 3 判断30是否为素数 否 6 确定15的最小素因数 3 15 3 5 4 确定30的最小素因数 2 30 2 15 7 判断5是否为素数 5是素数 所以分解结束 5 判断15是否为素数 否 8 输出结果 60 2020 3 18 13 例2 设计一个算法 求42与105的最大公因数 解 算法步骤如下 第一步 将42进行素因数分解 42 2 3 7 第二步 将105进行素因数分解 105 3 5 7 第三步 确定它们的公共素因数 3 7 第四步 确定公共素因数的指数 公共素因数3 7的指数都是1 第五步 最大公因数为 3 7 21 2020 3 18 14 1 给出求1 2 3 4 5的一个算法 解 算法1按照逐一相加的程序进行 第一步 计算1 2 得到3 第二步 将第一步中的运算结果3与3相加 得到6 第三步 将第二步中的运算结果6与4相加 得到10 第四步 将第三步中的运算结果10与5相加 得到15 练习 2020 3 18 15 练习2 2 设计一个算法 求324 440 556