HowtoThinkLikeaComputerScientistJavaVers2n

如何像計(jì)算機(jī)科學(xué)家一樣思考

Java版?中文版

如何像計(jì)算機(jī)科學(xué)家一樣思考

Java版/中文版

作者：AllenB.Downey

翻譯：朱珠(Aaron)

E-Mail：aarongo@

文檔版本：CHS_0.1

2004年10月一2005年元月

版權(quán)申明

本文檔由Aaron翻譯制作。

文檔基于GNU自由文檔執(zhí)照(GNUFreeDocumentationLicense)。

您可以自由地復(fù)制和發(fā)送這份文檔，前提是必須保留本申明。

版權(quán)所有?2005Aaron

目錄

第0章前言........................................................I

為什么要寫這本書...............................................1

背后的哲學(xué)觀...................................................1

面向?qū)ο缶幊?Object-orientedprogramming/OOP).........................................2

數(shù)據(jù)結(jié)構(gòu).......................................................3

計(jì)算機(jī)科學(xué)高級(jí)職業(yè)考試.........................................3

FreeBooks!.................................................................................................................3

噢，標(biāo)題！.....................................................4

第1章編程方法論..................................................5

1.1什么是編程語(yǔ)言？...........................................5

1.2什么是程序？...............................................7

1.3什么是程序調(diào)試？...........................................8

1.4形式語(yǔ)言和自然語(yǔ)言........................................10

1.5第一個(gè)程序................................................11

1.6術(shù)語(yǔ)表....................................................12

第2章變量和型別.................................................14

2.1關(guān)于打印的更多內(nèi)容.........................................14

2.2變量......................................................15

2.3賦值......................................................15

2.4打印變量..................................................16

2.5Java關(guān)鍵字................................................17

2.6運(yùn)算符....................................................18

2.7運(yùn)算符優(yōu)先級(jí)..............................................19

2.8字符串運(yùn)算符..............................................19

2.9復(fù)合......................................................19

2.10術(shù)語(yǔ)表...................................................20

第3章方法.......................................................21

3.1浮點(diǎn)數(shù)....................................................21

3.2浮點(diǎn)數(shù)轉(zhuǎn)換為整數(shù)..........................................22

3.3數(shù)學(xué)方法..................................................22

3.4復(fù)合......................................................23

3.5新增方法..................................................24

3.6類和方法..................................................26

如何像計(jì)算機(jī)科學(xué)家一樣思考

3.7多方法程序................................................26

3.8形參和實(shí)參................................................27

3.9堆棧圖....................................................28

3.10多參數(shù)方法...............................................29

3.11帶返回結(jié)果的方法.........................................30

3.12術(shù)語(yǔ)表...................................................30

第4章條件語(yǔ)句和遞歸.............................................31

4.1取模運(yùn)算符................................................31

4.2條件執(zhí)行..................................................31

4.3選擇執(zhí)行..................................................32

4.4鏈?zhǔn)綏l件..................................................33

4.5嵌套條件..................................................33

4.6返回語(yǔ)句..................................................34

4.7型別轉(zhuǎn)換..................................................34

4.8遞歸......................................................35

4.9遞歸方法的堆棧圖..........................................36

4.10約俗和法則...............................................37

4.11術(shù)語(yǔ)表...................................................37

第5章帶返回值的方法.............................................38

5.1返回值....................................................38

5.2程序開發(fā)..................................................39

5.3復(fù)合......................................................42

5.4重載......................................................42

5.5布爾表達(dá)式................................................43

5.6邏輯運(yùn)算符................................................44

5.7布爾方法..................................................45

5.8再談遞歸..................................................45

5.9“掩耳盜鈴”...............................................48

5.10最后一例.................................................48

5.11術(shù)語(yǔ)表...................................................49

第6章迭代.......................................................50

6.1多次賦值..................................................50

6.2迭代......................................................50

6.3while語(yǔ)句.................................................51

