算法设计

举报
knightaa 发表于 2021/04/11 22:27:00 2021/04/11
【摘要】 算法什么是算法?算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中...

算法
什么是算法?

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算,当其运行时能从一个初始状态和(可能为空的)初始输入开始,经过一系列有限而清晰定义的状态,最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。
算法的特点

有穷性

确切性

输入项

输出项

可行性

一、数据对象的运算和操作:

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类:

1.算术运算:加减乘除等运算

2.逻辑运算:或、且、非等运算

3.关系运算:大于、小于、等于、不等于等运算

4.数据传输:输入、输出、赋值等运算 [1] 

二、算法的控制结构:

一个算法的功能结构不仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。
算法的历史

“算法”即演算法的大陆中文名称出自《周髀算经》;而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi,因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为"algorism",意思是阿拉伯数字的运算法则,在18世纪演变为"algorithm"。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序,因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。 因为"well-defined procedure"缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要作用。
算法的描述
自然语言案例

自然语言就是人们日常用的语言,这种表示方式通俗易懂,下面通过实例具体介绍。

【实例2.1】 求n!。

(1)定义3个变量i、n及mul,并为i和mul均赋初值为1。

(2)从键盘中输入一个数赋给n。

(3)将mul乘以i的结果赋给mul。

(4)i的值加1,判断i的值是否大于n,如果大于n,则执行步骤(5),否则执行步骤(3)。

(5)将mul的结果输出。

 

【实例2.2】 任意输入3个数,求这3个数中的最小数。

(1)定义4个变量分别为x、y、z以及min。

(2)输入大小不同的3个数分别赋给x、y、z。

(3)判断x是否小于y,如果小于,则将x的值赋给min,否则将y的值赋给min。

(4)判断min是否小于z,如果小于,则执行步骤(5),否则将z的值赋给min。

(5)将min的值输出。

 
流程图

流程图是一种传统的算法表示法,它用一些图框来代表各种不同性质的操作,用流程线来指示算法的执行方向。由于它直观形象,易于理解,所以应用广泛,特别是在语言发展的早期阶段,只有通过流程图才能简明地表述算法。

【实例2.3】 从键盘中输入3个数分别赋给a、b、c,要求按大小顺序把它们打印出来。流程图如图所示

3种基本结构

Bohra和Jacopini为了提高算法的质量,经研究提出了3种基本结构,即顺序结构、选择结构和循环结构,因为任何一个算法都可由这3种基本结构组成。这3种基本结构之间可以并列,可以相互包含,但不允许交叉,不允许从一个结构直接转到另一个结构的内部去。 

整个算法都是由3种基本结构组成的,所以只要规定好3种基本结构的流程图的画法,就可以画出任何算法的流程图。

顺序结构是简单的线性结构,在顺序结构的程序里,各操作是按照它们出现的先后顺序执行的,如图所示。

在执行完A框所指定的操作后,接着执行B框所指定的操作,这个结构里只有一个入口点A和一个出口点B。

【实例2.4】 输入两个数分别赋给变量i和j,再将这两个数分别输出。

   本实例流程图可以采用顺序结构来实现,如图所示。

选择结构也叫分支结构,如图所示

选择结构中必须包含一个判断框。图中所代表的含义是根据给定的条件p是否成立选择执行A框或者是B框。

下图所代表的含义是根据给定的条件P进行判断,如果条件成立则执行A框,否则什么也不做。

在循环结构中,反复地执行一系列操作,直到条件不成立时才终止循环。按照判断条件出现的位置,可将循环结构分为当型循环结构和直到型循环结构。

当型循环是先判断条件P是否成立,如果成立,则执行A框;执行完A框后,再判断条件P是否成立,如果成立,接着再执行A框;如此反复,直到条件P不成立为止,此时不执行A框,跳出循环。

直到型循环是先执行A框,然后判断条件P是否成立,如果条件P成立则再执行A;然后判断条件P是否成立,如果成立,接着再执行A框;如此反复,直到条件P不成立,此时不执行A框,跳出循环。
N-S流程图

N-S图是另一种算法表示法,是由美国人I.Nassi和B.Shneiderman共同提出的,其根据是:既然任何算法都是由前面介绍的3种结构组成,则各基本结构之间的流程线就是多余的,因此去掉了所有的流程线,将全部的算法写在一个矩形框内。N-S图也是算法的一种结构化描述方法,同样也有3种基本结构,下面分别进行介绍:

顺序结构的N-S流程图

选择结构的N-S流程图

当型循环的N-S流程图

直到型循环的N-S流程图

【实例2.7】 从键盘中输入一个数n,求n!。

该程序流程图如图所示。

【实例2.8】 求两个数a和b的最大公约数。流程图如图所示:

N-S流程图如图所示:

算法举例

目前,算法的应用非常广泛,常用的算法包括递推算法,递归算法,穷举算法,贪婪算法,分治算法,动态规划算法和迭代算法等多种。

1、递推算法
2、递归算法
3、穷举算法
4、贪婪算法
5、分治算法
6、动态规划算法
7、迭代算法

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200