《算法的基本思想》参考1.pptx

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