算法的概念第一课时.ppt

算法的概念 大厂高级实验中学王斌 一一得一 一上一 二上二 三下五去二 四去六进一 问题一 解方程 解方程 第一步 第二步 解 3 得 第三步 第四步 解 4 得 第五步 得到方程组的解为 算法 在数学中算法通常指按照一定规则解决某一类问题的明确和有限的步骤 现在 算法通常可以编成计算机程序 让计算机执行并解决问题 算法的基本特征 明确性 算法对每一个步骤都是确切的 能有效执行且得到确定的结果 不能模棱两可 有效性 算法从初始步骤开始 分为若干明确的步骤 每一步都只能有一个确定的继任者 只有执行完前一步才能进入到后一步 并且每一步都确定无误后 才能解决问题 有限性 算法都是经有限次步骤内完成的 不唯一性 求解某一个问题的解法不一定是唯一的 对于同一个问题可以有不同的解法 1 下面的四种叙述不能称为算法的是 A 广播的广播操图解 B 歌曲的歌谱 C 做饭用米 D 做米饭需要刷锅 淘米 添水 加热这些步骤 练习题 C 2 有人对歌德巴赫猜想 任何大于4的偶数都能写成两个奇质数之和 设计了如下操作步骤 第一步 检验6 3 3 第三步 检验10 5 5 第二步 检验8 3 5 利用计算机无穷的进行下去 请问 利用这种程序能够证明猜想的正确性吗 这是一个算法吗 例1 设计一个算法判断7是否为质数 第一步 用2除7 得到余数1 因为余数不为0 所以2不能整除7 第二步 用3除7 得到余数1 因为余数不为0 所以3不能整除7 第三步 用4除7 得到余数3 因为余数不为0 所以4不能整除7 第四步 用5除7 得到余数2 因为余数不为0 所以5不能整除7 第五步 用6除7 得到余数1 因为余数不为0 所以6不能整除7 因此 7是质数 例1 设计一个算法判断35是否为质数 思考 整数89是否为质数 如果让计算机判断89是否为质数 按照上述算法需要设计多少个步骤 第一步 用2除89 得到余数1 所以2不能整除89 第二步 用3除89 得到余数2 所以3不能整除89 第三步 用4除89 得到余数1 所以4不能整除89 第八十七步 用88除89 得到余数1 所以88不能整除89 因此 89是质数 思考 用2 88逐一去除89求余数 需要87个步骤 这些步骤基本是重复操作 我们可以按下面的思路改进这个算法 减少算法的步骤 1 用i表示2 88中的任意一个整数 并从2开始取数 2 用i除89 得到余数r 若r 0 则89不是质数 若r 0 将i用i 1替代 再执行同样的操作 3 这个操作一直进行到i取88为止 你能按照这个思路 设计一个 判断89是否为质数 的算法步骤吗 用i除89 得到余数r 令i 2 若r 0 则89不是质数 结束算法 若r 0 将i用i 1替代 判断 i 88 是否成立 若是 则89是质数 结束算法 否则 返回第二步 第一步 第四步 第三步 第二步 算法设计 例2 设计一个算法判断n n 2 是否为质数 第一步 给定一个大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n不是质数 结束算法 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 第一步 给定一个大于2的整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则n是质数 否则 将i的值增加1 仍用i表示 第五步 判断 i n 1 是否成立 若是 则n是质数 结束算法 否则 返回第三步 例2 设计一个算法判断n n 2 是否为质数 3 写出求1 2 3 100的一个算法 可以运用公式1 2 3 n 直接计算 第一步 第二步 第三步输出运算结果 取n 100 计算 4 已知一个学生的语文成绩为89 数学成绩为96 外语成绩为99 求他的总分和平均成绩的一个算法为 第一步取A 89 B 96 C 99 第二步 第三步 第四步输出D E 计算总分D A B C 计算平均成绩E 5 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 第一步 输入任意一个正实数r 第二步 计算圆的面积 S r2 第三步 输出圆的面积S 6 任意给定一个大于1的正整数n 设计一个算法求出n的所有因数 第一步 给定一个大于1的正整数n 第二步 令i 2 第三步 用i除n 得到余数r 第四步 判断 r 0 是否成立 若是 则i是n的因数 否则i不是n的因