AP 计算机科学 A

一个算法(algorithm)是一个解决一个问题的有限的、逐步的程序。一个程序(program)用一门计算机能运行的语言表达一个算法。Java 是编译(compiled)的:编译器(compiler)把你的源代码翻译成字节码(bytecode),它由 Java 虚拟机(JVM)(Java Virtual Machine)运行。一个语法错误(syntax error)(破坏语法)被编译器捕捉;一个逻辑错误(logic error)(错误的结果)不被——程序运行但行为不当。

一个变量(variable)是一个存储一个固定类型(type)的值的命名的盒子。Java 的主要基本类型(primitive types)是 int(整数)、double(小数)和 boolean(true/false)。类型在先地声明:

int score = 90;
double price = 4.99;
boolean passed = true;

一个表达式(expression)组合值和运算符(operators)来计算一个结果:+ - * / 和 %(取模(modulus),余数)。整数除法(integer division)截断:7 / 2 是 3,而 7 % 2 是 1。运算符优先级(operator precedence)遵循数学(*、/、% 在 +、- 之前)。用以下打印:

System.out.print("no newline");
System.out.println("with newline");

整数除以整数 0(像 7 / 0)是不允许的,在运行时以一个 ArithmeticException 崩溃。在一个字符串里,一个反斜杠标记一个转义序列(escape sequence):\" 打印一个双引号,\\ 一个单反斜杠,而 \n 开始一个新行——所以 System.out.println("She said \"hi\""); 打印 She said "hi"。

一个赋值(assignment)x = expr; 求右侧的值并把它存进左边的变量。用一个 Scanner 读输入:

Scanner in = new Scanner(System.in);
int age = in.nextInt();
String name = in.next();

每个类型有一个固定的范围;一个 int 超过约 21 亿溢出。类型转换(casting)在类型之间转换。加宽(int 到 double)是自动的;缩窄需要一个显式的转换,它截断(不舍入):

double avg = (double) total / count;   // force real division
int whole = (int) 3.9;                 // 3, truncated

考试技能: 注意整数除法在期望一个小数时产生一个截断的结果——先把一个操作数转换成 double。

Worked example. 跟踪每个表达式:

• 7 / 2 → 3(两个都是 int,所以除法截断);
• 7.0 / 2 → 3.5(一个 double 迫使实数除法);
• 7 % 2 → 1(余数);
• (double) 7 / 2 → 3.5(转换比 / 结合得更紧,所以它是 7.0 / 2);
• (double) (7 / 2) → 3.0(括号先以 int 计算 7 / 2 = 3,然后加宽)。

最后两个看起来相似但不同——转换的位置决定截断是否发生。

简写把一个运算与赋值结合:x += 5 意味着 x = x + 5;同样 -=、*=、/=、%=。自增(increment)和自减(decrement)运算符 x++ 和 x-- 加或减一。

一个 API(应用程序接口,Application Programming Interface)是你可以使用的类和方法的已发布列表。一个库(library)是一个现成类的搜集(像 Math、String、Scanner)。你读 API 文档以学一个方法需要什么(它的参数)和返回什么,而不看它的内部代码——抽象(abstraction)的一个例子。

注释(comments)被编译器忽略但向人类解释代码:// 用于单行、/* ... */ 用于一个块,而 /** ... */ 用于一个 Javadoc 注释,它记录一个方法的目的、参数和返回值。精确的前置条件(preconditions)和后置条件(postconditions)写在这里。

一个方法签名(method signature)是一个方法的名字加它的参数类型,例如 nextInt() 或 substring(int, int)。要调用一个方法你必须提供在数量、类型和顺序上匹配参数的实参(arguments)。完整的方法头也陈述返回类型(return type)——方法返回的值的类型(若没有则是 void)——但返回类型不是签名的一部分,这就是为什么两个方法不能仅凭返回类型不同来区分。

一个类(静态)方法(class (static) method)属于类本身,所以你在类名上调用它:ClassName.method(args)。不需要对象。

Math 类提供静态数学方法:Math.abs(x)、Math.pow(base, exp)、Math.sqrt(x),和 Math.random()($[0,1)$ 里的一个 double)。要得到一个从 0 到 n-1 的随机整数:(int)(Math.random() * n)。

一个类(class)是一个蓝图;一个对象(object)是从它构建的一个具体的实例(instance)。一个类把数据(字段)与行为(方法)捆绑——面向对象编程(object-oriented programming)的核心。String、Scanner 和 ArrayList 都是你实例化的类。

