算法、框图、概率基础知识

《算法、框图、概率基础知识》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、—算法的含义、程序框图要点精讲1.算法的概念(1)算法的定义：广义的算法是指完成某项工作的方法和步骤，那么我们可以说洗衣机的使用说明书是操作洗衣机的算法，菜谱是做菜的算法等等。在数学中，现代意义的算法是指可以用计算机来解决的某一类问题的程序和步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成。(2)算法的特征：①确定性：算法的每一步都应当做到准确无误、“不重不漏”。“不重”是指不是可有可无的、甚至无用的步骤，“不漏”是指缺少哪一步都无法完成任务。②逻辑性：算法从开始的"第一步”直到“最后一步”之间做到环环相扣。分工明确，“前一步”是“后一步”的

2、前提，“后一步”是“前一步”的继续。③有穷性：算法要有明确的开始和结束，当到达终止步骤时所要解决的问题必须有明确的结果，也就是说必须在有限步内完成任务，不能无限制的持续进行。(3)算法的描述：自然语言、程序框图、程序语言。1.程序框图(1)程序框图的概念：程序框图又称流程图,是一种用规定的图形、指向线及文字说明来准确、直观地表示算法的图形；(2)构成程序框的图形符号及其作用P衣始法少.用烹LO中葬耀法的们用理诧它的处r,同的不据否口”•，处或是出丫口”sffAWS、写理衣和奮躺处式别处内判成处不标“出输、框入输框m二理处VV流程线塑进彳邨前暂向以及先后顺序r

3、-<7>>f循环框o连结点连注释框理解框團(3)程序框图的构成一个程序框图包括以下几部分：实现不同算法功能的相对应的程序框；带箭头的流程线；程序框内必要的说明文字。1.几种重要的结构(1)顺序结构顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的。它是由若干个依次执行的步骤组成的，它是任何一个算法都离不开的一种基本算法结构。AB示意图/输入n/flag=l见示意图和实例:顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来,按顺序执行算法步骤。如在示意图中，A框和B框是依次执行的，只有在执彳丁完A框指定的操作后，才能接

4、着执行BA[BI］线框内I构中含i行到此否成框所指定的操作。（2）条件结构：如下面图示中虚］是一个条件结构，此结］有一个判断框，算法执i判断给定的条件P是立，选择不同的执行框（A框、B框）。无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框、B框都不执行。A框或B框中可以有一个是空的，即不执行任何操作。见示意图（3）循环结构在一些算法中要求重复执行同一操作的结构称为循环结构。即从算法某处开始，按照一定条件重复执行某一处理过程。重复执行的处理步骤称为循环体。循环结构有两种形式：当型循环结构和直到型循环结构。①当型循环结构，如左

5、下图所示，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，返回来再判断条件P是否成立，如果仍然成立,返回来再执行A框，如此反复执行A框，直到某一次返回来判断条件P不成立时为止，此时不再执行A框，离开循环结构。继续执行下面的框图。①直到型循环结构，如右下图所示，它的功能是先执行重复执行的A框，然后判断给定的条件P是否成立，如果P仍然不成立，则返回来继续执行4框，再判断条件P是否成立。以次重复操作，直到某一次给定的判断条件F时成立为止，此时不再返回来执行A框，离开循环结构。继续执行下面的框图。见示意图—算法案例要点精讲1・求最大公约数(1)辗转相除法辗

6、转相除法求两个数的最大公约数，其算法可以描述如下：①输入两个正整数m和n；②求余数I•:计算m除以n,将所得余数存放到变量I•中；③更新被除数和余数：m=n,n=r；④判断余数r是否为0o若余数为0,则输出结果；否则转向第②步继续循环执行。如此循环，直到得到结果为止。(1)更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者,副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。步骤：I.任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。II

7、.以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这操作,直到所得的数相等为止，则这个数(等数)就是所求的最大公约数。2.秦九韶算法秦九韶算法的一般规则：秦九韶算法适用一般的多项式f(x)=anxn+an.ixn'1+....+aix+a0的求值问题。用秦九韶算法求一般多项式f(x)=anX^an-ix^^-.-.+arX+ao当时的函数值，可把n次多项式的求值问题转化成求n个一次多项式的值的问题，即求v0=anvi=anx+an-iv2=vix+an-2v3=v2x+an-3vn=vn-ix+ao观察秦九韶算法的数学模型，计算Vk

8、时要用到Vk-1的值，若令V0=8n。我们可以得到下