挑戰(zhàn)編程

前言

不管對初出茅廬的新人還是身經(jīng)百戰(zhàn)的老手，用“挑戰(zhàn)”一詞形容程序設(shè)計競賽是再合適不過的了?？釔劬幊痰娜藗兺矚g挑戰(zhàn)，但大多數(shù)程序員對各種程序設(shè)計競賽卻是“敬而遠之”，為什么會這樣呢？原因在于，學(xué)習(xí)編程語言和軟件開發(fā)的知識只是接受這些挑戰(zhàn)的必要而非充分條件。要想在程序設(shè)計競賽中脫穎而出，還需要更多的知識和技能。而這些知識和技能，卻是很難在傳統(tǒng)的課堂和教科書中學(xué)到的。本書的目標讀者便是那些已經(jīng)具備初步的編程技能，對程序設(shè)計競賽充滿好奇，希望有機會武裝自己、接受編程挑戰(zhàn)的人，以及他們的老師和教練（甚至父母）。即使不參加任何競賽，從本書的編程挑戰(zhàn)中學(xué)到的東西，也會對程序員的職業(yè)生涯產(chǎn)生重要影響，更不用說這些挑戰(zhàn)本身就是充滿樂趣、引人入勝的。本書文字精練、通俗易懂。盡管每一章都涉及一個不同的領(lǐng)域，但篇幅卻短得甚至可以一口氣讀完。另外，所有題目均附有難度、流行度等客觀評價系數(shù)，并可以在線提交。寫出程序并不意味著完善的解決了難題，只有通過了評測系統(tǒng)的嚴格把關(guān)才能讓人信服。全書由劉汝佳主譯，并得到王希、楊銳、尹淳興、邱前皓等的大力協(xié)助。感謝兩位作者算法大師Steven s.Skiena教授和在線評測系統(tǒng)uVaOJ的創(chuàng)立者Miguel A.Revilla教授邀請譯者完成本書的翻譯工作，提供了書的源程序和插圖，并討論書中的一些細節(jié)；感謝清華大學(xué)出版社的龍放銘編輯，他對工作認真負責的態(tài)度和嚴謹?shù)目茖W(xué)作風(fēng)令人欽佩。盡管我們付出了許多努力，但譯文中難免有翻譯不當之處，敬請批評指正。

內(nèi)容概要

本書分為14章，分別介紹在線評測系統(tǒng)的基本使用方法、數(shù)據(jù)結(jié)構(gòu)、字符串、排序、算術(shù)與代數(shù)、組合數(shù)學(xué)、數(shù)論、回溯法、圖遍歷、圖算法、動態(tài)規(guī)劃、網(wǎng)格、幾何，以及計算幾何，并在附錄中介紹了一些著名的程序設(shè)計競賽以及相應(yīng)的備賽建議與比賽技巧。每章的正文用十余頁的篇幅覆蓋了該領(lǐng)域最核心的概念和算法，然后給出八道可在線提交的完整編程挑戰(zhàn)題目供讀者練習(xí)。    全書內(nèi)容緊湊、信息量大，是各類程序設(shè)計競賽的選手與教練不可多得的參考書。

作者簡介

Steven S.Skiena是美國Stony Brook大學(xué)計算機教授，研究方向包括圖、串和幾何算法的設(shè)計和應(yīng)用(尤其是生物方面)。
    他曾獲ONR青年研究員獎和IEEE計算機科學(xué)與工程本科教學(xué)獎，并著有四本書籍，包括“The Algorithm Design Manual”和“Calculated Bets：Computers，Gambl

書籍目錄