6.4表........................................................52

6.5二維表....................................................54

目錄iii

6.6封裝和通用化..............................................55

6.7方法的好處................................................56

6.8再談封裝..................................................56

6.9本地變量..................................................57

6.10再談通用化...............................................57

6.11術(shù)語(yǔ)表...................................................59

第7章字符串及其它...............................................60

7.1向?qū)ο笳{(diào)用方法.............................................60

7.2length方法.................................................61

7.3遍歷......................................................61

7.4運(yùn)行時(shí)錯(cuò)誤................................................62

7.5閱讀文檔..................................................62

7.6indexOf方法...............................................62

7.7循環(huán)和計(jì)數(shù)................................................63

7.8自增1和自減1運(yùn)算符.......................................64

7.9字符算術(shù)運(yùn)算..............................................65

7.10剛性的字符串.............................................66

7.11不可比的字符串...........................................66

7.12術(shù)語(yǔ)表...................................................67

第8章有趣的對(duì)象.................................................68

8.1有趣在哪里................................................68

8.2包........................................................68

8.3Point對(duì)象.................................................68

8.4實(shí)例變量..................................................69

8.5對(duì)象做參數(shù)................................................70

8.6矩形......................................................70

8.7作為返回值的對(duì)象..........................................71

8.8剛性的對(duì)象................................................71

8.9別名......................................................72

8.10null............................................................................................................73

8.11垃圾收集.................................................73

8.12對(duì)象和基本類型...........................................74

8.13術(shù)語(yǔ)表...................................................75

第9章創(chuàng)建對(duì)象...................................................76

9.1類定義與對(duì)象的型別........................................76

9.2Time類...................................................76

iv如何像計(jì)算機(jī)科學(xué)家一樣思考

9.3構(gòu)造器....................................................77

9.4再談構(gòu)造器................................................78

9.5創(chuàng)建新對(duì)象................................................78

9.6打E[1對(duì)象..................................................79

9.7對(duì)象的操作................................................80

9.8純粹函數(shù)..................................................81

9.9修正方法..................................................82

9.10填充方法.................................................83

9.11哪種方法最好.............................................84

9.12遞增開發(fā)vs.規(guī)劃..........................................84

9.13通用化...................................................85

9.14算法.....................................................86

9.15術(shù)語(yǔ)表...................................................86

第10章數(shù)組......................................................88

10.1訪問(wèn)數(shù)組元素.............................................88

10.2拷貝數(shù)組.................................................89

10.3for循環(huán)語(yǔ)句..............................................90

10.4數(shù)組和對(duì)象...............................................91

10.5數(shù)組長(zhǎng)度.................................................91

10.6隨機(jī)數(shù)...................................................91

10.7隨機(jī)數(shù)數(shù)組...............................................92

10.8計(jì)數(shù).....................................................93

10.9矩形圖...................................................94

10.11術(shù)語(yǔ)表..................................................95

第11章對(duì)象的數(shù)組.................................................96

11.1復(fù)合.....................................................96

11.2紙牌對(duì)象—Card...................................................................................96

11.3printCard方法.............................................97

11.4sameCard方法.............................................99

11.5compareCard方法.........................................100

11.6牌的數(shù)組................................................101

11.7printDeck方法............................................102

11.8查找....................................................102

11.9Deck和subdeck.....................................................................................105

11.10術(shù)語(yǔ)表.................................................106

第12章數(shù)組的對(duì)象...............................................107

目錄

12.1Deck類..................................................107

12.2洗牌....................................................108

12.3排序....................................................109

12.4subdeck方法.............................................109

12.5洗牌和發(fā)牌..............................................110

12.6合并排序................................................111

12.7術(shù)語(yǔ)表..................................................113

第13章面向?qū)ο缶幊?............................................114

13.1編程語(yǔ)言和風(fēng)格...........................................114

13.2對(duì)象和類的方法..........................................114

13.3當(dāng)前對(duì)象.................................................114

13.4復(fù)數(shù)....................................................115

13.5復(fù)數(shù)函數(shù).................................................116

13.6另一個(gè)復(fù)數(shù)函數(shù)..........................................116

13.7修飾方法................................................117

13.8toString方法.............................................117

13.9equals方法..............................................118

13.10調(diào)用對(duì)象方法...........................................119

13.11奇怪的錯(cuò)誤..............................................119

13.12繼承...................................................120

13.13可拖動(dòng)的矩形...........................................120

13.14類的層次...............................................121

13.15面向?qū)ο笤O(shè)計(jì)...........................................121

