天天看点

python语言能参加的比赛_用Python 参加USACO竞赛到底靠不靠谱?

python语言能参加的比赛_用Python 参加USACO竞赛到底靠不靠谱?

最近几个准备参加 USACO 竞赛的学生,在向我咨询应该如何学习。他们原来都是学习Python 语言的, 本打算基于Python 语言继续深入学习算法和数据结构,但是不少人告诉他们,使用Python 语言考个银牌没有问题,但是想要考金牌和白金就会碰到瓶颈,毕竟Python 是解释性语言,速度比较慢,在执行时间上比较吃亏。 但如果不使用Python的话,就意味着要学习一种新的语言,这需要花费更多的时间在编程语言层面,并且Python是人工智能领域的王者语言,一旦放弃了Python 语言,今后想要转向人工智能,还要再重新把这门语言熟悉起来。因此,他们就是想确定清楚使用Python 语言参加USACO 竞赛到底靠不靠谱?

众所周知,USACO 竞赛是支持多种语言的,分别是 C++、C、Python、Java、Pascal,根据历届的数据统计,使用 C++ 语言的人数是最多的,其次是 Java,这两个语言占领了将近80% 的份额,Pascal 和C 语言基本上都已经无人问津了,Python 这两年一直处于上升期,使用的人员越来越多。

按照正常的逻辑去理解的话,既然 USACO 允许使用这几门语言参加竞赛,那么相信不管使用哪种语言都是能够完成任务的。在USACO 竞赛中,会对程序的执行时间做限制,为了弥补不同语言执行效率上的差异,同样的一道题目,给Java 和 Python 语言的限定时间会比C++ 要长一些,例如对于C++来说,大部分题目都是要求要在一秒内运行完毕,给Python 的限定时间就是二秒。

但不得不承认的是,Python 语言的运行效率和C++ 确实无法比拟,C++ 的效率和 C语言类似,非常接近 汇编语言,使用这种语言可以灵活的操作很多底层的命令,这带来了极大的效率提升,但如果没有使用好,也容易出现错误,例如指针操作就很容易引起崩溃。Python 语言把这些风险全都屏蔽掉了,它提供了更高级,更安全的环境,但带来的代价就是执行效率上会降低。我们来看一个案例,这是一道 USACO Training 的题目:

python语言能参加的比赛_用Python 参加USACO竞赛到底靠不靠谱?

这道题目最简单的解题思路就是暴力求解法,把所有的可能都罗列枚举出来进行比较,但这种算法在时间复杂性上没有办法达到要求,题目中给出的是在5秒时间内完成。

一种升级的做法就是预先计算bisquares 集合,然后以空间换时间,保存在125000 的数组中,序列的增长步长从 1 开始不断增加,看看什么样的组合是满足条件的,把符合的序列保存在结果中。 **这种方法使用 C++ 语言实现后,是能够达到时间要求的,但是同样的算法,使用Python 语言实现,就无法在5 秒内完成。**

对于使用Python语言的开发者来说,就需要在算法上更进一步,继续过滤掉一些不太可能的组合,使得尝试的选项更少,这样才能在 5秒内完成任务。这道题目官方给出了一个Python 实现,其算法方面更加精巧,能够在指定时间完成,有兴趣的同学可以去看看官方的解析。

从上面的例子大家可以看出,当你决定使用Python 语言的时候,在平时的训练和最终比赛中,会碰到同样的算法,但是由于语言效率低,而无法完成任务的情况,这就需要你在算法层面上进行更加深入的思考,找到一个更加高效的解决办法。

看上去如果使用Python,你可能需要在算法层面付出更多的努力,但这未尝不是一件好事,它可以帮助你养成一种习惯,一种对于算法学习来说非常重要的思维习惯—— 一题多解。一题多解 是很多高级竞赛教练总结出来的,对学生算法提升非常重要的一种练习方法。

对于使用 Python 语言的竞赛选手,既然知道语言的执行效率低一些,那就会更加主动的养成一种习惯,那就是拿到一道题目后,不仅仅是想着如何做出来,而是要思考还有什么更简便的方法可以进行解答,这种思维一旦形成习惯,很容易帮助选手在算法层面形成优势。而竞赛的核心目标就是考核这种算法思维,到了顶级的竞赛,例如白金级别,它其实就是通过时间的限定,要求你找到更优质的算法,如果你在训练中一直保持着一题多解的习惯,保持着寻找更高效算法的思维,那么势必是占有优势的。

综上大家可以了解到,对于USACO 竞赛来说,Python 既然是被认可的一种编程语言,那么使用这种编程语言一定是可以完成任务的。当然在高阶的比赛中,会对执行时间有限定,Python 相比于C++ 执行会慢一些,但竞赛给予Python 的限定时间也会长一些,这样就做了一个很好的弥补。如果准备使用Python 参加算法竞赛,可以在平时的练习中养成一题多解的习惯,更多的在算法层下功夫,这样的习惯会让你的竞赛之路走的更远。