CHAPTER 1: INTRODUCTION

第一章:簡介

In this chapter, we discuss the aims and goals ofthis text and briefly review programming concepts and discrete mathematics. Wewill

此章哈垢，我們將討論本書目的并且簡單溫故一下編程思想和離散數(shù)學.我們將

[if !supportLists]l? [endif]See that how a program performs for reasonably large input is just asimportant as its performance on moderate amounts of input.

??? 領會一個程序在多輸入條件下是如何執(zhí)行與它在輸入量適當?shù)臈l件下如何執(zhí)行同等重要

[if !supportLists]l? [endif]Review good programming style.

??? 溫故一下良好的編程風格

[if !supportLists]l? [endif]Summarize the basic mathematical background needed for the rest of thebook.

??? 總結本書使用到的必備數(shù)學基礎

[if !supportLists]l? [endif]Briefly review recursion.

??? 簡單地復習一下遞歸

1.1. What's the Book About?

1.1關于本書*

Suppose you have a group of n numbers andwould like to determine the kth largest. This is known as the selectionproblem. Most students who have had a programming course or two would have nodifficulty writing a program to solve this problem. There are quite a few"obvious" solutions.

假設你有個n個數(shù)字的數(shù)組并且想要確認一下第k個比較大數(shù)值翁垂。這被稱為選擇問題。很多學過一兩門編程課程的同學可以輕而易舉地寫個程序解決這個問題。有很多的解決方法。

One way to solve this problem would be toread the n numbers into an array, sort the array in decreasing order by somesimple algorithm such as bubblesort, and then return the element in position k.

一種解決這個問題的方式是把這n個數(shù)字放到一個數(shù)組里面扇调，通過一些簡單的算法(例如冒泡排序)將這個數(shù)組進行遞減排序擂送，然后返回第K個位置的元素

A somewhat better algorithm might be toread the first k elements into an array and sort them (in decreasing order).Next, each remaining element is read one by one. As a new element arrives, itis ignored if it is smaller than the kth element in the array. Otherwise, it isplaced in its correct spot in the array, bumping one element out of the array.When the algorithm ends, the element in the kth position is returned as theanswer.

一個更好的速算法是將前K個元素讀入一個數(shù)組里面并將其排序(遞減排序序列)弄贿。下來液斜，剩下的元素一個一個的訪問。每訪問一個新元素奔垦，如果他比原先數(shù)組中的第k位元素素小的話就忽略它屹耐，否則將此元素替換到數(shù)組中的合適的位置。當算法結束時椿猎，第k個元素將作為答案被返回惶岭。

Both algorithms are simple to code, and youare encouraged to do so. The natural questions, then, are which algorithm isbetter and, more importantly, is either algorithm good enough? A simulationusing a random file of 1 million elements and k = 500,000 will show thatneither algorithm finishes in a reasonable amount of time--each requiresseveral days of computer processing to terminate (albeit eventually with acorrect answer). An alternative method, discussed in Chapter 7, gives asolution in about a second. Thus, although our proposed algorithms work, theycannot be considered good algorithms, because they are entirely impractical forinput sizes that a third algorithm can handle in a reasonable amount of time.

兩個算法編寫起來都很簡單，你應該去實踐一下犯眠。那么一個白癡的問題來了按灶，那個算法更好？進一步再說筐咧，這個相對好一點的算法它地的確確足夠好么鸯旁？一個有使用1百萬個元素并且K=50萬的隨機文檔的模擬問題將顯示任何一個算法都無法在一個合理的時間內完成--每個(算法)都需要數(shù)天的實踐來計算才能結束噪矛。（雖然確實在最后能得出正確答案）,在第七章討論了一個可供選擇的方法，它一秒就可以得出答案铺罢。因此艇挨，雖然我們提出的算法的確能喲on個，但是它們稱不上是好算法韭赘，因為第三個算法可以在可靠時間內處理的輸入規(guī)模對它們兩而言缩滨，實現(xiàn)起來完全不切實際。

A second problem is to solve a popular wordpuzzle. The input consists of a two-dimensional array of letters and a list ofwords. The object is to find the words in the puzzle. These words may behorizontal, vertical, or diagonal in any direction. As an example, the puzzleshown in Figure 1.1 contains the words this, two, fat, and that. The word thisbegins at row 1, column 1 (1,1) and extends to (1, 4); two goes from (1, 1) to(3, 1); fat goes from (4, 1) to (2, 3); and that goes from (4, 4) to (1, 1).

第二個問題是解決一個眾數(shù)單詞問題泉瞻。輸入是由一個二維字母數(shù)組和一列單詞組成的脉漏。目的是在問題中找出眾數(shù)單詞。這些單詞或水平或豎直或對角的任意方向瓦灶。舉個栗子鸠删，如圖1.1所示抱完，該圖包含了單詞this贼陶，two，fat巧娱，and that碉怔。This這個單詞從(1,1)延伸到(1,4);Two 從(1,1)延伸到(3,1)；Fat從(4,1)到(2,3);That從(4,4)到(1,1)禁添。

Again, there are at least twostraightforward algorithms that solve the problem. For each word in the wordlist, we check each ordered triple (row, column, orientation) for the presenceof the word. This amounts to lots of nested for loops but is basicallystraightforward.

另外撮胧，至少有兩種明顯的算法可以解決這個問題。對于每個單詞列表中的單詞而言老翘，我們檢查有序的三個(方向)確認是否存在單詞芹啥。這就相當于是基于直線的多層嵌套循環(huán)。

Alternatively, for each ordered quadruple(row, column, orientation, number of characters) that doesn't run off an end ofthe puzzle, we can test whether the word indicated is in the word list. Again,this amounts to lots of nested for loops. It is possible to save some time ifthe maximum number of characters in any word is known.

再者铺峭，對于每個四次序列（行墓怀，列，斜向卫键，字符數(shù)）檢索而言傀履，它不能很快寫出這個問題的結果，我們可以檢測是否這個單詞在這個單詞表中莉炉。也就是說钓账，這就相當于是多層嵌套循環(huán)。如果每個單詞中出現(xiàn)的最多的字母是提前預知的絮宁，就可能節(jié)省一些時間梆暮。

