1.1.1算法的概念公开课ppt课件.ppt

1 1 1算法的概念 1 把大象放进冰箱里需要几步 第一步 把冰箱门打开 第二步 把大象装进去 第三步 把冰箱门关上 2 请问你怎样安排 3 知识探究 一 算法的概念 思考1 在初中 对于解二元一次方程组你学过哪些方法 加减消元法和代入消元法 思考2 解二元一次方程组的具体步骤是什么 4 解 得 解 得 第一步 第二步 第三步 第四步 第五步 得到方程组的解为 5 6 7 思考4 根据上述分析 你能归纳出算法的概念吗 在数学中 按照一定规则解决某一类问题的明确和有限的步骤称为算法 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 说明 计算机解决任何问题都要依赖于 只有将解决问题的过程分解为若干个 即 并用计算机能够接受的 准确地描述出来 计算机才能够解决问题 算法 明确的步骤 算法 语言 8 算法的特点 1 有序性 算法从初始步骤开始 分为若干明确的步骤 每一个步骤只能有一个确定的后续步骤 只有执行完前一步才能执行后一步2 明确性 算法的每一步计算 都必须有确定的结果 不能模棱两可 即算法的每一步只有唯一的执行路径 对于相同的输入只能得到相同的输出结果3 有限性 一个算法当运行完有限个步骤后必须结束 不能是无限地运行4 可行性 算法中的每一步骤必须能用实现算法的工具精确表达 并能在有限步内完成 5 不唯一性 解决一个或一类问题 可以有不同的方法和步骤 解决这个或这类问题的算法不一定是唯一的6 普遍性 算法一般要适用于输入值集合中不同形式的输入值 而不是局限于某些特殊的值 即算法具有一般性 一个算法总是针对某类问题设计的 所以对于求解这类问题中的任意一个问题都应该是有效的 9 算法的设计 1 算法设计的目的设计算法的目的实际上是寻求 的算法 它可以通过计算机来完成 设计算法的关键是把过程分解成若干个 然后用计算机能够接受的 语言 准确地描述出来 从而达到计算机执行的目的 一类问题 是确的步骤 一类问题 简单 少 正确 执行 2 算法设计的要求 写出的算法必须能解决 要使算法尽量 步骤尽量 要保证算法 且计算机能够 10 3 算法的描述 展现形式 目前可使用文字语言表示 展现方式 算法常用下列方式来表示 第一步 第二步 第三步 11 12 练习 判断下列关于算法的说法是否确 1 求解某一类问题的算法是唯一的 2 算法必须在有限步操作之后停止 3 算法的每一步必须是明确的 不能有歧义或模糊 4 算法执行后一定产生确定的结果 12 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 知识探究 二 算法的步骤设计 思考1 设计一个算法 判断7是否为质数 第一步 用2除7 得到余数1 因为余数不为0 所以2不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 第二步 用3除7 得到余数1 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 因此 7是质数 思考2 得到余数0 因为余数为0 以5能整除35 2 13 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 知识探究 二 算法的步骤设计 思考2 设计一个算法 判断7是否为质数 第一步 用2除7 得到余数1 因为余数不为0 所以2不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 第二步 用3除7 得到余数2 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 因此 7是质数 因此 35不是质数 得到余数0 因为余数为0 以5能整除35 第八十七步 用88除89 得到余数1 因为余数不为0 所以88不能整除89 因此 89是质数 1 思考3 14 第一步 第四步 第三步 第二步 算法设计 15 16 例1 写出求1 2 3 4 5 6的一个算法 解析 算法1 第一步 计算1 2得到3 第二步 将第一步中的运算结果3与3相加得到6 第三步 将第二步中的运算结果6与4相加得到10 第四步 将第三步中的运算结果10与5相加得到15 第五步 将第四步中的运算结果15与6相加得到21 第六步 输出运算结果 算法3 第一步 将原式变形为 1 6 2 5 3 4 3 7 第二步 计算3 7 第三步 输出运算结果 17 算法设计的步骤设计一个具体的算法 通常按以下步骤 18 例2 1 一个算法的步骤如下 第一步 输入x的值 第二步 计算y x2 第三步 计算z 2y log2y 第四步 输出z的值 若输入x的值为 2 则输出z的值为 A 2B 4C 12D 14 2 下面是求1 3 5 7 9 11值的算法 用p表示被乘数 i表示乘数 则将算法补充完整 第一步 使p 1 第二步 使i 3 第三步 使p 第四步 使i 第五步 若i 11 则返回到第三步继续执 否则输出p 1 D 2 P ii 2 19 变式 1 如下算法 第一步 输入x的值 第二步 若x 0成立 则y x 否则执行下一步 第三步 计算y 2x2 4 第四步 输出y的值 若输入x 2 则输出y 2 给出算法 第一步 输入n 8 第二步 令i 1 S 0 第三步 判断i n是否成立 若不成立 输出S