13.16術(shù)語(yǔ)表.................................................122

第14章鏈表.....................................................123

14.1對(duì)象內(nèi)的引用.............................................123

14.2Node類.................................................123

14.3作為容器的鏈表..........................................124

14.4鏈表與遞歸..............................................125

14.5無(wú)窮鏈表................................................126

14.6基本岐義定理............................................127

14.7節(jié)點(diǎn)的方法..............................................128

14.8修改鏈表................................................128

14.9包裝方法和助手方法......................................129

14.10IntList類...............................................129

14.11恒量...................................................131

vi如何像計(jì)算機(jī)科學(xué)家一樣思考

14.12術(shù)語(yǔ)表..................................................131

第15章堆棧.....................................................132

15.1抽象數(shù)據(jù)型別.............................................132

15.2堆棧ADT....................................................132

15.3Java中的Stack對(duì)象.......................................133

15.4包裝類..................................................134

15.5創(chuàng)建包裝對(duì)象............................................134

15.6再談創(chuàng)建包裝對(duì)象........................................135

15.7取值....................................................135

15.8包裝類中的有用方法......................................135

15.9后綴表達(dá)式..............................................136

15.10解析...................................................136

15.11實(shí)現(xiàn)ADT...................................................138

15.12堆棧ADT的數(shù)組實(shí)現(xiàn)....................................138

15.13縮放數(shù)組...............................................139

15.14術(shù)語(yǔ)表.................................................140

第16章隊(duì)列和優(yōu)先隊(duì)列...........................................142

16.1隊(duì)歹1JADT....................................................142

16.2蒙版....................................................143

16.3鏈隊(duì)列..................................................145

16.4循環(huán)緩沖................................................146

16.5優(yōu)先隊(duì)列................................................149

16.6元類....................................................150

16.7優(yōu)先隊(duì)列的數(shù)組實(shí)現(xiàn)......................................150

16.8優(yōu)先隊(duì)列的委托者（client）...................................151

16.9Golfer（高爾夫球手）類...................................152

16.10術(shù)語(yǔ)表.................................................154

第17章樹.......................................................156

17.1樹節(jié)點(diǎn)...................................................156

17.2建立樹..................................................157

17.3遍歷樹..................................................157

17.4表達(dá)式的樹..............................................158

17.5遍歷....................................................158

17.6封裝....................................................159

17.7定義元類................................................160

17.8實(shí)現(xiàn)元類................................................160

目錄vii

17.9Vector..........................................................................................................161

17.10Iterator類...............................................163

17.11Glossary.........................................................................................................163

第18章堆.......................................................165

18.1樹的數(shù)組實(shí)現(xiàn)............................................165

18.2性能分析................................................167

18.3合并排序的分析..........................................169

18.4額外開銷................................................171

18.5優(yōu)先隊(duì)列的實(shí)現(xiàn)..........................................171

18.6堆的定義................................................173

18.7堆的remove方法.........................................173

18.8add方法.................................................175

18.9堆的性能................................................175

18.10堆排序.................................................176

18.11術(shù)語(yǔ)表..................................................177

第19章映射.....................................................178

19.1數(shù)組、向量和映射.........................................178

19.2MapADT.........................................................................................................178

19.3內(nèi)建的HashMap............................................................................................178

19.4一個(gè)向量實(shí)現(xiàn)............................................181