It is relatively easy to code up eithersolution and solve many of the real-life puzzles commonly published in magazines.These typically have 16 rows, 16 columns, and 40 or so words. Suppose, however,we consider the variation where only the puzzle board is given and the wordlist is essentially an English dictionary. Both of the solutions proposedrequire considerable time to solve this problem and therefore are notacceptable. However, it is possible, even with a large word list, to solve theproblem in a matter of seconds.

編碼上述任意一個解決方案并且解決許多出版雜志中普遍出現(xiàn)的現(xiàn)實的問題相對來說是容易的。這些通常有16行绍昂，16列惕蹄，大約40個單詞。然而，假設我們考慮到這種情況卖陵，僅僅給定問題的圖案遭顶，并且這個單詞表實際上就是一本英語辭典。這兩個解決方案都需要很大的時間解決這個問題泪蔫，這一點是讓人無法忍受的棒旗。然而，即使是一個很大的單詞列表撩荣，用幾秒鐘的時間解決這個問題也是可能的铣揉。

An important concept is that, in manyproblems, writing a working program is not good enough. If the program is to berun on a large data set, then the running time becomes an issue. Throughoutthis book we will see how to estimate the running time of a program for largeinputs and, more importantly, how to compare the running times of two programswithout actually coding them. We will see techniques for drastically improvingthe speed of a program and for determining program bottlenecks. Thesetechniques will enable us to find the section of the code on which toconcentrate our optimization efforts.

一個重要的思想是，在許多問題中沒有完美的工作程序餐曹。如果程序在一個大的數(shù)據(jù)集合上逛拱，運行時間就變成了一個大問題。怎樣去估計一個大輸入程序的運行時間這個問題貫穿了整本書台猴。更重要的是比較兩個還沒有實際編碼的程序的運行時間朽合。我們將會學習到大幅度提高程序運行速度的技術以及測定程序的瓶頸的技術。這些技術可以使我們找出我們應該集中精力去優(yōu)化的那些代碼片段饱狂。

[if !vml]

[endif]

Figure 1.1 Sample word puzzle

?

?

1.2. Mathematics Review

1.2.數(shù)學復習

??????This section lists some of the basic formulas you need to memorize or beable to derive and reviews basic proof techniques.

??????這一部分列出了一些你需要記住的或者是導出的基礎數(shù)學公式并且復習基礎的證明方法曹步。

1.2.1. Exponents

1.2.1指數(shù)

[if !vml]

[endif]

1.2.2.Logarithms

1.2.2.Logarithms

??????In computer science, alllogarithms are to base 2 unless specified otherwise.

?????在計算機科學中，所有的對數(shù)都是以2為底數(shù)的除非有特殊聲明休讳。

DEFINITION:[if !vml]

[endif]?if and only if[if !vml]

[endif]

定義：[if !vml]

[endif]當且僅當[if !vml]

[endif]

?Severalconvenient equalities follow from this definition.

?通過這個定義可以推導出幾個便利的公式

THEOREM 1.1.

定理1.1.

PROOF:

?[if !vml]

[endif]

證明：

??????Let[if !vml]

[endif], and[if !vml]

[endif]. Then, by the definition oflogarithms,[if !vml]

[endif], and[if !vml]

[endif]. Combining these three equalitiesyields[if !vml]

[endif]. Therefore, x = yz, which implies z =x/y, proving the theorem.

???????令[if !vml]

[endif], 和[if !vml]

[endif]讲婚。那么，通過給出的對數(shù)的定義俊柔，[if !vml]

[endif], and[if !vml]

[endif]筹麸。結合這三個等式可以推導出[if !vml]

[endif]。因此雏婶，x = yz物赶，那么z = x/y，定理由此可證尚骄。

THEOREM 1.2.

定理1.2.

log ab = log a + log b

PROOF:

證明：

???? Letx = log a, y = log b, z = log ab. Then, assuming the default base of 2,[if !vml]

[endif]. Combining the last three equalitiesyields[if !vml]

[endif]. Therefore,x + y

= z, which proves the theorem.

??? 令x = log a, y = log b, z = log ab块差。默認底數(shù)為2，[if !vml]

[endif]倔丈。結合后邊這三個等式[if !vml]

[endif]憨闰，則x + y = z，由此定理可證需五。

??? Someother useful formulas, which can all be derived in a similar manner, follow.

?? 下面這些有用的公式鹉动，都可以用相似的方法推導。

? [if !vml]

[endif]

1.2.3. Series

1.2.3.級數(shù)

The easiest formulas to remember are

[if !vml]

[endif]

and the companion,

[if !vml]

[endif]

要記住的最簡單的公式是[if !vml]

[endif]類似的[if !vml]

[endif]宏邮。

???? In the latterformula, if 0 < a < 1, then[if !vml]

[endif]and as n tends to [if !vml]

[endif], the sum approaches 1/(1 -a). These are the

"geometric series" formulas.We can derive the last formula for[if !vml]

[endif]in the following manner. Let S be the sum.

Then[if !vml]

[endif]

Then[if !vml]

[endif]

?????? 接下來泽示，如果0 < a < 1,那么[if !vml]

[endif]缸血，并且當n趨向于[if !vml]

[endif]時，結果無限接近1/(1 -a)械筛。這些是“等比級數(shù)”公式捎泻。我們就可以用下面的方法導出最后的公式[if !vml]

[endif]。把這個總和記為S埋哟，

那么[if !vml]

[endif]笆豁，那么[if !vml]

[endif]

???? If we subtract thesetwo equations (which is permissible only for a convergent series), virtuallyall the terms on the right side cancel, leaving[if !vml]

[endif]which simplies that[if !vml]

[endif]We can use this same technique to compute[if !vml]

[endif], a sum that occurs frequently. Wewrite[if !vml]

[endif]and multiply by 2, obtaining

[if !vml]

[endif]。Subtracting these two equations yields[if !vml]

[endif]赤赊。Thus, S = 2.

??? 如果這兩個等式相減（只允許是收斂級數(shù)時）闯狱，右邊所有項幾乎都消去了，剩下了[if !vml]

[endif],就簡化成了[if !vml]

[endif]我們可以使用相同的方法計算多項式[if !vml]

[endif]的和抛计，我們寫成[if !vml]

[endif]哄孤，等式乘以二可得[if !vml]

[endif]，等式兩邊相減得到[if !vml]

