算法抽样估计案例文档.doc

算法的定义：是指可以用计算机来解决的某一类问题的程序或步骤，这些程序或步骤必须是明确和有效的，而且能够在有限步之内完成算法设计要遵循简易的原则。 特征：有限性：一个算法的步骤序列是有限的，必须在有限操作之后停止，不能是无限的.确定性：算法中的每一步应该是确定的并且能有效地执行且得到确定的结果，而不应当是模棱两可.顺序性与正确性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都准确无误，才能完成问题.不唯一性：求解某一个问题的解法不一定是唯一的，对于一个问题可以有不同的算法.普遍性：很多具体的问题，都可以设计合理的算法去解决，如心算、计算器计算都要经过有限、事先设计好的步骤加以解决.两类算法问题：数值性计算问题，如：解方程（或方程组），解不等式（或不等式组），套用公式判断性的问题，累加，累乘等一类问题的算法描述，可通过相应的数学模型借助一般数学计算方法，分解成清晰的步骤，使之条理化即可。非数值性计算问题，如：排序、查找、变量变换、文字处理等需先建立过程模型，通过模型进行算法设计与描述。程序框图：程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形常用程序框及其功能：图形符号名称功能终端框(起止框)表示一个算法的起始和结束输入、输出框表示一个算法输入和输出的信息处理框(执行框)赋值、计算判断框判断某一条件是否成立，成立时在出口处标明“是”或“Y”；不成立时标明“否”或“N”流程线连接程序框 连接点连接程序框图的两部分 画程序框图的规则如下：使用标准的图形符号。框图一般按从上到下、从左到右的方向画。除判断框外，大多数流程图符号只有一个进入点和一个退出点。判断框具有超过一个退出点的唯一符号。判断框分两大类，一类判断框“是”与“否”两分支的判断，而且有且仅有两个结果；另一类是多分支判断，有几种不同的结果。在图形符号内描述的语言要非常简练清楚。程序框图的三种基本结构：(1)顺序结构顺序结构是最简单的算法结构，语句与语句之间，框与框之间是按从上到下的顺序进行的，它是由若干个依次执行的处理步骤组成的，它是任何一个算法都离不开的一种基本算法结构。顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来，按顺序执行算法步骤。其结构形式如图所示(2)条件结构在一个算法中，经常遇到一些条件的判断，算法的流程根据条件是否成立有不同的流向这种先根据条件作出判断，再决定执行哪一种操作的结构称为条件结构，其结构形式如图甲、乙所示：(3)循环结构在一些算法中，经常会出现从某处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构，反复执行的处理步骤为循环体，显然，循环结构中一定包含条件结构。循环结构又称重复结构，循环结构可细分为两类：循环结构有两种形式：当型（while型）：先判断条件，再执行循环体；当型循环结构，它的功能是当给定的条件P成立时，执行A框，A框执行完毕后，再判断条件P是否成立，如果仍然成立，再执行A框，如此反复执行A框，直到某一次条件P不成立为止，此时不再执行A框，离开循环结构。直到型（until型）：先执行一次循环体，再判断条件。直到型循环结构，它的功能是先执行，然后判断给定的条件P是否成立，如果P仍然不成立，则继续执行A框，直到某一次给定的条件P成立为止，此时不再执行A框，离开循环结构。注：循环结构要在某个条件下终止循环，这就需要条件结构来判断。因此，循环结构中一定包含条件结构，但不允许“死循环”。在循环结构中都有一个计数变量和累加变量。计数变量用于记录循环次数，累加变量用于输出结果。计数变量和累加变量一般是同步执行的，累加一次，计数一次。框图：（1）结构图 首先，你要对所画结构图的每一部分有一个深刻的理解和透彻的掌握，从头至尾抓住主要脉络进行分解，然后将每一步分解进行归纳与提炼，形成一个个知识点并将其逐一地写在矩形框内。最后，按其内在的逻辑顺序将它们排列起来并用线段相连，这样就画成了知识结构图。认识结构图：由构成系统的若干要素和表达各要素之间关系的连线构成。绘制结构图的步骤：先确定组成系统的基本要素，以及这些要素之间的关系；处理好“上位”与“下位”的关系；“下位”要素比“上位”要素更为具体， “上位”要素比“下位”要素更为抽象。再逐步细化各层要素；画出结构图，表示整个系统。（2）流程图绘制流程图的一般过程：首先，用自然语言描述流程步骤；其次，分析每一步骤是否可以直接表达，或需要借助于逻辑结构来表达；再次，分析各步骤之间的关系；最后，画出流程图表示整个流程。鉴于用自然语言描述算法所出现的种种弊端，人们开始用流程图来表示算法，这种描述方法既避免了自然语言描述算法的拖沓冗长，又消除了起义性，且能清晰准确地表述该算法的每一步骤，因而深受欢迎。 设计算法解决问题的主要步骤：第一步、用自然语言描述算法；算法可以用自然语言来描述，但为了使算法的程序或步骤表达得更为直观，我们更经常地用图形方式来表示它。第二步、画出程序框图表达算法；第三步、写出计算机相应的程序并上机实现注：画流程图的时候一定要清晰，用铅笔和直尺画，要养成有开始和结束的好习惯拿不准的时候可以先根据结构特点画出大致的流程，反过来再检查，比如：遇到判断框时，往往临界的范围或者条件不好确定，就先给出一个临界条件，画好大致流程，然后检查这个条件是否正确，再考虑是否取等号的问题，这时候也就可以有几种书写方法了。在输出结果时，如果有多个输出，一定要用流程线把所有的输出总结到一起，一起终结到结束框。基本算法语句输入语句、输出语句和赋值语句INPUT “提示内容”；变量输入语句：INPUT语句，这个语句的一般格式是：其中，“提示内容”一般是提示用户输入什么样的信息。 INPUT语句不但可以给单个变量赋值，还可以给多个变量赋值，其格式为：INPUT “提示内容1，提示内容2，提示内容3，”；变量1，变量2，变量3， 注：“提示内容”与变量之间必须用分号“；”隔开。PRINT “提示内容”；表达式各“提示内容”之间以及各变量之间必须用逗号“，”隔开。但最后的变量的后面不需要。输出语句：PRINT语句是输出语句。它的一般格式是：同输入语句一样，表达式前也可以有“提示内容”。 输出语句的用途：输出常量，变量的值和系统信息；输出数值计算的结果。变量=表达式赋值语句：用来表明赋给某一个变量一个具体的确定值的语句。除了输入语句， 赋值语句也可以给变量提供初值。它的一般格式是：赋值语句中的“=”叫做赋值号。赋值语句的作用：先计算出赋值号右边表达式的值，然后把这个值赋给赋值号左边的变量，使该变量的值等于表达式的值。注：赋值号左边只能是变量名字，而不能是表达式。如：2=X是错误的。赋值号左右不能对换。如“A=B”“B=A”的含义运行结果是不同的。不能利用赋值语句进行代数式的演算。(如化简、因式分解、解方程等)赋值号“=”与数学中的等号意义不同。条件语句IF 条件 THEN语句1ELSE语句2END IFIF 条件 THEN语句END IF算法中的条件结构是由条件语句来表达的，是处理条件分支逻辑结构的算法语句。它的一般格式是：(IF-THEN-ELSE格式)当计算机执行上述语句时，首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句1，否则执行ELSE后的语句2。在某些情况下，也可以只使用IF-THEN语句：(即IF-THEN格式)计算机执行这种形式的条件语句时，也是首先对IF后的条件进行判断，如果条件符合，就执行THEN后的语句，如果条件不符合，则直接结束该条件语句，转而执行其他语句。条件语句的作用：在程序执行过程中，根据判断是否满足约定的条件而决定是否需要转换到何处去。需要计算机按条件进行分析、比较、判断，并按判断后的不同情况进行不同的处理。循环语句算法中的循环结构是由循环语句来实现的。对应于程序框图中的两种循环结构，一般程序设计语言中也有当型(WHILE型)和直到型(UNTIL型)两种语句结构。即WHILE语句和UNTIL语句。WHILE语句的一般格式是：DO循环体LOOP UNTIL 条件满足条件？循环体是否WHILE 条件循环体WEND满足条件？循环体是否其中循环体是由计算机反复执行的一组语句构成的。WHLIE后面的“条件”是用于控制计算机执行循环体或跳出循环体的。当计算机遇到WHILE语句时，先判断条件的真假，如果条件符合，就执行WHILE与WEND之间的循环体；然后再检查上述条件，如果条件仍符合，再次执行循环体，这个过程反复进行，直到某一次条件不符合为止。这时，计算机将不执行循环体，直接跳到WEND语句后，接着执行WEND之后的语句。因此，当型循环有时也称为“前测试型”循环。UNTIL语句的一般格式是：从UNTIL型循环结构分析，计算机执行该语句时，先执行一次循环体，然后进行条件的判断，如果条件不满足，继续返回执行循环体，然后再进行条件的判断，这个过程反复进行，直到某一次条件满足时，不再执行循环体，跳到LOOP UNTIL语句后执行其他语句，是先执行循环体后进行条件判断的循环语句。算法案例求最大公约数（1）短除法：求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来（2）穷举法（也叫枚举法）：穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 （3）辗转相除法：辗转相除法求两个数的最大公约数，其算法可以描述如下： 输入两个正整数m和n； 求余数r：计算m除以n，将所得余数存放到变量r中；更新被除数和余数：m=n，n=r；判断余数r是否为0。若余数为0，则输出结果；否则转向第步继续循环执行如此循环，直到得到结果为止。例1 求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，可以把它们都变小一点，根据已有的知识即可求出最大公约数8251610512146显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。6105214621813214618131333181333351483331482371483740则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：用较大的数m除以较小的数n得到一个商和一个余数；若0，则n为m，n的最大公约数；若0，则用除数n除以余数得到一个商 和一个余数；若0，则为m，n的最大公约数；若0，则用除数除以余数得到一个商 和一个余数；依次计算直至0，此时所得到的即为所求的最大公约数。（4）更相减损术：我国早期也有解决求最大公约数问题的算法，就是更相减损术。在九章算术中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也，以等数约之翻译为：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。步骤：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2 用更相减损术求98与63的最大公约数.分析：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：9863356335283528728721217141477 所以，98与63的最大公约数是7。辗转相除法与更相减损术的区别：都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到对于两个正整数如何选择合适的方法求他们的最大公约数方法适用范围及特点短除法适合两个较小的正整数或两个质因数较少的正整数，简便易操作。穷举法适合计算机操作，但一一验证过于繁琐。辗转相除法适用于两个较大的正整数，以除法为主，辗转相除法计算次数相对较少，特别当两个数字大小差别较大时计算次数较明显。更相减损术适用于两个较大的正整数，更相减损术以减法为主，计算次数上相对于辗转相处法较多。秦九韶算法秦九韶算法的一般规则：秦九韶算法适用一般的多项式f(x)=anxn+an-1xn-1+.+a1x+a0的求值问题。用秦九韶算法求一般多项式f(x)= anxn+an-1xn-1+.+a1x+a0当x=x0时的函数值，可把n次多项式的求值问题转化成求n个一次多项式的值的问题，即求v0=anv1=anx+an1v2=v1x+an2v3=v2x+an3.vn=vn1x+a0观察秦九韶算法的数学模型，计算vk时要用到vk1的值，若令v0=an。我们可以得到下面的递推公式：v0=anvk=vk1+ank(k=1,2,n)这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现通过一次式的反复计算逐步得出高次多项式的值，对于一个n次多项式，只要作n次乘法和n次加法即可。表达式如下：例题：秦九韶算法计算多项式 答案： 6 ， 6 排序：排序的算法很多，课本主要介绍里两种排序方法：直接插入排序和冒泡排序（1）直接插入排序在日常生活中，经常碰到这样一类排序问题：把新的数据插入到已经排好顺序的数据列中。思想就是读一个，排一个。将数组的第个数据放入数组的第个位置，以后读入的数据与已存入数组的数据进行比较，确定它按从大到小（从小到大）的排列中排在正确的位置。将该位置以及以后的元素向后推移一个位置，将读入的新数填到空出的位置即可。例如：一组从小到大排好顺序的数据列1，3，5，7，9，11，13，通常称之为有序列，我们用序号1，2，3，表示数据的位置，欲把一个新的数据8插入到上述序列中。完成这个工作要考虑两个问题：确定数据“8”在原有序列中应该占有的位置序号。数据“8”所处的位置应满足小于或等于原有序列右边所有的数据，大于其左边位置上所有的数据。将这个位置空出来，将数据“8”插进去。对于一列无序的数据列，例如：49，38，65，97，76，13，27，49，如何使用这种方法进行排序呢？基本思想很简单，即反复使用上述方法排序，由序列的长度不断增加，一直到完成整个无序列就有序了首先，49是有序列，我们将38插入到有序列49中，得到两个数据的有序列：38，49，然后，将第三个数据65插入到上述序列中，得到有序列：38，49，65按照这种方法，直到将最后一个数据65插入到上述有序列中，得到13，27，38，49，49，65，76，97这样，就完成了整个数据列的排序工作。注意到无序列“插入排序算法”成为了解决这类问题的平台（2）冒泡法排序所谓冒泡法排序，形象地说，就是将一组数据按照从小到大的顺序排列时，小的数据视为质量轻的，大的数据视为质量沉的。一个小的数据就好比水中的气泡，往上移动，一个较大的数据就好比石头，往下移动。显然最终会沉到水底，最轻的会浮到顶，反复进行，直到数据列排成为有序列。以上过程反映了这种排序方法的基本思路。理解：以从大到小为例：依次比较相邻的两个数,把大的放前面,小的放后面。即首先比较第1个数和第2个数,大数放前,小数放后；然后比较完成第2个数和第3个数；.；直到比较完了最后两个数。第一趟排序结束,最小的一定沉到最后。重复上过程,仍从第1个数开始,到最后第2个数. 由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序。我们先对一组数据进行分析。设待排序的数据为：49，38，65，97，76，13，27，49