文档介绍：,这种算法称为计算机算法。算法(algorithm)是一组严谨地定义运算次序规则,而且每一个规则全部是有效,同时是明确;此次序将在有限次数后终止。算法是对特定问题求解步骤一个描述,它是指令有限序列,其中每一条指令表示一个或多个操作。 1算法基础特征(1)可行性(effectiveness):针对实际问题而设计算法,实施后能够得到满意结果。(2)确定性(definiteness):算法中每一个步骤全部必需有明确定义,不许可有模棱两可解释和多义性。(3)有穷性(finiteness):算法必需在有限时间内做完,即算法必需能在实施有限个步骤以后终止。(4)拥有足够情报:要使算法有效必需为算法提供足够情报当算法拥有足够情报时,此算法才最有效;而当提供情报不够时,算法可能无效。 2算法基础要素(1)算法中对数据运算和操作:每个算法实际上是按解题要求从环境能进行全部操作中选择适宜操作所组成一组指令序列。计算机能够实施基础操作是以指令形式描述。一个计算机系统能实施全部指令集合,称为该计算机系统指令系统。计算机程序就是按解题要求从计算机指令系统中选择适宜指令所组成指令序列在通常计算机系统中,基础运算和操作有以下4类: ①算术运算:关键包含加、减、乘、除等运算; ②逻辑运算:关键包含“和”、“或”、“非”等运算; ③关系运算:关键包含“大于”、“小于”、“等于”、“不等于”等运算; ④数据传输:关键包含赋值、输入、输出等操作。(2)算法控制结构:一个算法功效不仅仅取决于所选择操作,而且还和各操作之间实施次序相关。算法中各操作之间实施次序称为算法控制结构。算法控制结构给出了算法基础框架,它不仅决定了算法中各操作实施次序,而且也直接反应了算法设计是否符合结构化标准。描述算法工具通常有传统步骤图、N-S结构化步骤图、算法描述语言等。一个算法通常全部能够用次序、选择、循环3种基础控制结构组合而成。(3)算法设计基础方法计算机算法不一样于人工处理方法,下面是工程上常见多个算法设计,在实际应用时,多种方法之间往往存在着一定联络。(1)列举法列举法是计算机算法中一个基础算法。列举法基础思想是,依据提出问题,列举全部可能情况,并用问题中给定条件检验哪些是需要,哪些是不需要。列举法特点是算法比较简单。但当列举可能情况较多时,实施列举算法工作量将会很大。所以,在用列举法设计算法时,使方案优化,尽可能降低运算工作量,是应该关键注意。(2)归纳法归纳法基础思想是,经过列举少许特殊情况,经过分析,最终找出通常关系。从本质上讲,归纳就是经过观察部分简单而特殊情况,最终总结出通常性结论。(3)递推递推是指从已知初始条件出发,逐次推出所要求各中间结果和最终结果。其中初始条件或是问题本身已经给定,或是经过对问题分析和化简而确定。递推本质上也属于归纳法,工程上很多递推关系式实际上是经过对实际问题分析和归纳而得到,所以,递推关系式往往是归纳结果。对于数值型递推算法必需要注意数值计算稳定性问题。(4)递归大家在处理部分复杂问题时,为了降低问题复杂程度(如问题规模等),通常总是将问题逐层分解,最终归结为部分最简单问题。这种将问题逐层分解过程,实际上并没有对问题进行求解,而只是当处理了最终那些最简单问题后,再沿着原来分解逆过程逐步进行综合,这就是递归基础思想。递归分为直接递归和间接递归两种。(5)减半递推技术实际问题复杂程度往往和问题规模有着亲密联络。所以,利用分治法处理这类实际问题是有效。工程上常见分治法是减半递推技术。所谓“减半”,是指将问题规模减半,而问题性质不变;所谓“递推”,是指反复“减半”过程。(6)回溯法在工程上,有些实际问题极难归纳出一组简单递推公式或直观求解步骤,而且也不能进行无限列举。对于这类问题,一个有效方法是“试”。经过对问题分析,找出一个处理问题线索,然后沿着这个线索逐步试探,若试探成功,就得到问题解,若试探失败,就逐步回退,换别路线再逐步试探。 4算法设计要求通常一个好算法应达成以下目标:(l)正确性(correctness) 正确性大致能够分为以下4个层次: ①程序不含语法错误; ②程序对于几组输入数据能够得出满足规格说明要求结果; ③程序对于精心选择经典、苛刻而带有刁难性几组输入数据能够得出满足规格说明要求结果; ④程序对于一切正当输入数据全部能产生满足规格说明要求结果。(2)可读性(readability) 算法关键是为了方便入阅读和交流,其次才是其实施。可读性好有利于用户对算法了解;晦涩难懂程序易于隐藏较多错误,难以调试和修改。(3)健壮性(robustness) 当输入数据非法时,算法也能合适地做出反应或进行处理,而不会产生莫名其妙输出结果。(4)效率和低存放量需求效率指是程序实施时,对