c++

10岁的小朋友开始用C挑战ldqu

发布时间:2022/5/18 15:22:06   点击数:

相信很多家长并不是很了解算法是什么,经常会听到家长们感叹:“小学生学算法?别闹了,他们学不懂。”但其实,算法并没有我们想象的那样高深莫测,甚至连孩子也是可以接触算法的。10岁的孩子就开始学习斐波那契算法。如果你也想让孩子学习信息奥赛,不妨先了解一下什么是算法。

几个例子

有一次,一个网友通过邮件问我:“你写的都是小儿科的东西,几十行代码就能搞定,能不能整一点高深的算法?”我反问他什么是他所理解的高深的算法,他答复说:“像遗传算法、蚁群算法之类的。”于是我给了他一个遗传算法求解0-1背包问题的例子,并告诉他,这也就是几十行代码的算法,怎么理解成是高深的算法?他刚开始不承认这是遗传算法,直到我给了他DenisCormier公开在北卡罗来纳州立大学服务器上的遗传算法的源代码后,他才相信他一直认为深不可测的遗传算法的原理原来是这么简单。

还有一个网友直言我写的“用三个水桶等分8升水”之类的问题根本就称不上算法,他认为像“深蓝”那样的人工智能才算是算法。我告诉他计算机下棋的基本理论就是博弈树,或者再加一个专家系统。但是他认为博弈树也是很高深的算法,于是我给了他一个井字棋游戏,并告诉他,这就是博弈树搜索算法,非常智能,你绝对战胜不了它(因为井字棋游戏很简单,这个算法会把所有的状态都搜索完)。我相信他一定很震惊,因为这个算法也不超过行代码。

对于上面提到的例子,我觉得主要原因在于大家对算法的理解有差异,很多人对算法的理解太片面,很多人觉得只有名字里包含“XX算法”之类的东西才是算法。而我认为算法的本质是解决问题,只要是能解决问题的代码就是算法。在讨论程序员与算法这个问题之前,我们先探讨一个最基本的问题:什么是算法。

什么是算法

《算法导论》一书将算法(algorithm)描述为定义良好的计算过程,它取一个或一组值作为输入,并产生一个或一组值作为输出。Knuth在《计算机程序设计艺术》一书中将算法描述为从一个步骤开始,按照既定的顺序执行完所有的步骤,最终结束(得到结果)的一个过程。Weiss在《数据结构与算法分析》一书中将算法描述为一系列的计算步骤,将输入数据转换成输出的结果。

算法的特征

虽然没有被普遍接受的“算法”的正式定义,但是各种著作中对算法的基本要素或基本特征的定义都是明确的,Knuth总结了算法的四大特征。

01

确定性

算法的每个步骤都是明确的,对结果的预期也是确定的。

02

有穷性

算法必须是由有限个步骤组成的过程,步骤的数量可能是几个,也可能是几百万个,但是必须有一个确定的结束条件。

03

可行性

一般来说,我们期望算法最后得出的是正确的结果,这意味着算法中的每一个步骤都是可行的。只要有一个步骤不可行,算法就是失败的,或者不能被称为某种算法。

04

输入与输出

算法总是要解决特定的问题,问题来源就是算法的输入,期望的结果就是算法的输出。没有输入的算法是没有意义的,没有输出的算法是没有用的。

得出结论

算法需要一定的数学基础,但是没有任何文献资料将算法限定于只解决数学问题。有些人将贪婪法、分治法、动态规划法、线性规划法、搜索和枚举(包括穷尽枚举)等方法理解为算法,其实这些只是设计算法常用的设计模式(Knuth称之为设计范式)。同样,计算机程序只是算法的一种存在形式,伪代码、流程图、各种符号和控制表格也是常见的算法展示形式。而顺序执行、并行执行(包括分布式计算)、递归方法和迭代方法则是常用的算法实现方法。

