AP CS复习（2）- Math和Random基础

本来就不是什么高产的人，但是由于AP里面会有一些琐碎的小点，所以干脆简洁的介绍一下。今天讲的就是 java.lang.math 和 java.util.Random 这两个小点。这些方法大家应该都大致懂得使用，所以过一遍就好了。

AP考什么?


按照惯例，先上个传送门：College Board AP CS

Java.lang.Math 会考：

1
2
3
4
5
static int abs(int x);
static double abs(double x);
static double pow(double base, double exponent);
static double sqrt(double x);
static double random();


Java.util.Random 会考（其实是FRQ会考）：
1
void nextInt(int bound);


将这两个类放在一起讲主要是因为他都可以生成伪随机数字（伪随机会在后面重点提到）。这在回答一些AP FRQ时极为重要。

> 对于Math的类的其他方法，下面简略用实例一一演示

static int abs(int x / double x)


1
2
3
4
int x = -20;
//返回int x的绝对值
int y = Math.abs(x); // y = 20
//double 同理


这个方法要自己实现也是非常之简单的，只需要通过if-else判断数字的正负然后一律改为正数就可以了：
1
2
3
4
5
//source源码
public static int abs(int x) {
    if (x < 0) return -x;
    return x;
}


没什么好说的。。。其实AP里面真正要考这个方法的也不多。

static double pow(double base, double exponent)


Java中基本的operators很难做到十进制上的乘方操作。
P.S. 在二进制层面是可以做到的，如移位运算符
1
2
3
4
5
6
int x = 3;
//表达式<< 3意味着将x的二进制表示向左平移3位，也就是乘以2^3
//原本：00011 -> 对应十进制3
//改变：11000 -> 对应十进制24
x = x << 3;
System.out.println(x); //结果为3*2^3=24


但是通过递归或者遍历的方法，可以做到乘方的操作，这也是Math.pow()方法的实现基础（但事实上pow方法调用了C语言完成，并不是一个java本身方法）。
1
2
3
4
//计算2^5
//虽然参数是double，可以直接传入int值，因为java中int可以被自动转型成double
double x = Math.pow(2.0, 5.0);
System.out.println(x); //输出32.0


可以试着用递归的办法实现这个方法的简略版：
1
2
3
4
5
6
public static double powWithRecursion(double base, double expo) {
    //任何数零次方为1
    if (expo==0) return 1;
    if (expo==1) return base;
    else return powWithRecursion(base, expo-1);
}


分析一下上述方法，要求传入的expo必须是positive integer（虽然写着是double），不然就会抛出 StackOverFlowError 。但至少，我们可以利用自己的知识实现一个高级的方法了。


static double sqrt(double x)


顾名思义，这是一个求平方根的操作，在AP考试里考的也不多。要注意的是，当传入的参数为负时，不会抛出 runtimeException , 返回的结果却也并不是一般的double数字，而是一个静态常量NaN（not a number）。
在double类中，这个NaN是这样被定义的：
1
public static final double NaN = 0.0d / 0.0;


除了分母为0之外，更神奇的是，这个常量自己与自己不想等，可谓是六亲不认！
1
2
3
boolean b = (Double.NaN == Double.NaN);
System.out.println(b); //false;
//所以唯一用于判断NaN的办法是Double.isNaN();


在这个特例之外，sqrt方法就兢兢业业的返回输入数字的平方根，仅此而已了。


———-
在讲Random有关的方法之前，这里也稍作延伸，再简略补充几个Math类中的方法，并且讲一下使用它的注意事项。
上代码：
1
2
3
4
5
Math.max(20,30); //取最大数字30
Math.min(20,30); //取最小数字20
Math.round(20.3); //四舍五入取20
double e = Math.E; //2.718...常量
double pie = Math.PI; //3.14159...常量


这里尤为注意的是最后两个静态常量值π和e，善于使用系统给定好的常量是java编程的一个非常好的习惯。这里顺带提一下魔法值（magic number）的概念：

代码实例1：
1
2
3
public static double getCirclePerimeter(double radius) {
    return 6.28318*radius;
}


这是一个通过输入半径计算圆周长的简单方法 （C=2πr） 。然而不认真看，你会惊讶：这个6.28318是哪里来的？这是什么鬼？ 哦，想了好久才发现这是3.14159和2的乘积啊！这样的数字，既不是类的成员常量，在方法内部也没有local variable承载，就像是魔术师突然变出来的一样，给阅读代码的人增添很多麻烦！
所以这样的代码是要尽力避免的！

代码实例2：
1
2
3
public static double getCirclePerimeter(double radius) {
    return 2*Math.PI*radius;
}


是不是清晰明了多了？ Math.PI 清晰，易读，即使不用注释也可以让阅读者轻松理解。何况Math类中的π的精准度极高，足够应付大多数计算场景。




———-


Math类和异常


这是第二个有趣且需要强调的点。我们来复习一遍：

在Java中的Exception分为Checked和Unchecked两种，其中运行时异常 （RuntimeException） 属于 unchecked exception。并且，Java强制规定所有的 checked exception 都需要用某种方式处理（try/catch或者throws）。具体关于Java异常的知识AP不做过多要求，之后可能单独写博客总结。

显而易见，在Math类中很多情况我们要考虑参数所造成的异常（如负数开方/除0），而且这些异常在编译期间都是不会捕获的，只能等到 runtime 才能看得出来。这就是为什么比较有名的 ArithmaticException 是运行时异常的原因了，编译器也不会提醒你去捕获。