类可以被组织成一个层级。一个父类(superclass)持有几个子类(subclasses)共享的属性和行为,这些子类 extend(扩展)它——一个继承关系(inheritance relationship)。Java 里每个类最终都是内置 Object 类的一个子类,这就是为什么每个对象已经有一个 toString 方法;写一个与父类方法有相同签名的子类方法就是方法重写(method overriding)。(设计你自己的继承超出本课程,但你要能识别这些词汇。)

实例化(instantiation)用 new 关键字创建一个对象,它调用一个构造函数(constructor):

Scanner in = new Scanner(System.in);
String s = new String("hi");   // or just "hi"

变量持有一个引用(reference)(对象的地址),不是对象本身。两个引用能指向同一个对象;用 == 比较它们比较地址,不是内容。

一个引用也能指向空:特殊值 null(空值)意味着“不附着于任何对象”。在一个 null 引用上调用一个方法会在运行时以一个 NullPointerException 崩溃。通过用 ==/!= 测试并先检查 null 来防范,这样 && 在方法运行前短路:if (s != null && s.length() > 0)。

一个实例方法(instance method)作用于一个特定的对象,所以你在对象引用上调用它:object.method(args)。例:in.nextInt()、word.length()。

String 对象是不可变(immutable)的——方法返回一个新字符串而不是改变原来的。关键方法(所有索引从 0 开始):

s.length();            // number of characters
s.substring(2, 5);     // chars at index 2,3,4 (5 excluded)
s.indexOf("ab");       // first position, or -1
s.equals(other);       // content comparison (never use == for Strings)
s.compareTo(other);    // <0, 0, >0 by dictionary order

考试技能: substring(a, b) 包括索引 a 但排除 b,而字符串比较必须用 .equals,不是 == ——两个最被考查的字符串陷阱。

Worked example. 令 String s = "COMPUTER";(索引 0–7)。那么 s.length() 是 8;s.substring(0, 4) 是 "COMP"(索引 0,1,2,3 ——索引 4 被排除);s.substring(4) 是 "UTER"(从索引 4 到末尾);s.indexOf("PU") 是 3;而 s.indexOf("X") 是 -1(未找到)。数 substring 被排除的端点是单个最常见的失误。

请求一个在 0 到 length()-1 之外的索引(一个坏的 substring 或 charAt 参数,例如这里的 s.substring(0, 20))会以一个 StringIndexOutOfBoundsException 崩溃——数组索引错误的字符串表亲。

• 逐行手工跟踪代码,在一张表里追踪每个变量的值——考试奖励仔细的跟踪而不是猜测。
• 知道 Java 的基本类型以及整数除法截断($7/2$ 给出 $3$);用一个转换或一个 double 做实数除法。
• 区分编译时错误(语法、类型)和运行时错误——知道有名字的那些:ArithmeticException(int ÷ 0)、NullPointerException(在 null 引用上的方法)、StringIndexOutOfBoundsException / ArrayIndexOutOfBoundsException——和逻辑错误(错误的输出)。
• 遵循运算符优先级并在你使用每个变量之前初始化它。
• 在自由回答上,写完整的、可编译的 Java ——返回正确的类型并精确匹配方法头。

算法由三种控制结构(control structures)构建:顺序(sequence)(按顺序的步骤)、选择(selection)(选择一条路径),和迭代(iteration)(重复步骤)。这个主题涵盖选择和迭代——让一个程序做决定和循环的工具。

一个布尔表达式(boolean expression)求值为 true 或 false,用关系运算符(relational operators):==(相等)、!=(不相等)、<、>、<=、>=。注意 == 比较基本值但对对象比较对象引用,所以对 String 用 .equals。

一个条件语句(if statement)只在它的条件为真时运行一个块;一个可选的 else 给出一个替代:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

把一个 if 放进另一个里面,或用 else if 链接,按顺序测试几个情况。只有第一个匹配的分支运行:

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

逻辑运算符(logical operators)组合条件:&&(与——两者都真)、||(或——至少一个真)、!(非——反转)。Java 用短路求值(short-circuit evaluation):&& 若左侧为假则停止,而 || 若左侧为真则停止——对防止错误有用,例如 if (n != 0 && total / n > 5)。

