天天看點

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 參加算法競賽,可以在平時的練習中養成一題多解的習慣,更多的在算法層下功夫,這樣的習慣會讓你的競賽之路走的更遠。