結合OJ及競賽的算法設計與分析課程教學實踐

時慧琨

摘要：針對算法設計與分析課程教學中教學以講授為主、學生缺乏實踐機會及實踐脫離應用實際的問題，從在線測試（OJ）系統建設、實踐團隊組織、教學活動開展和競賽組織參與等方面，詳細闡述了在教學過程中結合OJ以及競賽開展課程教學的實踐模式，激發學生學習主動性，引導培養學生分析問題，解決問題能力及團隊合作能力，提高教學效果。

關鍵詞：算法設計與分析;OJ;教學實踐

中圖分類號：G642? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）10-0149-03

Abstract：In the teaching of algorithm design and analysis course， there are some problems such as too many theoretical teaching， lack of practical opportunities and practice divorced from real application， etc. This paper elaborates on the practical mode of combining online judge（OJ）system and competitions in the teaching process from several aspects include OJ system construction， practice team organization， teaching activities development and competition organization participation. Practices proved these measures can stimulate students' learning initiative， guide and cultivate students' ability of analyzing， problem solving and team working， so as to improve the teaching effect.

Keywords：AlgorithmDesignandAnalysis;OJ;teaching practice

1算法設計與分析課程

算法設計與分析課程是高校計算機專業學生的一門專業必修課，該課程主要學習算法設計和算法分析的基本理論及方法。通過課程的學習，掌握算法設計的一般技術，能夠對給定的問題進行分析，建立數學模型，設計解決問題的算法，并進而將其轉換為程序。學生同時也要能夠從時間和空間角度對算法的性能進行分析，選擇合適的算法設計方法以高效的方式解決問題，培養學生分析問題、解決問題的能力及編程實踐能力和創新能力。

算法設計與分析課程直接以用計算機技術解決實際問題為教學目標。利用計算機技術解決問題和其他解決問題的方法不同，在解決問題時并不是針對數據實例直接處理，而是要分析問題的本質特性，建立問題求解模型，設計問題求解的步驟或算法，并開發程序，程序由計算機執行并得到結果。開發的程序要求能夠對問題的各種輸入都得到正確的結果，并且程序通過重復執行和復制傳播，從而成倍的提高生產效率。這樣一種解決問題方法的實現要求學生具備更高的分析、概括和抽象思維能力，同時也要求學生具備較高的設計能力和軟件開發能力。算法設計與分析課程就是一門綜合培養這些能力的課程，課程的教學效果對學生的培養質量有直接的影響。目前社會上對計算機專業學生的需求和學生的實際能力存在一定的脫節，部分就是因為學生分析問題，解決問題能力的缺乏。因此，在算法課程的教學中，研究如何提高培養質量，提高學生的分析能力、實踐能力和創新能力非常重要。

2程序設計競賽及OJ系統

程序設計類競賽中最早、最有名的是ACM-ICPC（ACM國際大學生程序設計競賽），競賽歷史最早可以追溯到1970年，是一項旨在展示大學生創新能力、團隊精神、分析、解決問題以及編程能力的年度競賽。2018年，來自全球6大洲，111個國家，3098所大學的5萬多名選手參加了比賽。這一比賽采用3人團隊合作利用一臺計算機解題的比賽機制，自出現以來，在國際上獲得了廣泛的影響，國內也出現了采用類似機制的各類程序設計比賽，例如CCPC中國大學生程序設計競賽以及各省教育廳組織的程序設計競賽等。另一方面，因特網上出現了各類的Online Judge系統（OJ），這是一種模擬ICPC機制的在線判題系統。常見的OJ系統包括POJ、ZOJ、HDOJ、Vijos、USACO等。一些OJ系統的源碼，例如HUSTOJ等也在因特網上公開，自主開發的難度也不大，這也大大促進了OJ系統的普及，為廣大師生的編程練習提供了絕佳的平臺。

3 結合OJ及競賽的算法設計與分析課程教學措施

OJ作為一個在線測試及實踐平臺，內部包含大量練習，可以提供給學生內容和難度各異的練習機會。學生可以在OJ系統中針對每一個任務進行分析和編程，并提交代碼，OJ系統用內置的數據進行驗證，并返回“通過”或者錯誤的原因。目前，國內外的各種OJ系統主要用于學生練習和比賽，并沒有和教學緊密聯系。如何結合OJ系統以及程序設計競賽，提高學生學習的積極性和主動性，提高算法設計與分析課程教學的效果，在如下幾個方面給出建議，供大家參考：

3.1 OJ系統的建設

目前已有的各種OJ系統主要是針對競賽及較高水平學生學習需求設立，在題目編排、難度劃分上并不適合用于教學，缺乏層次性和教學的針對性。為此，我們在公開的OJ系統的基礎上，將算法設計與分析以及相關的高級語言程序設計、數據結構等課程的例題和課后習題加入OJ系統中，學生在學習完相應內容后，可以直接在OJ系統中開展練習，由OJ系統進行判定[1]。為了方便大家學習，提供測試數據下載的功能，方便學生進行檢查分析。通過這些練習，為學生掌握課程教學內容提供了實踐機會。同時，將一些競賽材料中的試題及競賽題也輸入到系統中，以滿足學生進一步學習及競賽練習的需求。除此之外，為部分學生開放權限，鼓勵學生在題庫中添加內容，在添加內容時可以指定題目相關的知識點及難度等信息，方便學生在教學過程中根據自己的需要進行選擇。同時，也鼓勵學生注冊國內外其他OJ平臺賬號，并在平臺上開展練習及交流。