那么在写代码的时候（AP考试之外），就要自己留意参数了，不要想指望IDE来帮助你。

Random方法和伪随机


我们先来看一下Math.random方法：
1
2
3
4
5
/*
/没有参数
/返回一个在[0，1)之间的浮点值（左闭右开），如0.7762457478958932
*/
public static double random();


看得出来，这个random出来的double值是很难直接使用的。一般来讲，如果要生成0到100之间的整数，我们可以这样做：
1
2
//由于右边为开区间，故乘以100+1=101
int num = (int) (Math.random()*101);


上述操作先放大random值的倍数，然后转型为int。AP中有类似的考法，重点就在于理解其开闭区间的性质和放大的方法。

相比之下，Random类的操作就更加方便。下面是Random类的两个构造函数，其中第二个我们会重点讲：
1
2
Random random = new Random();
Random random = new Random(long seed);


使用上面，我们可以利用 nextInt(int bound) 方法得到随机数, 返回一个0到bound-1之间的整数（也是左闭右开）。

在AP考试中，有可能我们要设计一个这样的方法：
一个盒子中有很多球（使用一个ArrayList装载），然后不放回的随机从中抽球。

下面展示random在这个方法中的使用：
1
2
3
4
5
6
7
8
9
10
11
12
13
public class box {
    private Random random = new Random();
    private List<Ball> list;
    //构造方法中传入一个装有球的arraylist
    public box(ArrayList<Ball> list) {
        this.list = list;
    }
    //保证不放回的取出球。
    public Ball pickBall() {
        Ball pick = this.list.remove(random.nextInt(list.length));
        return pick;
    }
}


上面pickBall方法里的一调用看懂了吧。通过巧妙的使用list.length作为生成随机数的上界，可以保证不会出现list取出球之后长度变短，进而导致 indexOutOfBoundException。


———-

最后的最后，稍微延伸一下，讲一下编程中的伪随机概念。我们先有趣的设计一个代码，其中我们使用了Random的第二个构造函数（传入一个long seed）:
1
2
3
4
5
6
7
Random ran1 = new Random(100);
Random ran2 = new Random(100);

for (int i = 0; i < 5; i++) {
    System.out.println("第一个随机的第" +i+"个数字： "+ran1.nextInt(10));
    System.out.println("第二个随机的第" +i+"个数字： "+ran2.nextInt(10));
}


结果令人震惊！！！
1
2
3
4
5
6
7
8
9
10
第一个random的第0个数字： 5
第二个random的第0个数字： 5
第一个random的第1个数字： 0
第二个random的第1个数字： 0
第一个random的第2个数字： 4
第二个random的第2个数字： 4
第一个random的第3个数字： 8
第二个random的第3个数字： 8
第一个random的第4个数字： 1
第二个random的第4个数字： 1


两个不同的random实例竟然每一次得到的随机数都是相同的？？？！！！


———-
我们来思考一个问题：如果编程实现随机数是需要一个算法来计算的，那么：

“算法”和“随机”本身难道不是冲突的吗？？


算法要求有特定的公式生成“随机”数字，那么掌握这个公式的人就可以知道随机生成的规律，那么随机也就不是随机了。

正式如此，像Random或者Math类这样的随机都是伪随机。

事实上，java的伪随机实现是通过线性同余的方程实现的，基本公式如下：（百度百科）
此处输入图片的描述
简单来说，公式里的a，c和m都是整数常量，而随机数Xn+1的数值和上一个随机数Xn相关。那么第一个随机数和谁相关呢？哦，这时候上面代码里的long seed就有了意义了，这一个seed（种子）值就是用来确定第一个随机数用的。根据这个公式，种子数相等的两个random实例每一次随机出的数字都会是一样的（因为随机数只和上一个随机数有关）。

但更要注意的是！！种子的值和随机出来的数字范围没有关系！虽然上面代码里的种子为100，但是nextInt产生的随机数范围还是在0和30之间的！

最后的问题是，刚刚代码里面，不带参数构造的random实例，也就是：
1
Random random = new Random();


它的种子又是什么呢？我们看一下源码：
1
2
3
public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}


这个方法里面有二进制的运算符。但抛开这个不谈，我们发现了不带参的构造方法内部调用了带参的构造方法，而参数则于系统当前时间和一个叫 seedUniquifier() 方法的返回值相关。

好了，最后我们讨论一下什么是“真随机”吧。
既然算法本身无法得到真正的随机数，我们就要寻求计算机外界的帮助。虽然我对量子物理了解不多，但是我们不妨可以这样想：

既然量子世界中的一些值（如电子的运动）是不可预测的，我们可以通过观测读取这些值然后生成真随机数。

同理，现在也有以电脑硬件噪声大小（噪声大小在物理上可以看作随机的)作为输入得到随机值的办法。

脑洞大开！！

写在最后


这是本人的第二篇博文。不想只讲一下AP会考的无聊的方法，我在基础上进行延伸讨论了java随机数伪随机的问题和线性同余方程。

本人数学和CS水平都有限，但依然对这些AP不考，但是非常有趣的概念有着很大的热情。这一篇博文不太长，因为我在策划下一个知识点 AP数据结构-数组和ArrayList 的内容。
我计划做一个视频讲解list的API，并且带着大家通过泛型和数据结构自己实现一个ArrayList(很简单的啦！)，这个工作会在周末完成！

如果喜欢我的文章，不妨将它分享给你身边的CS学生或者对CS感兴趣的同学哦！