前言

這是一本關于算法的教程。算法是一系列解決問題的清晰指令，可以說它是程序設計的靈魂。同一問題可用不同的算法解決，而一個算法的質量優劣將影響程序的執行效率。算法分析的目的在于選擇合適算法和改進算法。評價一個算法的好壞主要是通過算法運行的時間長短和占用空間的大小來評估的。對于計算機專業或者愛好計算機的人士來說，無論學習還是工作，或多或少都會應用一些算法的知識。而目前國內外大型互聯網公司在招聘時的筆試和面試都以算法為主。可見，算法的重要性是不言而喻的。

ACM/ICPC（ACM International Collegiate Programming Contest）是一項由美國計算機協會主辦的，旨在展示大學生創新能力、團隊精神和在壓力下編寫程序、分析和解決問題能力的年度競賽。ACM程序設計競賽的題目強調算法的高效性與正確性。參賽選手只有編寫出能夠在規定時間內運行完成若干組數嚴格的測試數據，并且結果全部正確的程序才能得到分數。本書將以ACM程序設計競賽的題目為基礎，介紹一些經典的算法。

本書的目的是將更多對計算機算法感興趣，但又苦于無從入手的讀者帶進程序設計的大門，讓剛邁入大學校門的學生學會使用C++語言解決簡單的問題。本書主要介紹高級數據結構、字符串、動態規劃、圖論、組合數學方面的經典算法，相信當讀者掌握了這些內容之后，會對算法和程序設計有一個新層次的認識，并會產生濃厚的興趣。對于每個算法，本書都有圖文并茂的講解；在每章節的最后，都有針對該部分知識點的例題講解，每道例題都是國內外著名程序在線判題系統中的原題，而且對于每道例題，都會從理解題意開始，詳細講解解題的思路，并附有完整的可以正確通過測試樣例的代碼，供讀者研究學習。除了例題，在每章的最后還有一些練習題供讀者鞏固學到的知識，如果讀者對這些習題仍感覺無從下手，可以參考每道練習題后附帶的思路分析來幫助整理解題思路。

大連理工大學是在全國高校中較早倡導并開展創新創業教育的學校。自1984年以來，學校大力開展以突出創新創業實踐為特色的創新創業教育。1995年，在全國率先成立以學生創新創業教育為主體的教學改革示范區—創新教育實踐中心，開展創新創業教育課程體系、教學內容、教學方法、教學模式等方面的改革，探索與之配套的管理運行機制，將創造性思維與創新方法融入教學實踐中，在課堂教學中樹立“CDIO工程教育”新理念，倡導“做中學”，在實踐環節構建了“個性化、雙渠道、三結合、四層次、多模式”的創新教育實踐教學新體系，取得了一系列成果，在全國高校產生了很大的影響。“創造性思維與創新方法”和“創新教育基礎與實踐（系列）”課程分別被評為國家級精品資源開放課程。“大學生程序設計競賽初級教材”是“創新教育基礎與實踐”系列課程的核心課程，是面向大連理工大學ACM創新實踐班的學生開設的。

此外，本書在撰寫過程中，除了參考文獻和正文中標出的引用來源，還參考了國內外的相關研究成果和網站資源，但沒有一一列出，在此感謝所涉及的所有單位、專家和研究人員。

因編者水平有限，書中的錯誤和不足之處在所難免，歡迎廣大讀者來信批評指正，提出寶貴意見，幫助我們不斷地完善本書。

編　者

2018年12月