《《算法的基本思想》课件.ppt》由会员分享，可在线阅读，更多相关《《算法的基本思想》课件.ppt（17页珍藏版）》请在装配图网上搜索。
1、1算法的基本思想,课题引入,作为家里的一员，在平时分担一些力所能及的事是我们应尽的义务，你每天都帮家里做事吗？你会烧开水吗？请写出你在家中烧开水的过程,1、往壶内注水； 2、点火加热； 3观察：如果水开，则停止烧火，否则继续烧火； 4、如果水未开，重复“3”直至水开。,总结： “1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“2”判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程，因此有必要不断重复过程“3”,事实上，我们完成任何事，都要有一个步骤，合理安排步骤，会达到事半功倍的效果。在我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施
2、这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法。这种描述不是算法的定义，但反映了算法的基本思想。,中国古代数学以算法为主要特征， 这可以从中国古代数学家的著作中 看出端倪，其中最具代表性的就是 九章算术，就其成就来说堪称 是世界数学名著，其内容按类分章, 以数学问题的形式出现，包括分数 四则运算，开平方和开立方(包括二次方程数值的解法)，盈不足术，各种面积和体积的计算公式，线性方程组解法，正负数运算的加减法法则，勾股形解法等。另外还有贾宪的黄帝九章算法细草、刘益议古根源、秦九韶的数书九章，杨辉的详解九章算法和杨辉算法等。,随着计算科学和信息技术的飞速发展，算法的思想已经渗透到社会
3、的方方面。在以前的学习中，虽然没有出现算法这个名词，但实际上在数学教学中已经渗透了大量的算法思想，如四则运算的过程、求解方程的步骤等等。完成这些工作都需要一系列程序化的步骤，这就是算法的思想。,【例1】在中央电视台的幸运52节目中，要求参与者快速猜出物品的价格。主持人出示某件物品，参与者每次估算出一个价格，主持人只能回答高了、低了或者正确。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参与者的一段对话：,.,如果你是参与者，你接下来会怎么猜？,800元！,高了,400元！,600元！,低了,高了,参与者,主持人：李咏,例2 两个大人和两个小孩一起渡河，
4、渡口只有一条小船每次只能渡1 个大人或两个小孩，他们四人都会划 船，但都不会游泳试问他们怎样渡过河去？请写出一个渡河方案。,S1 两个小孩同船过河去；,S2 一个小孩划船回来；,S3 一个大人划船过河去；,S4 对岸的小孩划船回来；,S5 两个小孩同船渡过河去；,S6 一个小孩划船回来；,S7 余下的一个大人独自划船渡过河去； 对岸的小孩划船回来；,S8 两个小孩再同时划船渡过河去。,智力大比拼,在给定素数表的条件下，请你设计一个算法，将936分成素因数的乘积.,解 算法步骤如下： 判断936是否为素数：否。 确定936的最小素因数：2。936=2*468 判断468是否为素数：否。 确定46
5、8的最小素因数：2。936=2*2*234。 判断234是否为素数：否。 确定234的最小素因数：2。936=2*2*2*117。 判断117是否为素数：否。 确定117的最小素因数：3。936=2*2*2*3*39。 判断39是否为素数：否。 确定39的最小素因数：3。936=2*2*2*3*3*13。 判断13 是否为素数：13是素数，所以分解结束。 分解结果是：936=2*2*2*3*3*13,实际操作,写算法的要求,算法不同于求解一个具体问题的方法，是这种方法的高度概括。一个好的算法有如下要求： 写出的算法，必须能解决一类问题（如一元二次方程求根公式），并且能重复使用。 算法过程要能一
6、步一步执行，每一步执行的操作，必须确切，不能含混不清，而且在有限步能得出结果。 算法要简洁，要清晰可读，不能弄搞繁杂，以以致于易程序化。,思考以下问题的算法：,一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？,解: 1.把银元分成3组，每组3枚。,2先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。,3取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。,算法是什么,算法可以理解为由基本运算及规定的运算顺序构
7、成的完整的解题步骤，或看成按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能解决一类问题。,现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤。,求方程 在0,5上的近似解，精确到0.05,分析：,如何求方程的根？我们可以参考p9192,解法1,（1）移项，得,（2）两边同时加1并配方得：,（3）两边同时开放得：x=3或x=-1,（4）取x=3,解法2,1因为f(0)=-3,f(5)=12,f(0).f(5)0.05,2取0,5的中点2.5；计算f(2.5)=-1.75,则f(5)f(2.5)0.01,3取2.5,5的中点3.75，计算f(3.75)=3.5625
8、,则f(2.5)f(3.5625)0.05,4取2.5,3.5625的中点3.03125，则f(3.03125)=0.12598,则f(3.03125)f(2.5)0.05,5取2.5,3.03125的中点2.765625，则f(2.765625)=-0.88257,精度：3.03125-2.7656250.26570.05,6取2.765625,3.03125的中点2.8984，f(2.8984)=-0.340,则f(2.8984)f(3.03125)0.05,7取2.8984,3.03125的中点2.9648，则f(2.96)=-0.140,则f(3.03125)f(2.9648)0.01
9、,8取2.9648,3.031的中点3.009，则f(3.009)=0.008,则f(3.009)f(2.965)0,精度：3.009-2.9650.0450.05,9取3.009,2.965的中点2.99，则x=2.99,说明：,1算法实际上就是解决某一类问题的步骤和方法，在解决问题时形成的规律性的东西，按照算法描述的规则与步骤，一步一步地去做，最终便能解决问题。,2算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不一样，同一问题存在不同的算法，算法有优劣之分。,3从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法,算法的特征,有穷性： 一个算法应包含有限的操作步骤而不能是 无限的。,确定性：算法中每一个步骤应当是确定的，而不应当 是含糊的、模棱两可的。,有效性：算法中每一个步骤应当能有效地执行，并得到 确定的结果。,输 入: 有零个或多个输入。,输 出: 有一个或多个输出。,习题,5写出过A(2,1)、B(1,0) 、C(2,-1)三点的外接圆 的一个算法。,2二次函数顶点为A(1,-41)、且过B(0,-3)， 写出二次函数f(x)解析式的一个算法。,1写出解方程x2- x-1=0的一个算法。,
《算法的基本思想》课件.ppt