19.5List元類................................................183

19.6HashMap實(shí)現(xiàn)............................................183

19.7哈希函數(shù)................................................184

19.8縮放哈希映射............................................185

19.9哈希表調(diào)整操作的性能....................................185

19.10術(shù)語(yǔ)表.................................................186

第20章霍夫曼編碼...............................................187

20.1長(zhǎng)短編碼.................................................187

20.2頻率表..................................................188

20.3霍夫曼樹................................................188

20.4super方法...............................................190

20.5解碼(Decoding).........................................................................................191

20.6編碼Encoding................................................................................................192

20.7術(shù)語(yǔ)表..................................................192

附錄A程序開發(fā)計(jì)劃..............................................193

附錄B調(diào)試......................................................198

Vlll如何像計(jì)算機(jī)科學(xué)家一樣思考

B.1運(yùn)行時(shí)錯(cuò)誤...............................................198

B.2運(yùn)行時(shí)錯(cuò)誤...............................................200

B.3語(yǔ)義錯(cuò)誤.................................................203

附錄CJava中的輸入/輸出..........................................208

附錄DGraphics類.................................................210

D.lSlate和Graphics對(duì)象.......................................210

D.2對(duì)一個(gè)Graphics對(duì)象調(diào)用方法...............................210

D.3坐標(biāo).....................................................211

D.4未完成的米老鼠...........................................211

D.5其它繪圖命令.............................................213

D.6Slate類214

第。章前言

“當(dāng)我們享受他人的發(fā)明帶來(lái)的巨大便利時(shí)，也應(yīng)該很樂意提供一個(gè)用自己的發(fā)

明來(lái)為別人服務(wù)的機(jī)會(huì)，而且我們應(yīng)該慷慨地免費(fèi)地這樣做?！?/p>

——本杰明?富蘭克林

引自埃德蒙德?s?摩根著《本杰明?富蘭克林傳》

為什么要寫這本書

這是我在1999年于Colby大學(xué)任教時(shí)所著一書的第四版。其時(shí)我任教一門

用Java語(yǔ)言講解的計(jì)算機(jī)科學(xué)課程，但是苦于找不到自己喜歡的教科書。首先，

那些教材太大部頭了！即使我想讓學(xué)生讀這些動(dòng)輒800多頁(yè)密密麻麻的技術(shù)手

冊(cè)，他們也辦不到。而且我也不想讓他們那么做。這些資料大多太過(guò)專注于Java

語(yǔ)言的特定細(xì)節(jié)和…些到了期末就會(huì)被學(xué)生忘得干干凈凈的類庫(kù)，這些東西把我

真正想找的材料搞的撲朔迷離。

另外一個(gè)問(wèn)題是，對(duì)于面向?qū)ο蟪绦蛟O(shè)計(jì)的介紹太草率，使得很多在其它部

分學(xué)得很好的學(xué)生一講到“對(duì)象”就碰壁，甚至不管在開學(xué)、中間還是期末同樣

如此。

于是我開始了本書的編寫，十三天時(shí)間里每天寫一章，第十四天進(jìn)行編輯校

訂，然后把書送去復(fù)印裝訂。在開課第一天把書發(fā)到學(xué)生手里的時(shí)候，我告訴他

們希望他們一個(gè)星期讀一章，換句話說(shuō)，他們的閱讀速度應(yīng)該是我寫作速度的

l/7o

背后的哲學(xué)觀

下面是一些指導(dǎo)本書編寫并使之得以別具一格的主要觀念：

?詞匯表很重要。學(xué)生必須能夠談?wù)摗俺绦颉辈⑶颐靼资窃谡f(shuō)什么。我力

圖介紹盡量少的術(shù)語(yǔ)；第一次遇到一個(gè)術(shù)語(yǔ)就進(jìn)行精心定義；每一章后面都專門