[endif]吹截，可得S = 2瘦陈。

???? Another type ofcommon series in analysis is the arithmetic series. Any such series can beevaluated from the basic formula.

[if !vml]

[endif]

???? 在分析里邊另外一個常見級數(shù)類型是算法級數(shù)。任一個這樣的級數(shù)都能用基礎的公式[if !vml]

[endif]計算饭弓。

???? For instance, to findthe sum 2 + 5 + 8 +. . . + (3k - 1), rewrite it as 3(1 + 2+ 3 +. . . + k) - (1+ 1 + 1 +. . . + 1), which is clearly 3k(k + 1)/2 - k. Another way to rememberthis is to add the first and last terms (total 3k + 1), the second and next tolast terms (total 3k + 1), and so on. Since there are k/2 of these pairs, thetotal sum is k(3k + 1)/2, which is the same answer as before.

???? 例如双饥，為了計算2 + 5 + 8 +. . . + (3k - 1)的和媒抠，把它改寫成3(1 + 2+

3 +. . . + k) - (1 + 1 + 1 +. . . + 1)弟断，就等于3k(k + 1)/2 -

k。另外一個記住這個的方法就是首尾相加（和為3k + 1）趴生，第二項和倒數(shù)第二項相加（和為3k + 1）阀趴，等等。有這樣k/2對苍匆，總和就是k(3k + 1)/2刘急，跟之前的答案相同。

???? The next two formulaspop up now and then but are fairly infrequent.

[if !vml]

[endif]

When k = -1, the latter formula is not valid. We then need thefollowing formula, which is used far more in computer science than in othermathematical disciplines. The numbers, HN, are known as the harmonic numbers,and the sum is known as a harmonic sum.The error in the

following approximation tends to y[if !vml]

[endif] 0.57721566, which is known asEuler's constant.

[if !vml]

[endif]

???? 下面兩個幾乎用不到的公式我們也列舉出來：

[if !vml]

[endif]

當k=-1時浸踩，后邊這個公式沒有意義叔汁。我們需要后邊這個公式，它在計算機科學中比在其他數(shù)學科目中用得多得多检碗。這個數(shù)列被稱為調和數(shù)列据块，這個和被稱為調和級數(shù)之和。下邊這個近似值的誤差趨近于y[if !vml]

[endif] 0.57721566折剃，這被稱作歐拉常量另假。

These two formulas are just general algebraic manipulations.

[if !vml]

[endif]

下邊這兩個公式就是常見的代數(shù)運算：

[if !vml]

[endif]

1.2.4. Modular Arithmetic

1.2.4.模數(shù)運算

???? We saythat a is congruent to b modulo n, written a[if !vml]

[endif]b(mod n), if n divides a - b.Intuitively, this means that the remainder is the same when either a or b isdivided by n. Thus, 81 61 1(mod 10). As with equality, if a b (mod n), then a +c b + c(mod n) anda d b d (mod n).