德摩根定律(De Morgan's laws)重写否定:!(a && b) 等于 !a || !b,而 !(a || b) 等于 !a && !b。两个布尔表达式等价,若它们对每个输入给出相同的结果——一张真值表证明它。以这种方式化简条件是一个常见的考试任务。

一个循环(while loop)在它的条件保持为真时当……时重复,在每一趟之前测试。你必须在里面改变某样东西以便循环最终停止,否则它变成一个无限循环(infinite loop):

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

一个 for 循环(for loop)把初始化、条件和更新打包进一行——当你知道次数时最好:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

一个 for 和一个等价的 while 做相同的工作;能够在它们之间转换。

组合循环和条件来解决真实的问题——计数、求和、找一个最大值,或测试一个性质:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

有两个整数模式,考试会直接考,它们用 % 和 /。要一次一个地读出一个整数的各位数字,反复取 n % 10(最后一位)然后 n = n / 10(把它去掉)。要测试整除性,n % d == 0 表示 n 能被 d 整除。把它们和一个计数器结合起来,就能求出某个标准被满足的频率。

像一个连续总计、一个计数器,或一个标志(flag)(一个记录某事是否发生的布尔值)这样的标准模式贯穿整个课程重现。

按索引循环遍历一个字符串以处理每个字符:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

典型的任务:计数出现、构建一个反转或过滤的副本,或测试一个字符串是否包含另一个。

一个嵌套循环(nested loop)把一个循环放进另一个里面;内层循环对外层的每一趟完全完成。若外层运行 $n$ 次而内层 $m$ 次,主体运行 $n\times m$ 次——处理网格和比较所有对的基础。

运行时间分析(run-time analysis)数一个算法随着输入大小 $n$ 增长取多少基本步骤。数最内层语句的执行:一个遍历 $n$ 个项的单一循环是线性的($n$ 步);两个遍历 $n$ 的嵌套循环是二次的($n^2$)。这种非正式的计数让你能比较两个算法的效率。

考试技能: 对于一个嵌套循环,能够以循环边界陈述内层语句运行多少次——一个频繁的选择题。

Worked example. 这个打印多少个星?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

内层循环对每个外层 i 运行 i 次:0 + 1 + 2 + 3 = 6 个星。当内层边界是外层变量时,总数是三角和 $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ ——这里 $\dfrac{4\times3}{2}=6$ ——不是一个矩形嵌套循环的完整 $n^2=16$。

• 把边界条件搞对:有意地用 < vs <=,并注意每个循环的第一次和最后一次迭代(差一是经典的 bug)。
• 用 &&、||、! 构建复合条件并记住短路求值(把 null 检查放在先)。
• 通过数内层主体总共运行多少次来跟踪嵌套循环。
• 选择正确的结构——if/else if 用于范围、一个循环用于重复——并通过更新循环变量避免一个无限循环。
• 当你化简或否定一个布尔条件时应用德摩根定律。

抽象(abstraction)意味着把细节隐藏在一个简单的接口之后——你使用一个 String 而不知道它如何存储字符。好的设计把一个问题分解成类,每个负责一个思想。这个主题是关于写你自己的类。

设计选择影响代码是否正确、可读和可重用。封装(encapsulation)——保持数据私有并只通过方法暴露它——保护一个对象的状态免于误用,并让你在不破坏类的用户的情况下改变里面。深思熟虑的命名、单一目的的方法和测试减少 bug。

设计还承担着代码之外的责任。系统可靠性(system reliability) - 一个程序按预期完成任务、不出故障 - 是程序员应当通过精心的设计和测试去最大化的。程序对社会、经济和文化有真实的影响,这些影响既可以有益也可以有害。而且创造程序会引发法律和知识产权(intellectual property)方面的顾虑:程序员常常重用作为开源(open source)发布、可免费使用的代码,但必须尊重它的许可证并给出署名,而不是把他人的成果当作自己的来抄。

一个类有三个部分:实例变量(instance variables)(字段——对象的数据)、构造函数(constructors)(构建对象),和方法(methods)(行为)。字段通常是 private;方法通常是 public:

public class Student {
    private String name;      // instance variable
    private int score;

    public Student(String n, int s) {   // constructor
        name = n;
        score = s;
    }
    public int getScore() { return score; }   // accessor
}

一个构造函数(constructor)有与类相同的名字且没有返回类型。它在你写 new 时运行,而它的工作是初始化字段。一个类能有几个带不同参数列表的构造函数(重载(overloading));一个无参数构造函数设置默认值。

一个方法有一个签名、一个返回类型和一个主体。一个访问器(getter)(accessor)返回信息而不改变对象;一个修改器(setter)(mutator)改变一个字段。一个返回一个值的方法必须在每条路径上有一个正确类型的 return;一个 void 方法什么都不返回。

public void setScore(int s) { score = s; }   // mutator
public String toString() { return name + ": " + score; }

当你把一个对象传给一个方法时,Java 复制引用,所以方法作用于同一个对象——对它字段的变化对调用者可见。(基本类型按值复制,所以对它们的变化不可见。)一个方法也能返回一个对象的引用。因为一个 String 是不可变的,传一个是安全的;传一个可变的对象让一个方法能改变它。

考试技能: 知道在一个方法里面改变一个对象的字段影响原来的,但重新赋值参数(param = new...)不影响调用者。

Worked example. 假设 s 是一个分数为 50 的 Student,而我们调用 tweak(s):

public static void tweak(Student a) {
    a.setScore(100);          // (1) mutates the shared object
    a = new Student("Z", 0);  // (2) repoints the local copy only
    a.setScore(5);            // (3) changes only the new local object
}

第 (1) 行改变 s 指向的对象,所以调用者现在看到 100。第 (2) 行使方法自己的引用副本指向一个新的对象——调用者的 s 不受影响——而第 (3) 行只影响那个新对象。调用之后,s.getScore() 是 100:改变留住了,重新赋值没有。

一个静态(类)变量(static (class) variable),标记 static,被类的所有对象共享——总共一个副本(例如一个存在多少对象的计数器)。一个静态方法属于类而不能直接使用实例字段。按类名访问它们:Student.getCount()。

作用域(scope)是一个名字可见的地方。一个在一个方法里声明的局部变量(local variable)只在它里面存在;一个参数(parameter)只在它的方法里存在;一个实例变量(instance variable)在整个对象里可见。访问修饰符控制跨类的可见性:private(只这个类)与 public(任何地方)。局部变量遮蔽(shadow)同名的字段——一个 bug 的来源。

this 是对当前对象的一个引用。用它来把一个字段与一个同名的参数区分开,或调用同一对象的另一个方法:

public Student(String name, int score) {
    this.name = name;      // this.name is the field; name is the parameter
    this.score = score;
}

考试技能: 当一个构造函数或 setter 的参数与一个字段同名时,你必须写 this.field = param ——没有 this,赋值什么有用的都不做。

• 用方法和类设计:把数据封装为 private 字段并通过公有方法暴露行为。
• 知道一个对象和它的类之间的差别,以及对象按值传递——参数得到引用的一个副本,所以一个方法能改变对象的状态,但重新赋值参数不影响调用者(Java 没有按引用传递)。
• 安全地遍历数组和 ArrayList ——大小是 length vs .size(),而在一个循环期间移除会移动索引。
• 跟踪一个递归方法以确定它的结果:先找到基本情况,然后沿着每次递归调用到它的返回值(写递归代码不在考试范围内)。
• 认识继承词汇——超类、子类、方法重写,以及每个类都是 Object 的子类(设计和实现继承不在考试范围内)。

收集数据的程序提出隐私(privacy)和同意(consent)的问题。只收集需要的、保护它,并对它的使用诚实。数据能携带偏见(bias),若它不公平地代表每个人,导致不公平的结果——一个随着存储信息而来的责任。

一个单一的变量持有一个值;真实的问题需要存储许多相关的值——一个班级名册、像素、传感器读数。一个数据结构(data structure)组织一个搜集,以便我们能高效地存储、找到和处理项。AP 课程用三个:数组(array)、ArrayList,和 2D 数组。

一个数组(array)是一个固定大小的、有序的相同类型值的搜集。索引从 0 到 length - 1:

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

访问 0..length-1 之外的一个索引抛出一个 ArrayIndexOutOfBoundsException。

用一个 for 循环(给出索引)或一个增强 for / for-each(enhanced for / for-each)循环(给出每个值,只读)遍历(traverse)一个数组:

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

掌握这些模式:计算一个和或平均、找最大/最小、计数满足一个条件的项、检查一个重复,和反转或移位元素。每一个都是一个带连续结果的遍历:

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

File 和 IOException 在 java.io 里,所以一个读文件的程序需要 import java.io.*;。打开一个文件可能失败(它也许不存在),Java 强制你处理这一点——最简单的方式是在方法头上加 throws IOException。然后一个 Scanner 逐行读文件,用 hasNext... 在读之前测试:

import java.io.*;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

用 nextInt()、nextDouble() 或 nextBoolean() 读有类型的记号时,如果下一个记号是错误的类型,会抛出一个 InputMismatchException——例如当文件里下一个东西是单词 cat 时调用 nextInt()。

一个 ArrayList 存储对象,不是基本类型,所以一个基本类型被包装在一个对象里:Integer 包装 int,Double 包装 double。Java 用自动装箱(autoboxing)(int 到 Integer)和拆箱(unboxing)(再回去)自动做这个,所以你能写 list.add(5) 和 int x = list.get(0)。

一个 ArrayList(动态数组)在你添加或移除项时增长和收缩。用 <> 里的元素类型声明它:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

用一个索引循环或一个 for-each 循环遍历,就像数组(用 size() 和 get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

考试技能: 当在一个索引循环里移除项时,要么向后循环,要么在一次移除之后不递增 i ——否则移除会把元素向左移动而你跳过一个。而且绝不要在用一个 for-each 循环遍历一个 ArrayList 时添加或移除元素:在循环中途改变它的大小会抛出一个 ConcurrentModificationException,所以每当你必须移除时用一个索引循环(向后,如上)。

与数组相同的算法——最大/最小、计数、求和——加上数组不能轻易做的插入和删除。一个常见的任务是移除所有匹配一个条件的元素,小心地处理索引移位。

一个 2D 数组(2D array)是一个网格(行和列)——一个数组的数组:

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

用嵌套循环(nested loops)访问每个单元格——外层遍历行、内层遍历列(行主序(row-major order)):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

典型的网格任务:求一行或一列的和、找网格里的最大值、计数匹配的单元格,或求一条对角线的和(r == c 的地方)。每一个都是一个带连续结果的嵌套遍历。

• 线性搜索(linear search)依次检查每个元素——在任何列表上起作用,取最多 $n$ 步。
• 二分搜索(binary search)只在一个排序的列表上起作用:检查中间、然后丢弃不能包含目标的那一半,重复。它取约 $\log_2 n$ 步——在大数据上快得多。

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

考试技能: 二分搜索需要排序的数据;知道它做多少次比较以及 lo、hi、mid 如何更新。

Worked example. 在排序的数组 {3, 9, 14, 23, 31, 42, 55}(索引 0–6)里搜索 target = 40。开始 lo=0, hi=6:

• mid = (0+6)/2 = 3,a[3]=23 < 40,所以 lo = 4;
• mid = (4+6)/2 = 5,a[5]=42 > 40,所以 hi = 4;
• mid = (4+4)/2 = 4,a[4]=31 < 40,所以 lo = 5;
• 现在 lo (5) > hi (4),所以循环结束——40 不存在。

每一步把范围减半,所以即使这次未命中也只取三次比较。

• 选择排序(selection sort)反复找到最小的剩余元素并把它交换到位。
• 插入排序(insertion sort)增长一个排序的前部,把每个新元素插入到它所属的地方。

两者都简单,平均取约 $n^2$ 步——对小数组还行。能够跟踪每一趟之后的数组。

递归(recursion)是一个在一个更小的输入上调用它自己的方法。它需要一个停止调用的基本情况(base case),和一个朝基本情况移动的递归情况(recursive case):

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

没有一个可达的基本情况,递归从不停止(一个栈溢出)。

递归和迭代是可以互换的。任何递归解法都能用一个循环(迭代方式)改写,而任何循环也都能用递归改写 —— 它们解决的是同一类问题。上面的 factorial 与一个迭代版本效果完全相同:

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

所以这个选择关乎清晰度,而非能力:对于具有自相似结构的问题(树、归并排序),递归读起来很自然;而迭代则避免了每一步都压入一个调用帧的内存开销。考试可能会要求你把其中一种转换成另一种。

递归驱动高效的算法。二分搜索能被递归地写(搜索正确的那一半)。归并排序(merge sort)把数组分成一半、递归地排序每一半,然后归并两个排序的一半——取约 $n\log_2 n$ 步,在大数据上比选择或插入排序快得多。

Worked example. 跟踪 factorial(4)。每个调用推迟给一个更小的:factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1)。factorial(1) 命中基本情况并返回 1,所以调用向内展开:2 * 1 = 2,然后 3 * 2 = 6,然后 4 * 6 = 24。把每个调用写在它返回值的上方是跟踪递归的可靠方式。

考试技能: 通过写出每个调用和它的返回值来跟踪一个递归方法,并知道归并排序的效率($n\log n$)击败 $n^2$ 的简单排序。

• 权衡收集数据的好处和害处——这个单元通过简短的书面论证考查,不是代码。
• 保护个人身份信息(PII)(personally identifiable information)并在上下文里解释隐私和安全风险。
• 命名真实的害处:数据泄露、监视,和来自不具代表性数据的算法偏见。
• 当你重用代码或数据时尊重知识产权和许可。
• 给出一个具体的、有理由的答案——一个模糊的"它可能是坏的"不赢得分数。