2019-2020学年高中数学 第2章 算法初步 2-1-1 算法的基本思想（1）课件 北师大版必修

算法初步第二章§1算法的基本思想第一课时算法的基本思想(1)自主预习学习目标目标解读1.了解算法的含义，体会算法的思想．2．能够用自然语言叙述算法，掌握正确的算法应满足的要求．3．培养学生逻辑思维能力与表达能力.重点：算法概念以及用自然语言描述算法．难点：用自然语言描述算法.1．算法的概念算法是解决的一系列步骤或程序，只要按照这些步骤执行，都能使问题得到解决．知识梳理某类问题(1)算法并没有一个精确的定义，可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或看成按要求设计好的有限的、确切的计算序列，并且这样的步骤或序列能够解决一类问题．(2)通俗点说，算法就是计算机解题的过程．在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法，前者是推理实现的算法，后者是操作实现的算法．(3)描述算法可以有不同的方式．例如，可以用自然语言和数学语言加以叙述，也可以用算法语言给出精确的说明，或者用框图直观地显示算法的全貌．2．算法的基本思想在解决某些问题时，需要设计出的步骤，通过实施这些步骤来解决问题，通常把这些步骤称为解决这些问题的．这种解决问题的思想方法称为算法的基本思想．一系列可操作或可计算算法问题探究：算法与一般意义上具体问题的解法相同吗？提示：不同．算法与一般意义上具体问题的解法既有联系又有区别，它们之间是一般与特殊、抽象与具体的关系．算法的获得要借助于一般意义上具体问题的求解方法，而任何一个具体问题都可以利用这类问题的一般算法来解决．在解决某些问题时，需要设计出一系列可操作或可计算的步骤，这些步骤称为解决这些问题的算法，这种解决问题的思想方法称为算法的思想．3．算法的特点(1)有穷性：算法的步骤序列是的．一个算法对任何合理的输入值必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成．(2)：算法必须能有效地执行，并能得到确定的结果．算法的步骤中不能含有模糊不清、容易让人误解的叙述．有限确定性(3)顺序性：算法从初始步骤开始，分为若干个明确具体的步骤，前一步骤是后一步骤的前提，后一步骤是前一步骤的后续，且除了最后一步外，每一个步骤只能有一个确定的后续．(4)不唯一性：解决同一问题的算法可以是的．(5)可行性：算法中的每一个步骤必须是能的.不唯一实现要点导学解决有关算法的概念判断题应根据算法的特点进行判断，特别注意能在有限时间内求解某类问题，其中的每条规则必须是明确可行的，不能模棱两可，对同一个问题可设计不同的算法．要点一算法的概念下列语句表述的是算法的有()①从广州到北京旅游，先坐火车，再坐飞机抵达②解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1③方程x2－1＝0有两个实根④求1＋2＋3＋4的值，先计算1＋2＝3，再由3＋3＝6,6＋4＝10得最终结果是10A．1个B．2个C．3个D．4个【思路启迪】(1)算法的概念是什么？(2)算法的特点是什么？【解析】①中说明了从广州到北京的行程安排，完成任务；②中给出了一元一次方程这一类问题的解决方式；④中给出了求1＋2＋3＋4的一个过程，最终得出结果；对于③，并没有说明如何去算，故①②④表述的是算法，③表述的不是算法．【答案】C针对判断语句是否是算法的问题，正确理解算法的概念及其特点是解决问题的关键，要看它的步骤是否是明确的和有效的，而且能在有限步之内解决这一问题．下列对算法的理解不正确的是()A．一个算法应包含有限的步骤，而不能是无限的B．算法中的每一步骤都应当是确定的，而不应当是含糊的、模棱两可的C．算法中的每一步骤都应当有效地执行，并得到确定的结果D．一个问题只能设计出一种算法解析：A：算法的有限性是指包含的步骤是有限的，故A正确；B：算法的确定性是指每一步都是确定的，故B正确；C：算法的每一步都是确定的，且每一步都应有确定的结果，故C正确；D：对于同一个问题可以有不同的算法，故D错误．答案：D在这类算法的设计中，对自然数进行素因数分解是基础，是解决这个问题的“平台”．同样地，求两个自然数的最大公因数的算法，也可以成为解决其他问题的“平台”．“平台”的思想在算法设计中是一个最基本的思想，也是数学中思考问题的一个重要思想．要点二求最大公因数的算法设计一个算法求5280与12155的最大公因数．【思路启迪】(1)如何将一个素数进行因数分解？(2)有几种方法？(3)分解后怎样求两个数的最大公因数？【解】算法步骤如下：1．先将5280进行素因数分解：5280＝25×3×5×11；2．然后将12155进行素因数分解：12155＝5×11×13×17；3．确定它们的公共素因数：5,11；4．确定公共素因数的指数：公共素因数5,11的指数分别为1,1；5．最大公因数为：5×11＝55.求两个数的最大公因数的关键是对每个数准确进行因数分解，再找出两个数的公共素因数，再对公共素因数确定系数，从而求出两个数的最大公因数．设计求1356和2400的最小公倍数的算法．解：算法如下：1.将1356进行质因数分解：1356＝2×2×3×113；2．将2400进行质因数分解：2400＝2×2×2×2×2×3×5×5；3．确定它们的公共因数：2×2×3；4．确定它们的非公共因数23×113×52；5．确定它们的最小公倍数：25×3×52×113＝271200.我们经常遇到类似求1＋2＋3＋…＋100000的和，或者求1×2×3×…×100000的积的问题，求解过程往往使用若干步可重复的简单运算(规律)来完成．也称为递推算法．其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点．要点三求和(积)问题的算法给出求2＋4＋6＋8＋10的一个算法．【思路启迪】该式的求和有几种方法？分几步才可以求出该式的和？【解】解法一：按照逐一相加的程序进行．1．计算2＋4得到6；2．将第1步的运算结果6与6相加得到12；3．将第2步的运算结果12与8相加得到20；4．将第3步的运算结果20与10相加得到30.解法二：可运用公式2＋4＋6＋…＋2n＝n2＋2n2＝n(1＋n)．1．取n＝5；2．计算n(1＋n)；3．输出运算结果．对于同一个问题从不同角度出发，可设计不同的算法，其最终结果是相同的，但算法的方法不一样，解决的繁简程度也有所不同．因此，需找出解决问题的最好的算法，提高效率．求1×3×5×7×9×11的值，写出其算法．解：1.先求1×3，得到结果3；2．将第1步所得结果3再乘以5，得到结果15；3．再将15乘以7，得到结果105；4．再将105乘以9，得到945；5．再将945乘以11，得到10395，即是最后结果．易错点忽视算法的内涵对于下列算法的描述，正确的有()①算法就是某个问题的解题过程②算法执行后可以产生不确定的结果③解决某一问题的算法是唯一的④算法必须在有限步内操作之后停止A．1个B．2个C．3个D．4个易错盘点【错因分析】对算法的理解不清，而造成误选．【正确解答】根据算法的概念及特征，可知算法具有概括性，即能解决一类问题，而不是只解决某个问题，故①错误；同时算法具有确定性、不唯一性和有穷性，所以②③不正确，而④正确．因此正确的只有④，故选A.在学习算法的过程中，要注意算法的重要特征．下列关于算法的叙述中，不正确的是()A．计算机解决任何问题都需要算法B．只有将要解决的问题分解为若干步骤，并且用计算机能够识别的语言描述出来，计算机才能解决问题C．算法执行后可以不产生确定的结果D．解决同一个问题的算法并不唯一，而且每一个算法都要一步一步执行，每一步都要产生确切的结果解析：算法的主要特征是确定性和顺序性，确定性包括结果明确，每一步产生的结果和最后的结果都是明确的；顺序性包括步骤确切，每一步执行什么是明确的；因此，C项不正确，故选C.答案：C1．算法的概念：对一类问题的机械的、统一的求解方法．算法是由基本运算及规定的运算顺序所构成的完整的解题步骤，或者是按照要求设计好的有限的计算序列，并且这样的步骤或序列能解决一类问题．2．算法的特征：(1)有穷性；(2)确定性；(3)顺序性；(4)不唯一性；(5)可行性．学习小结1．下列关于算法的说法正确的个数为()①求解某一类问题的算法是唯一的②算法必须在有限步操作之后停止③算法的每一步操作必须是明确的，不能有歧义或模糊④算法执行后一定产生确定的结果A．1B．2C．3D．4随堂训练解析：由算法特性知，算法具有有穷性、确定性、可输出性，故②③④均对，选C.答案：C2．指出下列哪个不是算法()A．解方程2x－6＝0的过程是移项和系数化为1B．从济南到温哥华要先乘火车到北京，再转乘飞机C．解方程2x2＋x－1＝0D．利用公式S＝πr2计算半径为3的圆的面积就是计算π×32解析：算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成是按要求设计好的有限的确切的计算序列，并且这样的步骤或序列能解决一类问题，故C不是算法．答案：C3．下列哪个不是算法的特征()A．顺序性B．确定性C．有穷性D．唯一性解析：算法的特征有：有穷性、确定性、顺序性、不唯一性、可行性．答案：D4．著名数学家华罗庚“烧水泡茶”的两个算法．算法一：第一步：烧水；第二步；水烧开后，洗刷茶具；第三步：沏茶．算法二：第一步：烧水；第二步：烧水过程中，洗刷茶具；第三步：水烧开后沏茶．这两个算法哪个算法更高效？为什么？_______________________________________________________答案：第二个算法更高效，因为节约时间5．写出求1＋2＋3＋4＋5＋6＋…＋100的一个算法．可运用公式1＋2＋3＋…＋n＝nn＋12直接计算．1．①____________________________________；2．②____________________________________；3．输出计算的结果．答案：①取n＝100②计算nn＋12