列出新詞表。在教學(xué)中，隨堂測(cè)驗(yàn)和考試都有詞匯測(cè)試題，要求學(xué)生用適當(dāng)?shù)脑~

進(jìn)行簡(jiǎn)要回答。

?為了編寫程序，學(xué)生要懂得算法(algorithm)、了解編程語(yǔ)言，而且還要

有調(diào)試程序的能力才行。太多的書遺漏了調(diào)試的知識(shí)。而這本書有一個(gè)關(guān)于調(diào)試

的附錄和一個(gè)關(guān)于程序開發(fā)(幫助避免進(jìn)行不必要調(diào)試)的附錄。我建議盡早閱

讀并且經(jīng)?；仡欉@些材料。

?一些概念需要時(shí)間來(lái)了解。本書中一些較難以理解的概念比如遞歸，反

2如何像計(jì)算機(jī)科學(xué)家?樣思考

復(fù)出現(xiàn)了數(shù)次。通過(guò)反復(fù)提到這些概念，讓學(xué)生有機(jī)會(huì)復(fù)習(xí)鞏固，或者是如果

第一次漏過(guò)了也還有機(jī)會(huì)可以補(bǔ)上來(lái)。

?力圖用最少的Java語(yǔ)句實(shí)現(xiàn)最強(qiáng)大的編程能力。本書的目的是傳授編程

和計(jì)算機(jī)科學(xué)的一些引導(dǎo)性概念，而不是講授Java語(yǔ)言本身。我有意不講一些

語(yǔ)言特性，例如并非必要的swifM語(yǔ)句，還有大多數(shù)類庫(kù)，特別是像AWT這

樣保持快速更新而且極可能被取代的類庫(kù)。

采取風(fēng)格簡(jiǎn)約的寫作方法有很多優(yōu)點(diǎn)。不包括練習(xí)的話每章大約十頁(yè)。上

課討論之前要求學(xué)生先通讀一遍該章——他們樂意這樣做并且對(duì)課本理解的很

充分。這些準(zhǔn)備讓課堂上有充分的時(shí)間討論較難的材料，包括課堂作業(yè)，還有

不在課本中的補(bǔ)充話題。

當(dāng)然，簡(jiǎn)約并非十全十美。在這里沒有多少本質(zhì)上有趣的東西，我所用的

大多數(shù)例子主要是為了演示一利語(yǔ)言結(jié)構(gòu)的最基本用法，因此大多數(shù)練習(xí)潛心

于字符串操作和數(shù)學(xué)概念。我認(rèn)為這些東西有一部分還是很有趣，但是更多能

讓學(xué)生對(duì)計(jì)算機(jī)科學(xué)產(chǎn)生濃烈興趣的東西諸如圖形處理、聲音處理和網(wǎng)絡(luò)應(yīng)用

等等，卻被一筆帶過(guò)了。

原因在于，很多更加有趣的內(nèi)容卻包含了大量的細(xì)節(jié)而不是更多的概念。

從教育學(xué)的角度來(lái)看，這意味著不值得投入更多的注意力。所以，在討學(xué)生喜

歡的材料和智力含量更高的材料之間采取了折衷的選擇。我希望使用這本書的

時(shí)候師可以自己找到對(duì)他所教班級(jí)學(xué)生來(lái)說(shuō)最好的平衡點(diǎn)。為了幫助教學(xué)，這

本書有一個(gè)涵蓋了圖形、鍵盤輸入輸出的附錄。

面向?qū)ο缶幊?Object-orientedprogramming/OOP)

有些書一上來(lái)就介紹，，對(duì)象，，；另一些則是一步一步慢慢來(lái)，逐漸地建立面

向?qū)ο蟮娘L(fēng)格。這本書大概可以劃入極端“對(duì)象靠后”的路線。

Java中很多面向?qū)ο蟮奶匦允堑玫揭酝恼Z(yǔ)言啟發(fā)，這些結(jié)構(gòu)是有歷史可

