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