Introduction

In this chapter,we discuss the aims and goals of this text and briefly review programing concepts and discrete mathematics.We will

• See that how a program performs for reasonably large input is just as important as its performance on moderate amounts of input.
• Summarize the basic mathematical background needed for the rest of the book.
• Briefly review recursion
• Summarize some important features of Java that are used throughout the text

簡(jiǎn)介

在這章中，我們討論這本書的目標(biāo)和目的，然后簡(jiǎn)單回顧一下編程概念以及離散數(shù)學(xué)。我們將

• 看到一個(gè)程序在大量合法輸入的運(yùn)行情況和適量合法輸入的運(yùn)行情況是一樣重要的
• 為這本書的剩余部分總結(jié)基本的數(shù)學(xué)背景需求
• 簡(jiǎn)要介紹一下遞歸
• 總結(jié)這本書中通篇使用到的一些重要的Java特性

1.1 What's the Book About?

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

假設(shè)你有一組N個(gè)數(shù)字，然后要找出第k大的值。這被稱為選擇選擇排序問題。對(duì)大多數(shù)已經(jīng)有一兩門編程課程的學(xué)生來說，寫一個(gè)程序去解決這個(gè)問題沒有一點(diǎn)困難。有不少明顯的解決方案。

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

一種解決方法就是將這N個(gè)數(shù)字讀進(jìn)一個(gè)數(shù)組中，然后使用一些簡(jiǎn)單的算法對(duì)數(shù)組進(jìn)行降序排序，比如冒泡排序算法，然后返回?cái)?shù)組中第k個(gè)值。

package com.lin.data.structure;

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1};
        int k = 3;
        System.out.println("排序前數(shù)組為：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        for (int i = 0; i < arr.length - 1; i++) {//外層循環(huán)控制排序趟數(shù)
            for (int j = 0; j < arr.length - 1 - i; j++) {//內(nèi)層循環(huán)控制每一趟排序多少次
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println();

        System.out.println("排序后的數(shù)組為：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        System.out.println("第"+k+"大的元素為:"+arr[k-1]);
    }
}

A somewhat better algorithm might be to read 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,it is ignored if it is smaller than the kth element in the array.Otherwise ,it is placed 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 the answer.

一種多少更好的算法可能是首先讀k個(gè)元素到一個(gè)數(shù)組中并對(duì)其進(jìn)行降序排序。然后，一個(gè)一個(gè)讀剩下的元素。當(dāng)一個(gè)新的元素到達(dá)是，判斷如果它小于數(shù)組中的第k個(gè)元素，就忽略它。否則這個(gè)元素就放到數(shù)組中正確的位置。擠出數(shù)組中原來的一個(gè)元素。當(dāng)算法結(jié)束，數(shù)組中第k個(gè)元素將作為答案返回。

package com.lin.data.structure;

public class PumpingTest {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1};
        int k = 3;
        System.out.println("排序前數(shù)組為：");
        for (int num : arr) {
            System.out.print(num + " ");
        }


        int[] tempArr = new int[k];
        for (int i=0;i<k;i++){
            tempArr[i] = arr[i];
        }


        bubbleSort(tempArr);

        for (int i=k;i<arr.length;i++){
            if (arr[i] < tempArr[k-1]){
                continue;
            }else {
                tempArr[k-1] = arr[i];
                bubbleSort(tempArr);
            }
        }

        System.out.println();
        System.out.println("第k大的元素"+tempArr[k-1]);
    }

    public static void bubbleSort(int[] tempArr){
        for (int i = 0; i < tempArr.length - 1; i++) {//外層循環(huán)控制排序趟數(shù)
            for (int j = 0; j < tempArr.length - 1 - i; j++) {//內(nèi)層循環(huán)控制每一趟排序多少次
                if (tempArr[j] < tempArr[j + 1]) {
                    int temp = tempArr[j];
                    tempArr[j] = tempArr[j + 1];
                    tempArr[j + 1] = temp;
                }
            }
        }

    }
}

Both algorithms are simple to code,and you are encouraged to do so.The natural questions,then,are whick algorithm is better and ,more important,is either algorithm good enough?A simulation using a random file of 30 million elements and k = 15,000,000 will show that neither algorithm finishes in a reasonable amount of time;each requires several days of computer processing to terminate(albeit eventually which a correct answer).An alternative method,discussed in Chapter 7,gives a solution in about a second.Thus although our proposed algorithms work,they cannot be considered good algorithms,because they are entirely impractical for input sizes that a third algorithm can handle in a reasonable amount of time.

兩種算法都很容易編碼，并且鼓勵(lì)你去實(shí)現(xiàn)。很自然的問題是，哪一個(gè)算法更好，更重要一些？是否有一種算法足夠好？使用了一個(gè)包含3000萬元素的文件，指定k等于1500萬的模擬表明沒有一種算符在一個(gè)合理的時(shí)間內(nèi)結(jié)束，每種算法都要耗費(fèi)幾天的時(shí)間去計(jì)算（即使最終都能獲得一個(gè)正確的結(jié)果）。另一個(gè)供選擇的將在第7章討論的方法，給出的解決方法大概需要1秒鐘。因此，我們我們提議的算法，都不能被認(rèn)為是一個(gè)好的算法，因?yàn)樗麄儗?duì)上面的輸入來說，完全不切實(shí)際，并且第三種算法可以在一個(gè)合理的時(shí)間內(nèi)處理這種情況。

猜字謎游戲

A second problem is to solve a popular world puzzle. The input consists of a two-dimensional array of letters and a list of words.The object is to find the words in the puzzle.These words may be horizontal,vertical,or diagonal in any direction.As an example ,the puzzle shown in Figure 1.1 contains these words this,two,fat,and that.The word this begins at row 1,column 1,or (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)

第二個(gè)問題是解決流行的猜字謎的問題。輸入是由字母組成的二維數(shù)組和一個(gè)單詞列表。目的是找出迷宮中的單詞。這些單詞可能是橫向、縱向或者斜向任何一個(gè)方向。舉一個(gè)例子，圖標(biāo)1.1顯示的謎題包含 this,two,fat,that這些單詞。單詞this從行1，列1或者叫（1,1）延伸至（1,4)。two 從（1,1)出發(fā)到(3,1);fat 從（4,1)出發(fā)到（2,3);that 從（4,4)出發(fā)到(1,1)。

Again ,there are at least two straightforward algorithms that solve the problem. For each word in the word list, we check each ordered triple(row,column,orientation) for the presence of the word. The amounts to lots of nested for loops but is basically straightforward.

再次，有兩種簡(jiǎn)單的算法來解決這個(gè)問題。對(duì)列表中的每個(gè)單詞，我們檢查有序的三元組（橫，豎，斜）來找出存在的單詞。這相當(dāng)于很多的嵌套的for循環(huán)，但基本上很簡(jiǎn)單。

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

另外，對(duì)每個(gè)沒有跑出迷宮的有序四元組(行，列，方向，字符個(gè)數(shù))，我們可以測(cè)試這個(gè)單詞是否在單詞列表中。再次，這相當(dāng)于很多嵌套的for循環(huán)。如果每個(gè)單詞的最大字符數(shù)已經(jīng)知道了的話，可能會(huì)節(jié)省很多時(shí)間