溯的。如果學(xué)生不知道這些特性是為了解決問(wèn)題什么問(wèn)題而設(shè)計(jì)的，很多內(nèi)容

就難以向他們解釋清楚。

當(dāng)然，阻礙面向?qū)ο缶幊探^非目的；恰好相反，為了能盡快的引入OOP,

我盡量做到只介紹一次概念，第一次就解釋清晰，所以在增加新概念之前讓學(xué)

生對(duì)每個(gè)已引入的概念都專門練習(xí)。這樣在第13個(gè)概念上終于引入了面向?qū)ο?/p>

編程。

第0章前言3

數(shù)據(jù)結(jié)構(gòu)

在2000年秋季，我執(zhí)教了第二門引導(dǎo)課程——數(shù)據(jù)結(jié)構(gòu)，于是本書新增了

如下兒章：線性表、堆棧、樹和散列表。

這些新增的每一章給出了一種數(shù)據(jù)結(jié)構(gòu)的定義、至少一種用到了該數(shù)據(jù)結(jié)

構(gòu)的算法，以及至少一種實(shí)現(xiàn)版本。多數(shù)情況下當(dāng)然也有一個(gè)用標(biāo)準(zhǔn)的java.utils

包實(shí)現(xiàn)的版本。這樣一來(lái)，教師就能選擇是否討論實(shí)現(xiàn)版本或者讓學(xué)生做一個(gè)

練習(xí)來(lái)實(shí)現(xiàn)。大多數(shù)時(shí)候我都同時(shí)用了一個(gè)java.utils包的實(shí)現(xiàn)版本來(lái)描述一種

數(shù)據(jù)結(jié)構(gòu)和對(duì)應(yīng)的接口。

計(jì)算機(jī)科學(xué)高級(jí)職業(yè)考試

在2001年夏季，我和緬因州立數(shù)理學(xué)院的老師們合作編寫一本幫助學(xué)生準(zhǔn)

備計(jì)算機(jī)科學(xué)高級(jí)職業(yè)考試(TheComputerScienceAdvancedPlacementExam

/CSAPE)的Java版本教材，而當(dāng)時(shí)的教材用的是C++。翻譯工作的進(jìn)展非常

快，因?yàn)橐坏╅_始，我就發(fā)現(xiàn)我寫這本書所選用的材料跟考試大綱簡(jiǎn)直太吻合

了。

自然而然地，當(dāng)校方宣布考試改為采用Java語(yǔ)言，我也制定了計(jì)劃要更新

這本書中相關(guān)的Java的內(nèi)容。因?yàn)榭戳薈SAPE的考綱，我發(fā)現(xiàn)它對(duì)Java的介

紹很全而且跟我的選擇范圍非常相似。

2003年1月，我完成了本書第四版，做了如下修改：

?新增了一章涵蓋霍夫曼編碼。

?重寫了我發(fā)現(xiàn)有疑問(wèn)的幾個(gè)小節(jié)，包括向OOP的過(guò)渡和關(guān)于堆棧的討

論等。

?增強(qiáng)了調(diào)試和程序開發(fā)的附錄。

?新增了一些小節(jié)以提高對(duì)CSAPE考綱的覆蓋率。

?收集了我在曾經(jīng)執(zhí)教的班級(jí)用過(guò)的練習(xí)、檢測(cè)和考試問(wèn)題，放在相應(yīng)章

節(jié)的后面；同時(shí)設(shè)計(jì)了一些意在幫助準(zhǔn)備CSAPE的問(wèn)題。

FreeBooks!

從一開始，這本書和其后續(xù)版本都遵照GNU自由文檔執(zhí)照的形式存在。

讀者可以免費(fèi)的下載這本書的各種格式文檔，并打印出來(lái)或者直接在屏幕上閱

4如何像計(jì)算機(jī)科學(xué)家?樣思考

讀；教師可以自由的用打印機(jī)把本書打印出來(lái)，并且根據(jù)需要復(fù)印任意數(shù)量。

