算法的基本思想-课件.ppt

1、 随着计算机科学和信息技术的飞速发展，计算机已经随着计算机科学和信息技术的飞速发展，计算机已经被应用到了我们生活的方方面面，那么计算机是怎样工作被应用到了我们生活的方方面面，那么计算机是怎样工作的呢？这就要用到算法的思想。在以前的学习中，虽然没的呢？这就要用到算法的思想。在以前的学习中，虽然没有出现算法这个名词，在数学学习中已经学习到了大量的有出现算法这个名词，在数学学习中已经学习到了大量的算法的思想，例如四则运算的过程，求解方程的步骤等等。算法的思想，例如四则运算的过程，求解方程的步骤等等。完成这些工作都需要一系列程序化的步骤，这就是算法的完成这些工作都需要一系列程序化的步骤，这就是算法的思

2、想。思想。本章中，我们将介绍算法的基本思想、基本结构和描本章中，我们将介绍算法的基本思想、基本结构和描述算法的基本语句。这对我们理解数学与计算机技术的关述算法的基本语句。这对我们理解数学与计算机技术的关系是有很大帮助的。系是有很大帮助的。算法的基本思想算法的基本思想【例例1】在电视台的某个娱乐节目中，要求参与者快速在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在确。在某次节目中，主

3、持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：与者的一段对话：.如果你是参与者，你接下来会怎么猜？800元！元！高了高了400元！元！600元！元！低了低了高了高了参与者参与者主持人：李咏主持人：李咏例例2：给定素数表，设计算法，将：给定素数表，设计算法，将936分解成分解成 素因数的乘积。素因数的乘积。判断判断936是否为素数：是否为素数：确定确定936的最小素因数：的最小素因数：确定确定468的最小素因数：的最小素因数：判断判断468是否为素数：是否为素数：判断判断234是否为素数：是否为素数：确定确

4、定234的最小素因数：的最小素因数：否否2936468 2936234 22936117 23否否2否否2判断判断117是否为素数：是否为素数：否否确定确定117的最小素因数：的最小素因数：93639 23 33判断判断39是否为素数：是否为素数：否否确定确定39的最小素因数：的最小素因数：393613 23 32判断判断13是否为素数：是否为素数：是是 结束结束分解结果为：分解结果为：93613 23 329 3 64 6 82 3 41 1 73 922231 33练习：将下列两个数分解练习：将下列两个数分解素因数素因数 （1）840 （2）1764例例3：设计一个算法，求：设计一个算法，

5、求 840 与与 1764 的最大的最大 公因数。公因数。解：算法步骤如下：解：算法步骤如下：1.先将先将840进行素因数分解：进行素因数分解：840=23357；3.确定它们公共素因数：确定它们公共素因数：2,3,7；4.确定公共素因数的指数：公共素因数确定公共素因数的指数：公共素因数2，3,7的指的指数分别为数分别为2,1,1；2.先将先将1764进行素因数分解进行素因数分解:1764=223272；5.最大公因数为：最大公因数为：223171=84写算法的要求写算法的要求 写出的算法，必须能解决一类问题（如求两个写出的算法，必须能解决一类问题（如求两个正整数的最大公因数），并且能重复使用

6、。正整数的最大公因数），并且能重复使用。算法过程要一步一步执行，每一步执行的操作算法过程要一步一步执行，每一步执行的操作必须明确，不能含混不清，而且在有限步骤内必须明确，不能含混不清，而且在有限步骤内能得出结果。能得出结果。算法要简洁，清晰可读，不能搞得繁杂。算法要简洁，清晰可读，不能搞得繁杂。算法不同于求解一个具体问题的方法，算法不同于求解一个具体问题的方法，是这种方法的高度概括。一个好的算法有如是这种方法的高度概括。一个好的算法有如下要求：下要求：算法是什么算法是什么 算法可以理解为由基本运算及规定算法可以理解为由基本运算及规定的运算顺序构成的一个完整的的运算顺序构成的一个完整的解题步骤解

7、题步骤，或看成是按要求设计好的有限的、确切的或看成是按要求设计好的有限的、确切的计算步骤计算步骤，并且这样的步骤能解决一类问，并且这样的步骤能解决一类问题。题。现代意义上的现代意义上的“算法算法”通常是指可通常是指可以用计算机来解决的某一类问题的以用计算机来解决的某一类问题的程序程序或步骤或步骤。“韩信点兵韩信点兵”问题思考以下问题的算法：思考以下问题的算法：一位商人有一位商人有9 9枚银元，其中有枚银元，其中有1 1枚略轻的是枚略轻的是假银元。你能用天平（不用砝码）将假银元找假银元。你能用天平（不用砝码）将假银元找出来吗？出来吗？解解:2 2先将两组分别放在天先将两组分别放在天平的两边。如果

8、天平不平平的两边。如果天平不平衡，那边假银元就放在轻衡，那边假银元就放在轻的那一组；如果天平左右的那一组；如果天平左右平衡，则假银元就在末称平衡，则假银元就在末称的第的第3 3组里。组里。3 3取出含假银元的那一组，从中任取两枚放在天平取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。元。1.1.把银元分成把银元分成3 3组，每组，每组组3 3枚。枚。说明：说明：1算法实际上就是解决某一类问题的步骤和方法，在解算法实际上就是

9、解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。与步骤，一步一步地去做，最终便能解决问题。2算法的基本思想就是我们分析问题时的想法。由于想法算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。同的算法，算法有优劣之分。3从熟悉的问题出发，体会算法的程序化思想，学会用从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法自然语言来描述算法l有限性：有限性

10、：一个算法的步骤必须是有限的，必须在有一个算法的步骤必须是有限的，必须在有 限操作之后停止，不能是无限的限操作之后停止，不能是无限的.l确定性：确定性：算法中的每一步应该是确定的并且能有效算法中的每一步应该是确定的并且能有效 地执行且得到确定的结果，而不应当是模地执行且得到确定的结果，而不应当是模 棱两可棱两可.l普遍性：普遍性：一个算法通常设计成能解决一类问题，不一个算法通常设计成能解决一类问题，不l不唯一性：不唯一性：求解某一个问题的解法不一定是唯一求解某一个问题的解法不一定是唯一 的，对于一个问题可以有不同的算法的，对于一个问题可以有不同的算法.是仅仅解决一个单独问题的。是仅仅解决一个单

11、独问题的。例四例四 设函数设函数f(x)f(x)的图象是一条连续不断的的图象是一条连续不断的曲线，写出用曲线，写出用“二分法二分法”求方程求方程 f(x)=0f(x)=0的的一个近似解的算法一个近似解的算法.第一步，取函数第一步，取函数f(x)f(x)，给定精确度，给定精确度d.d.第二步，确定区间第二步，确定区间 a，bb，满足，满足f(f(a)f(b)f(b)0.0.第五步，判断第五步，判断 a,b,b的长度是否小于的长度是否小于d d或或f(m)f(m)是否是否等于等于0.0.若是，则若是，则m m是方程的近似解；否则，返回是方程的近似解；否则，返回第三步第三步.第三步，取区间中点第三步，取区间中点 .ma+b2第四步，若第四步，若f(f(a)f(m)f(m)0,0,则含零点的区间则含零点的区间 为为 a,m,m,否则，含零点的区间为否则，含零点的区间为mm，b.b.将新得到的含零点的区间仍记为将新得到的含零点的区间仍记为 a,b;,b;