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
简介
在这章中，我们讨论这本书的目标和目的，然后简单回顾一下编程概念以及离散数学。我们将
- 看到一个程序在大量合法输入的运行情况和适量合法输入的运行情况是一样重要的
- 为这本书的剩余部分总结基本的数学背景需求
- 简要介绍一下递归
- 总结这本书中通篇使用到的一些重要的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.
假设你有一组N个数字，然后要找出第k大的值。这被称为选择选择排序问题。对大多数已经有一两门编程课程的学生来说，写一个程序去解决这个问题没有一点困难。有不少明显的解决方案。
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个数字读进一个数组中，然后使用一些简单的算法对数组进行降序排序，比如冒泡排序算法，然后返回数组中第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("排序前数组为：");
for (int num : arr) {
System.out.print(num + " ");
}
for (int i = 0; i < arr.length - 1; i++) {//外层循环控制排序趟数
for (int j = 0; j < arr.length - 1 - i; j++) {//内层循环控制每一趟排序多少次
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("排序后的数组为：");
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个元素到一个数组中并对其进行降序排序。然后，一个一个读剩下的元素。当一个新的元素到达是，判断如果它小于数组中的第k个元素，就忽略它。否则这个元素就放到数组中正确的位置。挤出数组中原来的一个元素。当算法结束，数组中第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("排序前数组为：");
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++) {//外层循环控制排序趟数
for (int j = 0; j < tempArr.length - 1 - i; j++) {//内层循环控制每一趟排序多少次
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.
两种算法都很容易编码，并且鼓励你去实现。很自然的问题是，哪一个算法更好，更重要一些？是否有一种算法足够好？使用了一个包含3000万元素的文件，指定k等于1500万的模拟表明没有一种算符在一个合理的时间内结束，每种算法都要耗费几天的时间去计算（即使最终都能获得一个正确的结果）。另一个供选择的将在第7章讨论的方法，给出的解决方法大概需要1秒钟。因此，我们我们提议的算法，都不能被认为是一个好的算法，因为他们对上面的输入来说，完全不切实际，并且第三种算法可以在一个合理的时间内处理这种情况。
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)
第二个问题是解决流行的猜字谜的问题。输入是由字母组成的二维数组和一个单词列表。目的是找出迷宫中的单词。这些单词可能是横向、纵向或者斜向任何一个方向。举一个例子，图标1.1显示的谜题包含 this,two,fat,that这些单词。单词this从行1，列1或者叫（1,1）延伸至（1,4)。two 从（1,1)出发到(3,1);fat 从（4,1)出发到（2,3);that 从（4,4)出发到(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.
再次，有两种简单的算法来解决这个问题。对列表中的每个单词，我们检查有序的三元组（横，竖，斜）来找出存在的单词。这相当于很多的嵌套的for循环，但基本上很简单。
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.
另外，对每个没有跑出迷宫的有序四元组(行，列，方向，字符个数)，我们可以测试这个单词是否在单词列表中。再次，这相当于很多嵌套的for循环。如果每个单词的最大字符数已经知道了的话，可能会节省很多时间