???? 我們說a恒等于b對n求模，寫成a≡b(mod n)(a同余于b模n怕犁，或讀作a與b關于模m同余）边篮，如果n能整除a-b己莺。直觀地說，意思就是當a或b被n除的時候戈轿，它們的余數(shù)相同凌受。例如， 81 61 1(mod 10)思杯。等價的胁艰，如果 a b (mod n)，那么a + c b + c(mod n)和a d b d (mod n)智蝠。

There are a lot of theorems that apply to modulararithmetic, some of which require extraordinary proofs in number theory. Wewill use modular arithmetic sparingly, and the preceding theorems will suffice.

有很多適用于模數(shù)運算的定理腾么，有些在數(shù)論中證明的很巧妙。我們用到模數(shù)運算不多杈湾，前面的那些定理就夠用了解虱。

1.2.5. The P Word

1.2.5.證明方法

???? The twomost common ways of proving statements in data structure analysis are proof byinduction and proof by contradiction (and occasionally aproof

by intimidation, by professors only). The best way of proving that atheorem is false is by exhibiting a counterexample.

???? 數(shù)據(jù)結構中兩個最常見的證明方法是歸納證明法和反證法（只有教授偶爾使用歸謬法）。證明一個定理錯誤的最好的方法是舉反例漆撞。

Proof byInduction

歸納法證明

A proofby induction has two standard parts. The first step is proving a base case,that is, establishing that a theorem is true for some small (usuallydegenerate) value(s); this step is almost always trivial. Next, an inductivehypothesis is assumed. Generally this means that the theorem is assumed to betrue for all cases up to some limit k. Using this assumption, the theorem isthen shown to be true for the next value, which is typically k + 1. This provesthe theorem (as long as k is finite).

歸納法證明由標準的兩步構成殴泰。第一步是證明基本的情況，確定一個定理對一小部分值成立浮驳；這一步是瑣細的悍汛。下一步，一個歸納的假設是假定的至会。通常情況下這就意味著到k為止的所有情況下假設都是成立的离咐。使用這個假設，證明接下來的k+1值對于這個假設也是成立的奉件。定理可證（只要k是有限的）宵蛀。

???? As anexample, we prove that the Fibonacci numbers,[if !vml]

[endif]satisfy[if !vml]

[endif]。(Some definitions have F0 = 0, which

shifts the series.) To do this, we first verify that the theorem is true for

the trivial cases.It is easy to verify that F1 = 1 < 5/3 and F2 = 2县貌。We assume that the theorem is true for i = 1, 2, . . . , k; this is

the inductive hypothesis. To prove the theorem, we need to show that[if !vml]

[endif]术陶。We have[if !vml]

[endif]，by the definition, and we can use theinductive hypothesis on the right-hand side, obtaining

?? [if !vml]

[endif]

[if !vml]

[endif]

which simplifies to

[if !vml]

[endif]

proving the theorem.

????? 舉個例子煤痕，我們證明斐波那契數(shù)列梧宫，[if !vml]

[endif]，滿足[if !vml]

[endif]摆碉。（有一些定義改變了這個數(shù)列塘匣，設置了F0=0）。為了這名這個定理兆解，我們首先證明這個定理適用于瑣細的情況馆铁。證明F1 = 1 < 5/3 和F2 = 2是簡單的。我們假設這個定理適用于i = 1, 2, . . . , k锅睛；這是歸納假設埠巨。為了證明這個定理历谍，我們需要證明[if !vml]

[endif]（1是加于k上的）。我們有[if !vml]

[endif]辣垒，通過定義望侈，我們把這個歸納假設用在等號右邊，得到

[if !vml]

[endif]

[if !vml]

[endif]

化簡為

[if !vml]

[endif]

定理可證勋桶。

???? As asecond example, we establish the following theorem.

???? 第二個例子脱衙，我們證明下一個定理。

THEOREM 1.3.

[if !vml]

[endif]

當[if !vml]

[endif]

PROOF:

證明：

???? Theproof is by induction. For the basis, it is readily seen that the theorem istrue when n = 1. For the inductive hypothesis, assume that the theorem is truefor[if !vml]

[endif]. We will establish that, underthis assumption, the theorem is true for n + 1. We have

[if !vml]

[endif]

Applying the inductive hypothesis, we obtain

[if !vml]

[endif]

Thus,

[if !vml]

[endif]

proving the theorem.

?? 用歸納法證明例驹。首先捐韩，當n=1時，定理顯然成立鹃锈。假設這個定理對于[if !vml]

[endif]都是成立的荤胁。我們將證明這個定理在這個假設的情況下對于n+1也是成立的。我們有

[if !vml]

[endif]

根據(jù)這個歸納假設屎债，可以得到

[if !vml]

[endif]

因此仅政，

[if !vml]

[endif]

Proof by Counterexample

舉反例法證明

???? Thestatement[if !vml]

[endif]is false.The easiest way to prove

this is to compute[if !vml]

[endif]。

????????? [if !vml]

[endif]是錯誤的盆驹。最簡單的證明方法就是估計[if !vml]

[endif]圆丹。

Proof by Contradiction

反證法

???? Proof bycontradiction proceeds by assuming that the theorem is false and showing thatthis assumption implies that some known property is false, and hence theoriginal assumption was erroneous. A classic example is the proof that there isan infinite number of primes. To prove this, we assume that the theorem isfalse, so that there is some largest prime[if !vml]

[endif]，Let[if !vml]

[endif]be all the primes in order and

consider[if !vml]

[endif]躯喇。Clearly, N is larger than pk, so byassumption N is not prime. However, none ofp1, p2, . . . ,

pkdivide N exactly, because there will always be a remainder of 1. This isa contradiction, because every number is either prime or a product of primes.Hence, the original assumption, that pk is the largest prime, is false, whichimplies that the theorem is true.

[if !vml]

[endif]

?????? 反證法通過假設這個定理是錯的來進行的辫封，證明這個假設就意味著證明一些已知條件是錯的，從而假設是錯誤的玖瘸。一個典型的例子就是證明有無窮多個質數(shù)秸讹。為了證明檀咙，我們假設這個定理是錯誤的雅倒，所以就有最大的質數(shù)[if !vml]

[endif]，使得[if !vml]

[endif]是按順序排列的所有的質數(shù)并且令[if !vml]

[endif]弧可。很明顯蔑匣，N比pk大，所以根據(jù)假設棕诵，N不是質數(shù)裁良。事實上，p1, p2, . . . , pk沒有一個數(shù)能整除N校套，因為總有一個余數(shù)1.這就是反證价脾，因為每一個數(shù)都是質數(shù)或者質數(shù)的乘積。因此笛匙，最初的假設：pk是最大的質數(shù)是錯誤的侨把，證明了定理是正確的犀变。

1.3. A Brief Introduction to Recursion

1.3. 遞歸的簡介

Most mathematical functions that we arefamiliar with are described by a simple formula. For instance, we can converttemperatures from Fahrenheit to Celsius by applying the formula

我們熟悉的絕大多數(shù)數(shù)學函數(shù)都可以使用一個簡單的數(shù)學公式來表達。舉個栗子秋柄，我們可以通過下述公式將溫度值從華氏度轉化為是攝氏度

?C =5(F - 32)/9

攝氏度=5x(華氏度-32)/9

Given this formula, it is trivial to writea C function; with declarations and braces removed, the one-line formulatranslates to one line of C.

給出的這個公式获枝，如果用C函數(shù)寫出來小菜一碟；如果不考慮聲明和括號骇笔，單句公式可以被翻譯成一句C語言語句省店。

Mathematical functions are sometimesdefined in a less standard form. As an example, we can define a function f,valid on nonnegative integers, that satisfies f(0) = 0 and f(x) = 2f(x - 1) +x2. From this definition we see that f(1) = 1, f(2) = 6, f(3) = 21, and f(4) =58. A function that is defined in terms of itself is called recursive. C allowsfunctions to be recursive.

有時,數(shù)學公式是使用極簡形式。舉個栗子,我們可以定義一個函數(shù)f,定義域為非負整數(shù)笨触，滿足f(0)=0,且f（x）=2f(x-1)+x^2懦傍。從此定義我們可以得出，f(1) = 1, f(2) = 6, f(3)

= 21, f(4) = 58芦劣。一個函數(shù)是根據(jù)自身定義的谎脯，那么這個函數(shù)就是遞歸的。C語言允許遞歸持寄。

* It is important to remember that what Cprovides is merely an attempt to follow the recursive spirit. Not allmathematically recursive functions are efficiently (or correctly) implementedby C's simulation of recursion. The idea is that the recursive function f oughtto be expressible in only a few lines, just like a non-recursive function.Figure 1.2 shows the recursive implementation of f.

謹記C語言僅提供一個試圖遵循遞歸性是重要的源梭。并非所有的數(shù)學遞歸函數(shù)都能用C語言有效(或合適)地實現(xiàn)。思想是遞歸函數(shù)f應當像非遞歸函數(shù)一行可以僅用幾行代碼描述出來.

圖片1.2顯示了遞歸函數(shù)f的實現(xiàn)

*Using recursion for numerical calculationsis usually a bad idea. We have done so to illustrate the basic points. Lines 1and 2 handle what is known as the base case, that is, the value for which thefunction is directly known without resorting to recursion. Just as declaringf(x) = 2 f(x - 1) + x2 is meaningless, mathematically, without including thefact that f (0) = 0, the recursive C function doesn't make sense without a basecase. Line 3 makes the recursive call.

使用遞歸計算數(shù)值通常不是什么好想法稍味。我們先表明了基礎態(tài)度废麻。第一二行代碼已經處理了元情況，也就是說模庐，此函數(shù)的值無需遞歸計算烛愧，直接給出。就像聲明數(shù)學函數(shù)f(x) = 2 f(x - 1) + x^2在不給定能夠基礎條件f（0）=0下是無意義的一樣掂碱。該C語言遞歸函數(shù)在無元情況條件下也是無意義的怜姿。第三行代碼使用了遞歸調用。

There are several important and possiblyconfusing points about recursion. A common question is: Isn't this justcircular logic? The answer is that although we are defining a function in termsof itself, we are not defining a particular instance of the function in termsof itself. In other words, evaluating f(5) by computing f(5) would be circular.Evaluating f(5) by computing f(4) is not circular--unless, of course f(4) isevaluated by eventually computing f(5). The two most important issues areprobably the how and why questions. In Chapter 3, the how and why issues areformally resolved. We will give an incomplete description here.

關于遞歸疼燥，有以下幾個重難點沧卢。一個經常遇到的問題就是:遞歸就是一個邏輯循環(huán)嗎？答案是:雖然我們使用函數(shù)本身來定義它自己醉者，但是我們并未定義一個特定的函數(shù)實例但狭。換句話說，使用計算機計算f(5)的值就是循環(huán)撬即，通過f(4)的值來計算f(5)不是循環(huán)----當然立磁，這不包括f(4)的值在計算f(5)的過程中已經計算出來的這種情況。兩個最重要的點或許是問題怎樣破和為什么這么破剥槐。在第三章中唱歧，這兩點會正式解決。我們在這里給一個不完整的描述粒竖。

It turns out that recursive calls arehandled no differently from any others. If f is called with the value of 4,then line 3 requires the computation of 2 * f(3) + 4 * 4. Thus, a call is madeto compute f(3). This requires the computation of 2 * f(2) + 3 * 3. Therefore,another call is made to compute f(2). This means that 2 * f(1) + 2 * 2 must beevaluated. To do so, f(1) is computed as 2 * f(0) + 1 * 1. Now, f(0) must beevaluated. Since this is a base case, we know a priori that f(0) = 0. Thisenables the completion of the calculation for f(1), which is now seen to be 1.Then f(2), f(3), and finally f(4) can be determined. All the bookkeeping neededto keep track of pending function calls (those started but waiting for arecursive call to complete), along with their variables, is done by thecomputer automatically. An important point, however, is that recursive callswill keep on being made until a base case is reached. For instance, anattempt to evaluate f(-1) will result in calls to f(-2), f(-3), and so on.Since this will never get to a base case, the program won't be able to computethe answer (which is undefined anyway). Occasionally, a much more subtle erroris made, which is exhibited in Figure 1.3. The error in the program in Figure1.3 is that bad(1) is defined, by line 3, to be bad(1). Obviously, thisdoesn't give any clue as to what bad(1) actually is. The computer will thusrepeatedly make calls to bad(1) in an attempt to resolve its values.Eventually, its bookkeeping system will run out of space, and the program willcrash. Generally, we would say that this function doesn't work for one specialcase but is correct otherwise. This isn't true here, since bad(2) calls bad(1).Thus, bad(2) cannot be evaluated either. Furthermore, bad(3), bad(4), andbad(5) all make calls to bad(2). Since bad(2) is unevaluable, none of thesevalues are either. In fact, this program doesn't work for any value of n,except 0. With recursive programs, there is no such thing as a "specialcase."

執(zhí)行遞歸調用和執(zhí)行其他調用時沒啥區(qū)別的颅崩！如果使用參數(shù)值為4調用函數(shù)f,那么第三行代碼要求計算2*f(3)+4*4绍刮。因此，產生了一個新的調用來計算f(3)挨摸。這個新的調用要求去計算2*f(2)+3*3.因此再來一個調用來計算f(2),這就相當于會計算2*f(1)+2*2,為了完成這個計算f(1)會被計算為2f(0)+1*1『⒏铮現(xiàn)在,f(0)一定要被計算出來了。因為這是一個源情況,我們知道原條件f(0)=0得运。這就是的f(1)可以被計算了膝蜈，f(1)=1,以此類推,f(2),f(3),最終f(4)都可以被計算出。所有根據(jù)路徑被記在賬本上的待定的函數(shù)調用伴隨著他們的變量值都被電腦自動計算了熔掺。然而饱搏，在抵達元情況之前,遞歸調用將一直在重復是個重點。舉個例子置逻，嘗試計算f(-1)將導致調用計算f(-2),f(-3)等等...推沸。程序將無法計算算出答案(它們未定義),因為它永遠無法到達元情況。偶爾券坞，展示出的圖片1.3會產生一個坑人于無形的錯誤鬓催。圖1.3中程序的錯誤在求bad(1)在第三行代碼產生了。

明顯恨锚，關于bad(1)實際上是啥宇驾，它等于沒說！電腦會重復調用去嘗試計算算bad(1)的值猴伶。最后课舍，這個記賬本系統(tǒng)將會使用完所有的空間，并且程序會崩潰他挎。一般而言呢筝尾，我們會說這個函數(shù)在特定條件下不工作但其余情況運轉正常。它在這兒這兒不對办桨，bad(2)要調用bad(1)筹淫，因此，bad(2)也是無法計算的崔挖，此外贸街，bad(3),bad(4)，bad(5)都會調用bad(2)狸相，因為bad(2)無法計算，因此他們沒有一個可以倍計算出來捐川。事實上脓鹃，這個程序對于任意的非零n,都無法正常工作。對于遞歸程序而言古沥，沒有什么”特殊情況”瘸右！

These considerations lead to the first twofundamental rules of recursion:

關于遞歸,這有兩個基本原則值得考慮:

[if !supportLists]1. [endif]Base cases.You must always have some base cases, which can be solved without recursion.

[if !supportLists]1.[endif]元情況娇跟，你必須總有一些不適用遞歸就能得出答案的基本情況

[if !supportLists]2. [endif]Makingprogress. For the cases that are to be solved recursively, the recursive callmust always be to a case that makes progress toward a base case.

[if !supportLists]2.[endif]編寫下一步。對于那些使用遞歸解決的情況而言太颤，遞歸調用必須總是達到一種可以逐步使用到元情況的狀態(tài)苞俘。

Throughout this book, we will use recursionto solve problems. As an example of anonmathematical use,consider a large dictionary. Words in dictionaries are defined in terms ofother words. When we look up a word, we might not always understand thedefinition, so we might have to look up words in the definition. Likewise, wemight not understand some of those, so we might have to continue this searchfor a while. As the dictionary is finite, eventually either we will come to apoint where we understand all of the words in some definition (and thusunderstand that definition and retrace our path through the other definitions),or we will find that the definitions are circular and we are stuck, or thatsome word we need to understand a definition is not in the dictionary.

我們遞歸地解決遇到的問題將貫穿整本書。對于那些非數(shù)學的用例龄章，將它們人做是一個超大的字典吃谣。字典中的單詞使用其他單詞來定義。當我們查詢一個單詞的時候做裙，我們或許不總是理解其定義岗憋，因此我們可能要查詢其定義中的單詞。同樣锚贱，我們或許不理解它們(定義中的單詞)仔戈，因此我們不得不繼續(xù)再進行查找。因為一個字典是有限的拧廊，要么最終我們可以抵達理解定義中所有的單詞的地步(理解那些定義并且回溯我們對單詞的理解路徑)监徘，要么我們會發(fā)現(xiàn)我們卡在輪回的定義上，要么我們需要理解的某些單詞定義根本不在字典里吧碾。

[if !vml]

[endif]

圖1.3? 一個無盡的遞歸程序

Our recursive strategy to understand wordsis as follows: If we know the meaning of a word, then we are done; otherwise,we look the word up in the dictionary. If we understand all the words in thedefinition, we are done; otherwise, we figure out what the definition means byrecursively looking up the words we don't know. This procedure will terminateif the dictionary is well defined but can loop indefinitely if a word is eithernot defined or circularly defined.

我們理解單詞遞歸策略如下:如果我們知道一個單詞的意思耐量，那么就罷了，否則滤港，我們需要在字典中查詢廊蜒。如果我們理解定義中的所有單詞，那就完成了溅漾，否則山叮，我們需要通過遞歸查詢那些我們不懂得單詞來搞明白定義。如果字典編寫的很好,那么這個套路結束了屁倔，如果一個單詞沒定義或輪回定義,那么這個套路就沒完沒了了暮胧。

Printing Out Numbers

打印數(shù)字

Suppose we have a positive integer, n, thatwe wish to print out. Our routine will have the heading print_out(n). Assumethat the only I/O routines available will take a single-digit number and outputit to the terminal. We will call this routine print_digit; for example,print_digit(4) will output a 4 to the terminal.

假設我們想打印一個正數(shù)，我們的程序把 print_out(n)作為標題,假設唯一I/O程式可用將取一個個位數(shù)取出并顯示在終端上钞翔。我們將這個程式成為print_digit;比如來說席舍，print_digit(4)，就是把4輸出到終端上。

Recursion provides a very clean solution tothis problem. To print out 76234, we need to first print out 7623 and thenprint out 4. The second step is easily accomplished with the statementprint_digit(n%10), but the first doesn't seem any simpler than the originalproblem. Indeed it is virtually the same problem, so we can solve itrecursively with the statement print_out(n/10).

對于這個問題稠肘，遞歸給出一個極簡風格的解決方案萝毛。為了打印出76234项阴，我們需要先打印7623而后打印4.第二步通過表達式print_digit(n%10)非常容易實現(xiàn)，但是前面的部分看起來似乎不必原問題簡單笆包。的確它是相同的問題,因此我們通過表達式print_out(n/10)來遞歸的解決它們环揽。

This tells us how to solve the generalproblem, but we still need to make sure that the program doesn't loopindefinitely. Since we haven't defined a base case yet, it is clear that we stillhave something to do. Our base case will be print_digit(n) if 0

這給我們說明了如何解決一般問題，但是我們仍需確認這個程序不會無限循環(huán)色查。因為我們仍未定義元情況薯演，明顯我們還有些事情未做。我們的元情況就是print_digit(n) if 0

* is shown Figure 1.4.

已經在圖1.4中給出秧了。

*The term procedure refers to a functionthat returns void.

這個部分程序是無返回值函數(shù)

We have made no effort to do thisefficiently. We could have avoided using the mod routine (which is veryexpensive) because n%10 = n - (n/10) * 10.

我們輕易地已經完成了這個程序跨扮。我們本可以避免使用模數(shù)例程(模數(shù)運算太高消耗)，因為 n%10求余 = n-(n/10)*10验毡。

Recursion and Induction

遞歸和歸納

Let us prove (somewhat) rigorously that therecursive number-printing program works. To do so, we'll use a proof byinduction.

讓我們嚴格證明遞歸數(shù)字打印程序衡创。為此，我們需要使用歸納來證明晶通。

THEOREM 1.4

定理1.4

The recursive number-printing algorithm iscorrect for n >=0.

對于n>=0的情況璃氢，這個遞歸打印數(shù)字算法是正確的。

PROOF: First, if n has one digit, then theprogram is trivially correct, since it merely makes a call to print_digit.Assume then that print_out works for all numbers of k or fewer digits. A numberof k + 1 digits is expressed by its first k digits followed by its leastsignificant digit. But the number formed by the first k digits is exactly n/10, which, by the indicated hypothesis is correctly printed, and the last digitis n mod10, so the program prints out any (k + 1)-digit number correctly. Thus,by induction, all numbers are correctly printed.

證明:首先狮辽，如果n是個位數(shù)字一也，那么很簡單，它是正確的喉脖，因為他只調用了跑一次print_digit椰苟。假設print_out支持k個或少于k數(shù)位的數(shù)字作為參數(shù)。一個k+1位數(shù)字就是由它的前k位數(shù)字和在這之后的最低有效位數(shù)字組成树叽。但是前k位數(shù)字組成的書實際上等于n/10,根據(jù)之前的假設它們(前k個數(shù)字組成的數(shù))可以被正確打印,并且最后一位數(shù)就是n mod 10,因此這個程序可以正確打印任意(k+1)位的數(shù)字舆蝴。因此题诵，通過歸納法赠潦，所有的數(shù)字都可以被正確打印祭椰。

[if !vml]

[endif]

圖片1.4 遞歸程序打印一個整數(shù)

This proof probably seems a little strangein that it is virtually identical to the algorithm description. It illustratesthat in designing a recursive program, all smaller instances of the sameproblem (which are on the path to a base case) may be assumed to workcorrectly. The recursive program needs only to combine solutions to smallerproblems, which are "magically" obtained by recursion, into asolution for the current problem. The mathematical justification for this isproof by induction. This gives the third rule of recursion:

這個證明,或許看起來有點奇怪方淤，因為它幾乎跟算法描述一模一樣。它說明了在設計一個遞歸程序的時候讳苦，所有相同問題的小小實現(xiàn)(問題就是到元情況的過程)或許假定正確執(zhí)行了鸳谜。遞歸程序僅僅需要將小問題的解決方式組合起來,這些解決方式是通過遞歸魔法般的組織在一起的，最終成為當前問題的解決方案蝗肪。這個數(shù)學證明過程使用了歸納法薛闪。這給出了第三條關于遞歸的戒律豁延。

[if !supportLists]3.[endif]Design rule.Assume that all the recursive calls work.

3.設計規(guī)則,使得所有的遞歸調用都可以正常工作诱咏。

This rule is important because it meansthat when designing recursive programs, you generally don't need to know thedetails of the bookkeeping arrangements, and you don't have to try to tracethrough the myriad of recursive calls. Frequently, it is extremely difficult totrack down the actual sequence of recursive calls. Of course, in many casesthis is an indication of a good use of recursion, since the computer is beingallowed to work out the complicated details. The main problem with recursion isthe hidden bookkeeping costs. Although these costs are almost alwaysjustifiable, because recursive programs not only simplify the algorithm designbut also tend to give cleaner code, recursion should never be used as asubstitute for a simple for loop. We'll discuss the overhead involved inrecursion in more detail in Section 3.3.

這個規(guī)則很重要，因為它意味著當你設計一個遞歸程序的時候硕并，你一般不需要知道棧內細節(jié)安排,并且你不必嘗試回溯遞歸調用的路徑倔毙。通常而言,回溯實際的遞歸調用順序非常困難陕赃。當然么库，很多情況下葡缰，這是一個遞歸好的用法的表現(xiàn)泛释，因為計算機被允許計算出這些復雜的磨人的細節(jié)怜校。遞歸的主要問題是棧內存消耗的隱蔽性茄茁。雖然那些消耗幾乎總是合理的，因為遞歸程序不僅簡化了算法設計传轰，它還能使代碼更簡潔。遞歸永遠不應該被當做一個簡單for循環(huán)的替代品扬卷。在3.3章節(jié)我們將討論這個遞歸導致棧內存開銷的詳細問題怪得。

When writing recursive routines, it iscrucial to keep in mind the four basic rules of recursion:

寫遞歸程序的時候,牢記四條基本遞歸法則很重要。

[if !supportLists]1. [endif]Base cases.You must always have some base cases, which can be solved without recursion.

1.元情況,你必須總是有幾個元情況入挣，可以無需使用遞歸直接給出答案葛假。

[if !supportLists]2. [endif]Makingprogress. For the cases that are to be solved recursively, the recursive callmust always be to a case that makes progress toward a base case.

2.使進程化聊训，對于那些需要遞歸解決的情況而言魔眨，遞歸調用必須總是通過一系列進程最終到達元情況。

[if !supportLists]3. [endif]Designrule. Assume that all the recursive calls work.

3.設計規(guī)則指黎，使得所有的遞歸調用都可以工作醋安。

[if !supportLists]4. [endif]Compoundinterest rule. Never duplicate work by solving the same instance of a problemin separate recursive calls.

4.整合有意思的規(guī)則。在不同的遞歸調用不要復制相同的工作通過相同的問題實例

The fourth rule, which will be justified(along with its nickname) in later sections, is the reason that it is generallya bad idea to use recursion to evaluate simple mathematical functions, such asthe Fibonacci numbers. As long as you keep these rules in mind, recursiveprogramming should be straightforward.

將會在后面的章節(jié)中被解釋(沿用它的名稱)的第四條規(guī)則柠辞，是在通常情況下遞歸被用來計算簡單的數(shù)學函數(shù)(例如菲波那切數(shù)列)是個壞主意的原因叭首。只要你將這些規(guī)則牢記于心，遞歸程序將會非常簡單眷唉。

Summary

總結

This chapter sets the stage for the rest ofthe book. The time taken by an algorithm confronted with large amounts of inputwill be an important criterion for deciding if it is a good algorithm. (Ofcourse, correctness is most important.)Speed is relative. What is fast for oneproblem on one machine might be slow for another problem or a differentmachine. We will begin to address these issues in the next chapter and will usethe mathematics discussed here to establish a formal model.

這章節(jié)是本書其余內容的基礎，相對多輸入的情況下算法消耗的時間是很重要的評判算法優(yōu)良的標準摩泪。(當然,正確是最重要的!)速度是相對的见坑。對一個機器上的一個問題的快速解決的方案有可能對另一個問題或者不同機器來說就慢了不皆。我們將在下一張開始處理這些問題并且會使用到這張討論的數(shù)學只是去建立一個合適模型。

Exercises

[if !supportLists]1.1?? [endif]Writea program to solve the selection problem. Let k = n/2. Draw a table showing therunning time of your program for various values of n.

1.2 Write a program to solve the word puzzle problem.

1.3 Write a procedure to output an arbitrary real number(which might be negative) using only print_digit for I/O.

1.4 C allows statements of the form

#include filename

which reads filename and inserts its contents in place ofthe include statement. Include statements may be nested; in other words, thefile filename may itself contain an include statement, but, obviously, a filecan't include itself in any chain. Write a program that reads in a file andoutputs the file as modified by the include statements.

1.5 Prove the following formulas:

a. log x < x for all x > 0

[if !vml]

[endif]

1.6 Evaluate the following sums:

[if !vml]

[endif]

1.7 Estimate

[if !vml]

[endif]

*1.8 What is[if !vml]

[endif]？

1.9 Let[if !vml]

[endif]be the Fibonacci numbers as definedin Section 1.2. Prove the following:

[if !vml]

[endif]

**c. Give a precise closed-form expression for[if !vml]

[endif]

1.10 Prove the following formulas:

[if !vml]

[endif]

1.1寫一個程序解決選擇問題枕磁。令k=n/2.畫一張表计济，體現(xiàn)你的程序對于不同的n值需要的運行時間。

1.2寫一個程序解決單詞字謎問題

1.3寫一個只用print digit來輸出的程序輸出一個任意實數(shù)(包括負數(shù))

1.4 C語言允許這樣形式的語句：

#include filename

它會讀取文件名并且插入該文件的內容取代這個#include語句传藏。Include語句可能是嵌入的漩氨；換句話說，這個文件名或許它本身就包括一個include語句，但是，很明顯宾濒，一個文件在任何環(huán)節(jié)中都不能包括它自己橘忱。寫一個程序讀入一個文件钝诚，并且輸出被include語句修改后的這個文件。

1.5證明下面的公式：

a. log x < x for all x > 0

[if !vml]

[endif]

1.6計算下列和:

[if !vml]

[endif]

1.7估值：

[if !vml]

[endif]

*1.8[if !vml]

[endif]是什么拧略？

1.9 設[if !vml]

[endif]是1.2節(jié)被定義的斐波那契數(shù)列。證明下式：

[if !vml]

[endif]

**c. 給出一個精確的封閉式的[if !vml]

[endif]表達式

1.10 證明下列公式：

[if !vml]

[endif]

?

References

There are many good textbooks covering the mathematicsreviewed in this chapter. A small subset is [1], [2], [3], [11], [13], and[14]. Reference [11] is specifically geared toward the analysis of algorithms.It is the first volume of a three-volume series that will be cited throughoutthis text. More advanced material is covered in [6].

有許多好的教材都在這一章復習了數(shù)學知識杠茬。一小部分是[1], [2], [3], [11], [13],和[14]。參考書[11]是專門面向算法分析的弛随。一個分為三冊的一套書的第一冊在整書中被引用瓢喉。更先進的材料在[6]中。

Throughout this book we will assume a knowledge of C [10].Occasionally, we add a feature where necessary for clarity. We also assumefamiliarity with pointers and recursion (the recursion summary in this chapteris meant to be a quick review). We will attempt to provide hints on their usewhere appropriate throughout the textbook. Readers not familiar with theseshould consult [4], [8], [12], or any good intermediate programming textbook.

整本書中舀透，我們都將假設C[10]的知識栓票。偶爾，為了更清晰愕够，我們也有必要加一點特別的知識惑芭。我們也假設熟悉指針和遞歸（本章中遞歸的總結是一個快速的復習）凯亮。我們將會在整本書中要適當?shù)氖褂盟臅r候提供提示堂鲤。不熟悉這個的讀者應該去查閱[4]

