算法的基本思想.ppt

《算法的基本思想.ppt》由会员分享，可在线阅读，更多相关《算法的基本思想.ppt（20页珍藏版）》请在三一办公上搜索。

1、随着计算机科学和信息技术的飞速发展，计算机已经被应用到了我们生活的方方面面，那么计算机是怎样工作的呢？这就要用到算法的思想。在以前的学习中，虽然没有出现算法这个名词，在数学学习中已经学习到了大量的算法的思想，例如四则运算的过程，求解方程的步骤等等。完成这些工作都需要一系列程序化的步骤，这就是算法的思想。本章中，我们将介绍算法的基本思想、基本结构和描述算法的基本语句。这对我们理解数学与计算机技术的关系是有很大帮助的。,算法的基本思想,【例1】在电视台的某个娱乐节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人

2、出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：,.,如果你是参与者，你接下来会怎么猜？,800元！,高了,400元！,600元！,低了,高了,参与者,主持人：李咏,例2：给定素数表，设计算法，将936分解成 素因数的乘积。,判断936是否为素数：,否,2,936468 2,936234 22,936117 23,否,2,否,2,否,93639 23 3,3,否,3,93613 23 32,是,结束,分解结果为：93613 23 32,练习：将下列两个数分解素因数（1）840（2）1764,例3：设计一个算法，求 840 与 1764 的最大 公因数。,解

3、：算法步骤如下：,1.先将840进行素因数分解：840=23357；,3.确定它们公共素因数：2,3,7；,4.确定公共素因数的指数：公共素因数2，3,7的指数分别为2,1,1；,2.先将1764进行素因数分解:1764=223272；,5.最大公因数为：223171=84,写算法的要求,写出的算法，必须能解决一类问题（如求两个正整数的最大公因数），并且能重复使用。算法过程要一步一步执行，每一步执行的操作必须明确，不能含混不清，而且在有限步骤内能得出结果。算法要简洁，清晰可读，不能搞得繁杂。,算法不同于求解一个具体问题的方法，是这种方法的高度概括。一个好的算法有如下要求：,算法是什么,算法可以

4、理解为由基本运算及规定的运算顺序构成的一个完整的解题步骤，或看成是按要求设计好的有限的、确切的计算步骤，并且这样的步骤能解决一类问题。,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。,“韩信点兵”问题,思考以下问题的算法：,一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,解:,2先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。,3取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元

5、。,1.把银元分成3组，每组3枚。,说明：,1算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。,2算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。,3从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法,算法的特点：,有限性：一个算法的步骤必须是有限的，必须在有 限操作之后停止，不能是无限的.确定性：算法中的每一步应该是确定的并且能有效 地执行且得到确定的结果，而不应当是模 棱两可.普遍性：一个算法通常设计成能解决一类问题，

6、不不唯一性：求解某一个问题的解法不一定是唯一 的，对于一个问题可以有不同的算法.,是仅仅解决一个单独问题的。,例四 设函数f(x)的图象是一条连续不断的曲线，写出用“二分法”求方程 f(x)=0的一个近似解的算法.,第一步，取函数f(x)，给定精确度d.,第二步，确定区间a，b，满足f(a)f(b)0.,第五步，判断a,b的长度是否小于d或f(m)是否等于0.若是，则m是方程的近似解；否则，返回第三步.,第三步，取区间中点.,第四步，若f(a)f(m)0,则含零点的区间 为a,m,否则，含零点的区间为m，b.,将新得到的含零点的区间仍记为a,b;,两个大人和两个小孩一起渡河，渡口只有一条小船每次只能渡1 个大人或两个小孩，他们四人都会划 船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。,S1 两个小孩同船过河去；,S2 一个小孩划船回来；,S3 一个大人划船过河去；,S4 对岸的小孩划船回来；,S5 两个小孩同船渡过河去；,S6 一个小孩划船回来；,S7 余下的一个大人独自划船渡过河去；对岸的小孩划船回来；,S8 两个小孩再同时划船渡过河去。,智力大比拼,