而最重要的是，任何人都可以根據(jù)需要自由的修改本書。你可以下載LaTeX源

代碼，然后添加、刪除、編輯或者重排其中的材料］以達(dá)到使本書最大程度為

你或你執(zhí)教的班級(jí)學(xué)生所用的目的。

有人已經(jīng)把本書翻譯成了其它計(jì)算機(jī)語(yǔ)言（包括Python和Eiffel）和其它

自然語(yǔ)言（包括西班牙語(yǔ)和法語(yǔ)），很多這樣的衍生版本都遵循GNU自由文檔

執(zhí)照而存在。

這種發(fā)行辦法有很多優(yōu)點(diǎn)，但是也有一個(gè)不利的地方：所有這些書從來(lái)沒

有得到正式的編排和校對(duì)。在開源軟件的影響下，我已經(jīng)習(xí)慣于盡早的發(fā)布然

后經(jīng)常更新本書。我盡全力把錯(cuò)誤減少，但是我更依賴讀者幫我找出問(wèn)題。

一直以來(lái)反響都非常好。我?guī)缀趺刻於际盏阶x過(guò)并且非常喜歡本書的人們

不辭繁瑣的給我發(fā)送“bug報(bào)告”。一般說(shuō)來(lái)我都能立即改正錯(cuò)誤并且發(fā)布更新

后的版本。每次我有時(shí)間進(jìn)行修訂，或者當(dāng)讀者不惜時(shí)間給我發(fā)回反饋的時(shí)候,

我感到這本書是一個(gè)不斷進(jìn)步的作品。

噢，標(biāo)題！

我有一大堆關(guān)于本書標(biāo)題的傷心往事，不是每個(gè)人都明白——基本上——

那是一個(gè)笑話。閱讀本書也許不會(huì)真的讓你學(xué)會(huì)像計(jì)算機(jī)科學(xué)家那樣思考。那

需要時(shí)間、經(jīng)驗(yàn)，也許在加上一些課程。

但是標(biāo)題中有一個(gè)核心事實(shí)：這本書不是專門講Java的，對(duì)具體語(yǔ)言的使

用只是編程工作的一部分。如果這本書是成功的，它就是寫思考方法的。計(jì)算

機(jī)科學(xué)家們自有一套問(wèn)題求解（problem-solving）的方法，一種精巧解決問(wèn)題

的路子，那是獨(dú)一無(wú)二的，而又是通用的、強(qiáng)大的法子。我希望這本書能給你

關(guān)于上述方法到底是什么樣子的一個(gè)認(rèn)識(shí)，最后使你從某種程度上發(fā)現(xiàn)自己在

像一個(gè)計(jì)算機(jī)科學(xué)家那樣思考。

AllenDowney

于馬薩諸塞州，波士頓

2003年3月6日

第1章編程方法論

這本書和這門課(計(jì)算機(jī)科學(xué)導(dǎo)引)的目的是教會(huì)你像一個(gè)計(jì)算機(jī)科學(xué)家

那樣思考。我喜歡計(jì)算機(jī)科學(xué)家思考的方式，因?yàn)檫@種方式整合了數(shù)學(xué)、工程

和自然科學(xué)的最佳特點(diǎn)。計(jì)算機(jī)科學(xué)家像數(shù)學(xué)家那樣使用形式語(yǔ)言來(lái)表示概念