[8] [12] ，或許任何一本好的作為媒介的編程教材。

General programming style is discussed in several books.Some of the classics are [5], [7], and [9].

比較普遍的編程風格在幾本書中都有介紹糯崎。[5] [7] [9]都是比較經典的薄霜。

[if !supportLists]1.????? [endif]M. O.Albertson and J. P. Hutchinson, Discrete Mathematics with Algorithms, JohnWiley & Sons, New York , 1988.

2. Z. Bavel, Math Companion for Computer Science, RestonPublishing Company, Reston, Va., 1982.

3. R. A. Brualdi, Introductory Combinatorics, North-Holland,New York, 1977.

4. W. H. Burge, Recursive Programming Techniques,Addison-Wesley, Reading, Mass., 1975.

5. E. W. Dijkstra, A Discipline of Programming, PrenticeHall, Englewood Cliffs, N.J., 1976.

6. R. L. Graham, D. E. Knuth, and O. Patashnik, ConcreteMathematics, Addison-Wesley, Reading, Mass., 1989.

7. D. Gries, The Science of Programming, Springer-Verlag,New York, 1981.

8. P. Helman and R. Veroff, Walls and Mirrors: IntermediateProblem Solving and Data Structures, 2d ed., Benjamin Cummings Publishing,Menlo Park, Calif., 1988.