综合以上分析和引述,本人将算法定义为:算法是为解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤,这些操作步骤将问题描述的输入数据逐步处理、转换,并最后得到一个确定的结果。使用“精心设计”一词,是因为我将算法的设计过程理解为人类头脑中知识、经验激烈碰撞的过程,将算法理解为最终“小宇宙爆发”一般得到的智力结果。

算法有什么用

我要说的是,大多数程序员并不需要知道各种专业领域里的算法,但是你要会设计能够解决你面临问题的算法。一些领域内的经典问题,在前人的努力之下都有了高效的算法实现。但是更多情况下,你所面临的问题并没有现成的算法实现,需要程序员具有创新的精神。

算法设计需要具备很好的数学基础,但数学并不是唯一需要的知识,计算机技术的一些基础学科(比如数据结构)也是必需的知识,有人说:程序=算法+数据结构,这个虽然不完全正确,但是提到了计算机程序最重要的两点,那就是算法和数据结构。算法和数据结构永远是紧密联系在一起的,算法可以理解为解决问题的思想,这是程序中最具有创造性的部分,也是一个程序有别于另一个程序的关键点,而数据结构就是这种思想的载体。

再次重申一遍,我和大多数人一样,并不是要求每个程序员都精通各种算法。大多数程序员可能在整个职业生涯中都不会遇到像ACM(AssociationforComputingMachinery)组织的国际大学生程序设计竞赛中的问题,但是说用不到数据结构和算法则是不可想象的。说数据结构和算法没用的人是因为他们用不到,用不到的原因是他们想不到,而想不到的原因是他们不会。请息怒,我不是要打击任何人,很多情况下确实是因为不会,所以才用不到。

如果要自己解决问题,应该如何解决问题?为什么要自己解决问题?先来回答第一个问题——如何设计算法解决问题?编写计算机程序实现算法,让计算机帮我们解决问题的过程也需要一定的知识和经验。为了让计算机帮我们解决问题,就要设计计算机能理解的算法程序。

设计算法程序的第一步就是要让计算机理解问题是什么。这就需要建立现实问题的数学模型。建模过程就是一个对现实问题的抽象过程,运用逻辑思维能力,抓住问题的主要因素,忽略次要因素。建立数学模型之后,第二个要考虑的问题就是输入输出问题,输入就是将自然语言或人类能够理解的其他表达方式描述的问题转换为数学模型中的数据,输出就是将数学模型中表达的运算结果转换成自然语言或人类能够理解的其他表达方式。最后就是算法的设计,其实就是设计一套对数学模型中的数据的操作和转换步骤,使其能演化出最终的结果。数学模型、输入输出方法和算法步骤是编写计算机算法程序的三大关键因素。

为什么要自己解决问题?爱因斯坦说过:“兴趣是最好的老师。”这就是说,只要一个人对某事物产生兴趣,就会主动去学习、去研究,并在学习和研究的过程中产生愉快的情绪。

我把从算法中体会到的乐趣分成三个层次:初级层次是找到特定的算法解决特定的实际问题,这种乐趣是解决问题后的成就感;中级层次是有些算法本身就是充满乐趣的,搞明白这种算法的原理并写出算法的程序代码,能为自己今后的工作带来便利;高级层次是自己设计算法解决问题,让其他人可以利用你的算法享受到初级层次的乐趣。有时候问题可能是别人没有遇到过的,没有已知的解法,这种情况下只能自己解决问题。这是本书一直强调算法的乐趣的原因。只有体会到乐趣,才有动力去学习和研究,而这种学习和研究的结果是为自己带来正向的激励,为今后的工作带来便利。

摘自:王晓华《算法的乐趣》

算法就在我们身边,孩子学习信息学不是全为了成为程序员,更多的是锻炼计算思维,去解决身边的问题。

预览时标签不可点收录于合集#个上一篇下一篇
转载请注明:http://www.xienasc.com/jbtly/24298.html
------分隔线----------------------------