算法的基本思想

§1算法的基本思想课题引入作为家里的一员，在平时分担某些力所能及的事是我们应尽的义务，你每天都帮家里做事吗？你会烧开水吗？请写出你在家中烧开水的过程1、往壶内注水；2、点火加热；3观察：如果水开，则停止烧火，否则继续烧火；4、如果水未开，重复“3”直至水开。总结：“1”其实大部分事情都是按照一定的程序执行，因此要理清事情的每一步。“2”判断水与否烧开与与否继续烧火的过程是一种反馈与判断过程，因此有必要不停重复过程“3”事实上，我们完毕任何事，都要有一种环节，合理安排环节，会达成事半功倍的效果。在我们数学的意义来讲，在解决某些问题时，需要设计出一系列可操作或可计算的环节，通过实施这些环节来解决问题，我们普通把这些环节称为解决问题的一种算法。这种描述不是算法的定义，但反映了算法的基本思想。中国古代数学以算法为重要特性，这能够从中国古代数学家的著作中看出端倪，其中最具代表性的就是《九章算术》，就其成就来说堪称是世界数学名著，其内容按类分章,以数学问题的形式出现，涉及分数四则运算，开平方和开立方(涉及二次方程数值的解法)，盈局限性术，多个面积和体积的计算公式，线性方程组解法，正负数运算的加减法法则，勾股形解法等。另外尚有贾宪的《黄帝九章算法细草》、刘益《议古本源》、秦九韶的《数书九章》，杨辉的《详解九章算法》和《杨辉算法》等。随着计算科学和信息技术的飞速发展，算法的思想已经渗入到社会的方方面。在以前的学习中，即使没有出现算法这个名词，但事实上在数学教学中已经渗入了大量的算法思想，如四则运算的过程、求解方程的环节等等。完毕这些工作都需要一系列程序化的环节，这就是算法的思想。【例1】在央视的《幸运52》节目中，规定参加者快速猜出物品的价格。主持人出示某件物品，参加者每次估算出一种价格，主持人只能回答高了、低了或者对的。在某次节目中，主持人出示了一台价值在1000元以内的随身听，并开始了竞猜。下面是主持人和参加者的一段对话：….如果你是参加者，你接下来会怎么猜？800元！高了400元！600元！低了高了参与者主持人：李咏例2两个大人和两个小孩一起渡河，渡口只有一条小船每次只能渡1个大人或两个小孩，他们四人都会划船，但都不会游泳试问他们如何渡过河去？请写出一种渡河方案。S1两个小孩同船过河去；S2一种小孩划船回来；S3一种大人划船过河去；S4对岸的小孩划船回来；S5两个小孩同船渡过河去；S6一种小孩划船回来；S7余下的一种大人独自划船渡过河去；对岸的小孩划船回来；S8两个小孩再同时划船渡过河去。智力大比拼在给定素数表的条件下，请你设计一种算法，将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实际操作写算法的规定算法不同于求解一种具体问题的办法，是这种办法的高度概括。一种好的算法有以下规定：写出的算法，必须能解决一类问题（如一元二次方程求根公式），并且能重复使用。算法过程要能一步一步执行，每一步执行的操作，必须确切，不能含混不清，并且在有限步能得出成果。算法要简洁，要清晰可读，不能弄搞繁杂，以以致于易程序化。思考下列问题的算法：一位商人有9枚银元，其中有1枚略轻的是假银元。你能用天平（不用砝码）将假银元找出来吗？解:1.把银元分成3组，每组3枚。

2．先将两组分别放在天平的两边。如果天平不平衡，那边假银元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里。3．取出含假银元的那一组，从中任取两枚放在天平的两边。如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则末称的那一枚就是假银元。算法是什么算法能够理解为由基本运算及规定的运算次序构成的完整的解题环节，或当作按规定设计好的有限的、确切的计算序列，并且这样的环节或序列能解决一类问题。当代意义上的“算法”普通是指能够用计算机来解决的某一类问题的程序或环节。求方程在[0,5]上的近似解，精确到0.05分析：如何求方程的根？我们能够参考p91～92解法1（1）移项，得（2）两边同时加1并配方得：（3）两边同时开放得：x=3或x=-1（4）取x=3解法21由于f(0)=-3,f(5)=12,f(0).f(5)<0,则在区间[0,5]上有解，精度为：5-1＝4>0.052取[0,5]的中点2.5；计算f(2.5)=-1.75,则f(5)f(2.5)<0,精度：5-2.5＝2.5>0.013取[2.5,5]的中点3.75，计算f(3.75)=3.5625,则f(2.5)f(3.5625)<0,精度：3.5625-2.5＝1.1625>0.054取[2.5,3.5625]的中点3.03125，则f(3.03125)=0.12598,则f(3.03125)f(2.5)<0,精确度：3.03125-2.5＝0.53125>0.055取[2.5,3.03125]的中点2.765625，则f(2.765625)=-0.88257,精度：3.03125-2.765625＝0.2657>0.056取[2.765625,3.03125]的中点2.8984，f(2.8984)=-0.340,则f(2.8984)f(3.03125)<0,精度：3.03125-2.898＝0.13>0.057取[2.8984,3.03125]的中点2.9648，则f(2.96)=-0.140,则f(3.03125)f(2.9648)<0,精度：3.031-2.968＝0.06>0.018取[2.9648,3.031]的中点3.009，则f(3.009)=0.008,则f(3.009)f(2.965)<0,精度：3.009-2.965＝0.045<0.059取[3.009,2.965]的中点2.99，则x=2.99阐明：1算法事实上就是解决某一类问题的环节和办法，在解决问题时形成的规律性的东西，按照算法描述的规则与环节，一步一步地去做，最后便能解决问题。2算法的基本思想就是我们分析问题时的想法。由于想法不同思考的角度不同，着手点不同，同一问题存在不同的算法，算法有优劣之分。3从熟悉的问题出发，体会算法的程序化思想，学会用自然语言来描述算法算法的特性有穷性：一种算法应包含有限的操作环节而不能是无限的。