(特別地，叫做計(jì)算一像工程師那樣設(shè)計(jì)事物，進(jìn)行權(quán)衡折衷

然后把部件集成成為一個(gè)系統(tǒng)；像自然科學(xué)家那樣通過(guò)假言和預(yù)設(shè)來(lái)觀測(cè)復(fù)雜

的系統(tǒng)。

對(duì)于一個(gè)計(jì)算機(jī)科學(xué)家來(lái)說(shuō)，唯一最重要的事情就是問(wèn)題求解。所謂“問(wèn)

題求解(problem-solving)”的能力就是，能夠抽象問(wèn)題并創(chuàng)造性的思考解決辦

法，然后清晰而且準(zhǔn)確無(wú)誤的描述出解決方案。久經(jīng)驗(yàn)證的結(jié)果表明，學(xué)習(xí)編

程的過(guò)程是一個(gè)練習(xí)問(wèn)題求解技巧的絕佳機(jī)會(huì)。這就是為什么這一章要叫做“編

程方法論”。

一方面，你將要學(xué)習(xí)編程------種有用的技巧；在另一層面上講，你會(huì)用

編程做為達(dá)到目的的手段，在學(xué)習(xí)的過(guò)程中，目標(biāo)將慢慢變得清楚起來(lái)。

1.1什么是編程語(yǔ)言？

這里要學(xué)習(xí)的是一門相當(dāng)新派名喚Java的編程語(yǔ)言(第一版是由Sun公司

在1995年發(fā)布)。Java是--例高階語(yǔ)言(.high-levellanguage),你可能還聽說(shuō)

過(guò)其它諸如Pascal,C或者C++和FORTRAN這樣的高階語(yǔ)言。

正如你可以從字面上推斷出來(lái)的那樣，有“高階”語(yǔ)言就有“低階”語(yǔ)言。

低階語(yǔ)言(low-levellanguage)通常指機(jī)器語(yǔ)言(machinelanguage)或者匯編

語(yǔ)言(assemblylanguage)。計(jì)算機(jī)只能執(zhí)行用低階語(yǔ)言編寫的程序，因此，用

高階語(yǔ)言編寫的程序必須經(jīng)過(guò)翻譯才能運(yùn)行。翻譯過(guò)程需要消耗時(shí)間——這是

高階語(yǔ)言的一個(gè)小小缺點(diǎn)。

而優(yōu)點(diǎn)則是不可勝數(shù)。首先，用高階語(yǔ)言編程更容易，這意味著寫程序需

要的時(shí)間更少，寫出來(lái)的東西也更短小易讀，也更容易改正。其次，高階語(yǔ)言

是可移植(portable)的，這意味著寫出來(lái)的程序只需要稍加修改甚至不用改就

可以直接在不同的計(jì)算機(jī)上運(yùn)行。低階程序只能在一種特定的機(jī)器上運(yùn)行

(rim),要換地方跑(run)只有另寫。

正是由于上述優(yōu)點(diǎn)，幾乎所有程序都是用高階語(yǔ)言編寫的，低階語(yǔ)言只用

來(lái)寫少數(shù)兒種特殊的應(yīng)用程序。

6如何像計(jì)算機(jī)科學(xué)家?樣思考

程序的翻譯有兩種方式：解釋(interpreting)和編譯(compiling)o

解釋器(interpreter)是用來(lái)讀取高階程序代碼然后照著做的程序。實(shí)際上，它

一行一行的翻譯程序代碼，然后依次執(zhí)行命令。

解釋器讀取源代碼...…結(jié)果在屏幕上顯示。

編譯器(compiler)則是這樣一種程序：它讀取高階程序代碼但并不執(zhí)行而把

它們一次全部翻譯好。一?般說(shuō)來(lái)編譯程序是一個(gè)單獨(dú)的步驟，經(jīng)過(guò)編譯的代碼

可供稍候執(zhí)行使用。在這種情況下，高階程序叫做源代碼(sourcecode),而翻

譯好的程序叫做目標(biāo)代碼(objectcode)或者可執(zhí)行代碼(.executable)0

舉個(gè)例，假如你要用C語(yǔ)言寫一個(gè)程序。你需要一個(gè)文本編輯器(一個(gè)很

簡(jiǎn)單的文字處理程序)用來(lái)寫你的程序，程序?qū)懞弥?，把它保存在一個(gè)叫做

的文件里，"program”是一個(gè)隨意取的名字，而后綴".c"