譯者序前言第1章　入門  1.1　初識自動評測系統(tǒng)    1.1.1　評測系統(tǒng)反饋  1.2　挑選你的武器    1.2.1　程序設(shè)計語言    1.2.2　如何閱讀本書的程序    1.2.3　標準輸入輸出  1.3　編程提示  1.4　基本數(shù)據(jù)類型  1.5　關(guān)于習(xí)題  1.6　習(xí)題    1.6.1　3n+1問題（3n+l Problem）    1.6.2　掃雷（Minesweeper）    1.6.3　旅行（The Trip）    1.6.4　液晶顯示屏（LC～Display）    1.6.5　圖形化編輯器（Graphical Editor）    1.6.6　解釋器（Interpreter）    1.6.7　將軍fCheck the Checkl    1.6.8　澳大利亞投票（Australian Voting）  1.7　提示  1.8　注解第2章　數(shù)據(jù)結(jié)構(gòu)  2.1　基本數(shù)據(jù)結(jié)構(gòu)    2.1.1　棧    2.1.2　隊列    2.1.3　字典    2.1.4　優(yōu)先隊列    2.1.5　集合  2.2　庫函數(shù)    2.2.1　C++標準模板庫  2.3　程序設(shè)計實例：紙牌大戰(zhàn)  2.4　準備行動  2.5　字符串輸入輸出  2.6　贏得戰(zhàn)爭  2.7　測試與調(diào)試  2.8　習(xí)題    2.8.1　快樂的跳躍者（Jolly Jumper）    2.8.2　撲克牌型（Poker Hands）    2.8.3　罷工（Hartals）    2.8.4　解密（Crypt Kicker）    2.8.5　完美洗牌術(shù)（Stack’em Up）    2.8.6　ErdSs數(shù)（ErdSs Numbersl    2.8.7　比賽記分板（Contest Scoreboard）    2.8.8　Yahtzee游戲（Yahtzee）  2.9　習(xí)題  2.10　注解第3章　字符串    3.1　字符編碼    3.2　字符串的表示    3.3　程序設(shè)計實例：公司更名    3.4　模式查找    3.5　字符串操作    3.6　程序的完成    3.7　字符串庫函數(shù)    3.8　習(xí)題    3.8.1　WERTYU鍵盤fWERTYU）    3.8.2　尋找單詞（Where’s Waldorf?）    3.8.3　公共排列（Common Permutation）    3.8.4　解密II（Crypt Kicker II）    3.8.5　自動評測腳本（Automated Judge Script）    3.8.6　文件碎片（File Fragmentation）    3.8.7　Doublet序列fDoublets）　……第4章　排序第5章　算術(shù)與代數(shù)第6章　組合數(shù)學(xué)第7章　數(shù)論第8章　回溯法第9章　圖遍歷第10章　圖算法第11章　動態(tài)規(guī)劃第12章　網(wǎng)格第13章　幾何第14章　計算幾何附錄A參考文獻

章節(jié)摘錄

插圖：第2章數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是復(fù)雜算法的核心。數(shù)據(jù)結(jié)構(gòu)的選擇會對算法實現(xiàn)的復(fù)雜性產(chǎn)生巨大的影響。選擇了正確的數(shù)據(jù)結(jié)構(gòu)，編程會十分容易；選擇了錯誤的數(shù)據(jù)結(jié)構(gòu)，則需要大量的時間和代碼量作為決策失誤的代價。在本章中，你將復(fù)習(xí)到一些每個程序員都應(yīng)熟悉的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。我們將以一個孩子們喜歡的撲克牌游戲作為背景展開討論。很多經(jīng)典的編程題目都是以游戲為背景的。幾乎所有人在初學(xué)編程的課程中都會接觸到漢諾塔（HanoiTower）、騎士周游、八皇后這樣的游戲。2.1 基本數(shù)據(jù)結(jié)構(gòu)我們首先介紹棧（stack）、隊列（queue）、字典（dictionaries）、優(yōu)先隊列（priorityqueues）、集合（sets）等最重要的數(shù)據(jù)結(jié)構(gòu)的抽象操作（abstractoperations），接下來簡單描述從頭實現(xiàn)這些操作的最簡單的方法。請注意，c++和Java這樣的現(xiàn)代面向?qū)ο蟪绦蛟O(shè)計語言都已經(jīng)在它們的標準庫中實現(xiàn)了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。我們將在2.2 節(jié)中簡單地介紹它們。每個程序員都應(yīng)該花一些時間來熟悉這些數(shù)據(jù)結(jié)構(gòu)，而不是每次都從頭實現(xiàn)。當你很好地熟悉了這些庫的使用方法后，在閱讀本節(jié)時便可專注于這些數(shù)據(jù)結(jié)構(gòu)所擅長的領(lǐng)域而非實現(xiàn)細節(jié)。

編輯推薦

《挑戰(zhàn)編程:程序設(shè)計競賽訓(xùn)練手冊》是由清華大學(xué)出版社出版的。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    挑戰(zhàn)編程 PDF格式下載

---