9. B. W. Kernighan and P. J. Plauger, The Elements ofProgramming Style, 2d ed., McGraw- Hill, New York, 1978.

10. B. W. Kernighan and D. M. Ritchie, The C ProgrammingLanguage, 2d ed., Prentice Hall, Englewood Cliffs, N.J.,1988.

11. D. E. Knuth, The Art of Computer Programming, Vol. 1:Fundamental Algorithms, 2d ed., Addison-Wesley,Reading, Mass., 1973.

12. E. Roberts, Thinking Recursively, John Wiley & Sons,New York, 1986.

13. F. S. Roberts, Applied Combinatorics, Prentice Hall,Englewood Cliffs, N.J., 1984.

14. A. Tucker, Applied Combinatorics, 2d ed., John Wiley& Sons, New York, 1984.

[if !supportLists]1.????? [endif]M. O.

Albertson and J. P. Hutchinson 打月，離散數(shù)學和算法秘通，John Wiley & Sons夕吻，紐約捻浦，1998

[if !supportLists]2.????? [endif]Z.

Bavel形导，計算機數(shù)學，Reston出版公司檐薯，Reston,

Va.，1982

[if !supportLists]3.????? [endif]R. A.

Brualdi勇皇，組合數(shù)學介紹，North-Holland,

New York,房揭，1997

[if !supportLists]4.????? [endif]Burge,遞歸編程技術，Addison-Wesley,Reading, Mass., 1975.

[if !supportLists]5.????? [endif]W.

Dijkstra,一門編程學科，Prentice Hall, Englewood Cliffs, N.J.,1976.

[if !supportLists]6.????? [endif]L.

Graham, D. E. Knuth, and O. Patashnik,具體的數(shù)學巫湘，Addison-Wesley, Reading,Mass., 1989.

[if !supportLists]7.????? [endif]Gries,編程科學尚氛，Springer-Verlag,New York, 1981.

[if !supportLists]8.????? [endif]Helman

and R. Veroff, Walls and Mirrors:解決問題的中間語言及數(shù)據(jù)結構，2ded., Benjamin Cummings Publishing, Menlo Park, Calif., 1988.

[if !supportLists]9.????? [endif]W.

Kernighan and P. J. Plauger,編程風格的元素，2d ed., McGraw- Hill, NewYork, 1978.