软件算法
计算机术语
要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个软件算法,然后再根据软件算法编写程序。软件算法在现实生活中有很多的运用 ,在不同的领域也会采用不同的软件程序进行计算。随着信息化的不断发展 ,计算机软件算法已经逐渐成为一种最重要的运算模式,近些年来,我国十分重视对计算机软件技术的相关问题探究,同时,在各大高校 ,也不断重视培养相关的计算机软件操作方面的人才 ,并逐步深化软件算法在现实生活中的运用。
简介
要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个软件算法,然后再根据软件算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。
算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机软件算法指令所描述的顺序执行算法的指令能在有限的步骤内终止,或终止于给出问题的解,或终止于指出问题对此输入数据无解。
算法设计
迭代法
迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 ,用某种数学方法导出等价的形式 ,然后按以下步骤执行:
1、选一个方程的近似根,赋给变量 ;
2、将 的值保存于变量 ,然后计算 ,并将结果存于变量;
3、当 与 的差的绝对值还小于指定的精度要求时,重复步骤2的计算。
若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的 就认为是方程的根。
具体使用迭代法求根时应注意以下两种可能发生的情况:
1、如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制。
2、 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
穷举搜索法
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
对一组数穷尽所有排列,有很直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。
穷举搜索法的缺陷是编写的程序通常不能适应变化的情况。
递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 的解,当 时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为 的解后,由问题的递推性质,能从已求得的规模为 的一系列解,构造出问题规模为 的解。这样,程序可从 或 出发,重复地,由已知至 规模的解,通过递推,获得规模为 的解,直至得到规模为 的解。
递归法
递归是设计和描述算法的一种有力的工具,它在复杂算法的描述中被经常采用,能采用递归描述的算法通常有这样的特征:为求解规模为 的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模 时,能直接得解。
递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。
编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。
回溯法
回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。
在用回溯法求解有关问题的过程中,一般是一边建树,一边遍历该树。一般采用非递归方法。回溯法的非递归算法的一般流程如下:
在用回溯法求解问题,也即在遍历状态空间树的过程中,如果采用非递归方法,则我们一般要用到栈的数据结构。这时,不仅可以用栈来表示正在遍历的树的结点,而且可以很方便地表示建立孩子结点和回溯过程。例如在组合问题中,我们用一个一维数组Stack[ ]表示栈。开始栈空,则表示了树的根结点。如果元素1进栈,则表示建立并遍历(1)结点;这时如果元素2进栈,则表示建立并遍历(1,2)结点;元素3再进栈,则表示建立并遍历(1,2,3)结点。这时可以判断它满足所有约束条件,是问题的一个解,输出(或保存)。这时只要栈顶元素(3)出栈,即表示从结点(1,2,3)回溯到结点(1,2)。
贪婪法
贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。
例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。
应用领域
建筑工程
软件算法目前已经很好的运用于工程建筑领域。许多建筑工程单位利用计算机的软件算法进行相关的成本预算 ,收益预算以及采购预算等。相关的建筑单位可以根据特定的程序,对所采用的数据进行输入,完成输入后,利用统一的程序计算出建筑工程中的相关数据。目前,随着计算机软件算法水平的提高 ,建筑工程领域对软件算法的大量运用 ,很大程度上提高了工程建筑的运作效率。
船舶建造
软件算法在船舶建造领域有着广泛的运用 。在船舶建造过程中,往往通过软件算法进行合理的计算所要使用的材料量,利用软件算法中的贪婪算法,可以最大程度上节省所要运用的建造材料以及资源,减少在船舶建造过程中不必要的资源的浪费。因此可以说,软件算法的广泛运用,在很大程度上解决了船舶建造过程中有关资源浪费的一系列问题。因此,在我国船舶建造过程中一般都会选择软件算法的运用。
金融领域
在金融领域方面利用软件算法,是近些年逐步运用的一种形式。通过软件算法,可以实时的分析出现阶段金融时态的变化过程,以及相关金融数据的掌握,因此软件算法在金融领域的运用逐步深化。现阶段,我国银行业发行的金融 IC 卡全部采用国外芯片和国际通用标准算法(金融社保卡除外),这是软件算法的一种重要的运算形式 ,这种方式方法的运用 ,无疑为我国金融银行领域提供了良好的便利条件与便利基础。
资源开发
软件算法也广泛的运用于资源开发领域过程中 ,资源的高效率的合理开发和利用是近些年来所追求的目标 ,因此 ,对资源的开发与利用 ,利用软件算法进行对开采度等数据的计算 ,可以很好的把握资源的开采程度 ,防止资源开采过度造成资源的枯竭 ,或者资源的开采力度不够 ,不能实现很大的经济效益。因此可以说 ,计算机软件算法在资源开采方面也有很大的利用程度。
软件算法在多个领域有所运用 ,不仅局限于以上所列举的 3 个领域,软件算法还在医学、道路设计、数学研究等多种领域有所利用和发展 ,近些年来 ,越来越多的软件算法被开发 ,不同的领域运用不同的软件算法进行相关的计算,带来了极大的便利性。
最新修订时间:2022-08-25 13:44
目录
概述
简介
算法设计
参考资料