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
簡介
在這章中筛欢，我們討論這本書的目標(biāo)和目的纵揍，然后簡單回顧一下編程概念以及離散數(shù)學(xué)宇植。我們將
- 看到一個程序在大量合法輸入的運(yùn)行情況和適量合法輸入的運(yùn)行情況是一樣重要的
- 為這本書的剩余部分總結(jié)基本的數(shù)學(xué)背景需求
- 簡要介紹一下遞歸
- 總結(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個數(shù)字工猜，然后要找出第k大的值日裙。這被稱為選擇選擇排序問題弦疮。對大多數(shù)已經(jīng)有一兩門編程課程的學(xué)生來說阻肩，寫一個程序去解決這個問題沒有一點(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個數(shù)字讀進(jìn)一個數(shù)組中，然后使用一些簡單的算法對數(shù)組進(jìn)行降序排序够颠，比如冒泡排序算法熙侍，然后返回數(shù)組中第k個值。
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個元素到一個數(shù)組中并對其進(jìn)行降序排序履磨。然后蛉抓，一個一個讀剩下的元素。當(dāng)一個新的元素到達(dá)是剃诅，判斷如果它小于數(shù)組中的第k個元素巷送，就忽略它。否則這個元素就放到數(shù)組中正確的位置矛辕。擠出數(shù)組中原來的一個元素笑跛。當(dāng)算法結(jié)束付魔，數(shù)組中第k個元素將作為答案返回。
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.
兩種算法都很容易編碼飞蹂，并且鼓勵你去實現(xiàn)几苍。很自然的問題是，哪一個算法更好陈哑，更重要一些妻坝？是否有一種算法足夠好？使用了一個包含3000萬元素的文件芥颈，指定k等于1500萬的模擬表明沒有一種算符在一個合理的時間內(nèi)結(jié)束惠勒，每種算法都要耗費(fèi)幾天的時間去計算（即使最終都能獲得一個正確的結(jié)果）。另一個供選擇的將在第7章討論的方法爬坑，給出的解決方法大概需要1秒鐘纠屋。因此，我們我們提議的算法盾计，都不能被認(rèn)為是一個好的算法售担，因為他們對上面的輸入來說，完全不切實際署辉，并且第三種算法可以在一個合理的時間內(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)
第二個問題是解決流行的猜字謎的問題。輸入是由字母組成的二維數(shù)組和一個單詞列表哭尝。目的是找出迷宮中的單詞哥攘。這些單詞可能是橫向、縱向或者斜向任何一個方向材鹦。舉一個例子逝淹，圖標(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.
再次尤泽，有兩種簡單的算法來解決這個問題欣簇。對列表中的每個單詞，我們檢查有序的三元組（橫坯约，豎熊咽，斜）來找出存在的單詞。這相當(dāng)于很多的嵌套的for循環(huá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.
另外，對每個沒有跑出迷宮的有序四元組(行妇智，列滥玷，方向，字符個數(shù))巍棱，我們可以測試這個單詞是否在單詞列表中惑畴。再次，這相當(dāng)于很多嵌套的for循環(huán)航徙。如果每個單詞的最大字符數(shù)已經(jīng)知道了的話如贷，可能會節(jié)省很多時間
