AP CS复习(2)- Math和Random基础

本来就不是什么高产的人,但是由于AP里面会有一些琐碎的小点,所以干脆简洁的介绍一下。今天讲的就是 java.lang.mathjava.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感兴趣的同学哦!