ACSL
J |
15 Dec 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
1. 进制系统
如果你对这个部分已经非常了解，请直接跳到 “1.5 题目” 的章节。把所有题目完成，比赛就随便考了。
进制系统是现在主流的计数系统。比如我们从小学的十进制就是一个以十为基数的进制系统。一个进制系统有以下特性
- 由 **有限个符号** 构成。一般我们会使用阿拉伯数字0-9作为计数符号，在某些需要更多符号的情况下也会用上英文字母。比如在十六进制中，我们用 A 代表 10, B 代表 11, C 代表 12, D 代表 13, E 代表 14, F 代表 15
- 这些符号有大小之分。数数的本质，其实是不断比上一个数大一点点
- 每一个数会有若干位。每一位上可以放一个该计数系统的符号。如果要表示的数超过了这若干位能表示的范围，那么可以在数的左边继续增加符号
1.1 N进制转十进制
如果一个 m 位的 n 进制数可以写成以下的形式，其中 $d_0…d_n$ 是这个进制系统中的符号
\[d_md_{m-1}...d_3d_2d_1d_0\]右边第一位实际上是代表有多少个 $n^0$，右边第二位代表的是有多少个 $n^1$，右边第三位代表有多少个 $n^2$，以此类推
所以它对应的十进制数就是
\[d_0\cdot n^0 +. d_1 \cdot n^1 + ... +. d_m\cdot n^m\]举个例子
\[\begin{equation} \begin{aligned} 123_8 &= 3\cdot 8^0 + 2 \cdot 8^1 + 1\cdot 8^2 \\ &= 3 + 16 + 64 \\ &= 83\end{aligned} \end{equation}\]1.2 十进制转 N 进制
这里我们不介绍数学原理（其实可以由上面的 (2) 式拓展推），直接介绍方法。比如说，我们要将 **1384 转换成 7 进制**的数。我们需要不断对这个数用 7 去除，然后记录余数。
\[\begin{equation} \begin{aligned} 1384\quad /\quad 7 &= 197 &余数\quad 5 \\ 197 \quad /\quad 7 &= 28 &余数\quad 1\\ 28 \quad /\quad 7 &=4 &余数\quad 0\\ 4\quad /\quad 7 &= 0 &余数\quad 4 \end{aligned} \end{equation}\]然后把所有余数倒过来排列，$4015_7$ 就是我们所要的结果。
1.3 快速换算
理论上来说，掌握 1.1 和 1.2 可以让你解决所有题目了。但有些问题如果想深一步，可以用更加快捷的方式去进行解答。请先思考以下问题，我们知道一个：
- 一个二进制位能表示多少种不同的状态？
- 一个十六进制位能表示多少种不同的状态？
- 四个二进制位能表示多少种不同的状态？
一个二进制位可以表示 2 种状态，所以四个二进制位可以表示 2*2*2*2=16 种状态；而一个十六进制位也刚好能表示 16 种状态。
换句话说，一个十六进制位等价于四个二进制位。所以如果在十六进制位和二进制位互相转换时，我们可以利用这个特性。
1.3.1 十六进制到二进制
十六进制的每个字符都可以转化成4个二进制字符，因为它的基数16相当于$2^4$。
例子：
\[4B7_{16} \rightarrow \begin{array} {c:c:c} 0100 & 1011 & 0111 \end{array} \rightarrow 10010110111_{2}\]
1.3.2 八进制到二进制
同样的原理，我们可以利用 $8=2^3$ 这个事实，用三个二进制位代表一个八进制位。
八进制与二进制之间的转化与十六进制与二进制之间的转化相似，因为基数8相当于$2^3$。
例子：
\[363_8 = \begin{array}{c:c:c}011 & 110 & 011\end{array} = 11110011_2\]
1.3.3 十六进制与八进制互相转化
虽然 16 和 8 不存在上面所说的关系，但是他们都是2的幂，所以我们可以把这两个进制的数先转成二进制，然后重新分组，进行快速的转化。
将要转化的数字先转成二进制，然后对二进制的数位重新分割
例子：
\[\begin{aligned} &3FD7_{16}\\ &=\begin{array}{c:c:c:c}0011 & 1111 & 1101 & 0111\end{array}_2\\ &=11111111010111_2\\ &=\begin{array}{c:c:c:c}0 & 011 & 111 & 111 & 010 & 111\end{array}_2\\ &=37727_{8} \end{aligned}\]
1.3.4 [选修] 推广：互为乘方的进制间转
相似的做法可以在base互为乘方的数字之间使用，例如在 9-base 与 3-base 之间也可以用这个方法
例子：
\[458_9 = \begin{array}{c:c:c}11&12&22\end{array} = 111222_3\]
1.4 [选修] n进制计算*
大部分情况下，我们会使用常规的做法，把式子中所有的数转换成十进制数，用我们最熟悉的十进制做计算，再把结果转换回相应的进制。
但是有些时候我们也可以直接在n进制下进行运算。这是一个进阶内容，如果你对进制系统的理解足够好，那么有些情况下可以加速计算。对于大部分同学而言，可以略过这个部分，并不会影响你做题的效率。
其实规则也很简单，和十进制的运算做类比
- 加法时逢 n 进 1
- 减法时遇到不够减的，可以向左边一位借1，借回来的当 n 使用
1.4.1 n进制的加减法（熟练运用竖式 vertical calculation
-
同样进制的加减法
\[3B7_{16} + 1A_{16} = 3D1_{16}\] \[\begin{matrix} &3 & B & 7_{16} \\ +& & 1 & A_{16} \\ \hline &3 & D & 1_{16} \end{matrix}\]Example - Senior 16, 26
-
转换回十进制进行计算
-
转换回二进制进行计算
\[123_{16} + 12_{10} + 16_{8} = 475_{8} \\ \downarrow\\ 100100011_2 + 1100_2 + 1110_2 = 100111101_{2}\] \[\begin{matrix} &1&0010&0011\\ +&&&1100\\ \hline &1&0010&1111\\ +&&&1110\\ \hline &1&0011&1101 \end{matrix}\]
1.4.2 n进制乘除法
-
转换回十进制计算
\[101_2 \times 32_8 = 202_8\\ \downarrow\\ 5\times 26 = 130\] -
位移
$n$ 进制的数字乘上$n$ 相当于在后面加上一个0，除以$n$ 相当于在后面减少一个0
\[8_{10} \times 100101_2 = 450_8\\ \downarrow\\ 8_{10} \times 45_8 = 450_8\]Example: Senior 9, 10, 23
miscellaneous
Palindrome 回文 - 顺读和倒读都一样的数字
Example Senior 29, Intermediate 17
1.5 题目
以下是按照出题形式分类的题号表
| Senior | Intermediate | |
|---|---|---|
| 解方程 | 1, 3, 9, 10, 12, 13, 14, 17, 18, 20, 23, 25, 26, 32, 34, 35, 39 |
2, 3, 4, 8, 10, 21, 24, 25, 26 |
| 枚举 | 2, 7, 11, 31, (28), 36 | 4, 7, 15, 18, 19, 22, 29, 30, 35, 37, 38 |
| 找规律 | 4, 40 | |
| 回文 | 5, 21, 27, 29 | 17, 27 |
| 计算 | 6, 8, 15, 16, 19, 33, 38 | 6, 11, 12, 14, 20, 23, 28, 33, 34 |
| 比较 | 24, 37 | 13, 32 |
| 进制转化 | 1, 9, 16, 31 | |
| 杂项 | 22, 30 |
1.5.1 Senior 组题目
如果下面的文档无法显示，点击这里下载文件
1.5.2 Intermediate 组题目
如果下面的文档无法显示，点击这里下载文件
2. 递归函数
2.1 题型分类
递归函数的题目主要有以下几种题型：
-
传统类型
Intermediate 3, 8 （一个变量），Intermediate 2 （两个变量）
-
$n$ 推 $n + 1$
Intermediate 14
-
应用题（自己推出来recursive function
Intermediate 10, 16
2.2 传统类型
Example - Find $f(8)$
\[f(x) = \begin{cases} f(f(x-3)) + 4, \quad x>4\\ x^2 - 3, \quad x \leq 4 \end{cases}\]
可以先尝试自己做一下，如果做对了，可以直接快进到下一个section。
如果没做对，可以参考使用下面的方法：
-
先展开 $f(x)$ 的表达式，如果有递归的话先不着急往下递归
\[f(8) = f(f(5)) + 4\] -
如果刚刚的表达式中有递归的函数，展开递归到的函数的表达式
\[f(5) = f(f(2)) + 4\] \[f(2) = 2^2-3 = 1\] -
如果递归到底部（表达式中没有递归的式子了，也就是说表达式可以求出来值了），直接算出来以后开始一层一层往回带
\[f(5) = f(f(2)) + 4 = f(1) + 4\\ \uparrow\\ f(2) = 1\] -
往回带的时候如果遇到新的递归函数，回到第二步
\[f(5) = f(1) + 4=-2 + 4=2\\ \downarrow\quad\quad\quad\quad\quad \uparrow\\ f(1) = 1^2 - 3 = -2\] -
重复2 - 4，直到算出来最后的结果为止
\[\begin{aligned} f(8) = f(&f(5)) + 4 = f(2) + 4 = 1 + 4 = 5\\ &\downarrow\quad\quad\quad\quad\uparrow\\ f(5) = f(&f(2)) + 4 =\quad f(1) + 4= -2 + 4 = 2\\ &\downarrow\quad\quad\quad\uparrow\quad\quad\downarrow\quad\quad\uparrow\\ f(2) &= 2^2 - 3 = 1\;\; f(1) = 1^2 - 3 = -2 \end{aligned}\]
计算递归函数实际上是一个很机械的过程，只要细心把自己的草稿纸维护的比较整洁有条理一般不会出错
2.3 题目
2.3.2 Senior 组题目
如果下面的文档无法显示，点击这里下载文件
2.3.2 Intermediate 组题目
如果下面的文档无法显示，点击这里下载文件
3. 伪代码 What Does this Program Do (WDTPD)
官方的链接
http://www.categories.acsl.org/wiki/index.php?title=What_Does_This_Program_Do%3F
3.1 介绍
这里主要是考验大家阅读伪代码 Pseudocode 的能力，伪代码不是任何一种可以运行的语言，但是可以让我们不管语言的具体语法而理解算法/程序的逻辑
3.2 伪代码语法/运算符
3.2.1 运算符
| Code Segment | Meaning |
|---|---|
! |
not 非运算 |
^ or ↑
|
exponent 指数 |
% |
modulus 求余（取模） |
&& |
logical and 逻辑与运算 |
|| |
logical or 逻辑或运算 |
3.2.2 函数
| Code Segment | Meaning |
|---|---|
ABS(n) |
n的绝对值 |
INT(n) |
n向下取整 |
SQRT(n) |
n 的平方根 |
3.2.3 数组
| Code Segment | Meaning |
|---|---|
dim a(n) |
创建一个一维，大小为n的数组a，index 从0或1开始计算
|
a(x, y) |
返回二维数组a中第x 行y列的元素 |
3.2.4 字符串操作
| Code Segment | Meaning |
|---|---|
S = "Example String" |
创建一个字符串（可以包含0或多个字符），index 从0开始计算 |
len(S) |
字符串S的长度 |
S[0] |
字符串S的第0位 （在我们的例子里面，S[0] -> "E"） |
S[:3] |
字符串的前3位（在我们的例子李，S[:3] -> "Exa"）
|
S[11:] |
字符串从第11位到结尾的值，包括第11位（在我们的例子里，S[11:] = ring） |
S[2:5] |
字符串的第2位到第4位，注意不包括第5位 |
S + "abc" |
拼接"abc"在S后面 |
3.2.5 代码逻辑语句
| Code Segment | Meaning |
|---|---|
IF ... THEN ... (ELSE ...) |
if语句 |
WHILE ... END WHILE |
不定循环语句 |
FOR x=start TO end STEP increment...NEXT x
|
确定循环次数的循环 |
3.3 题型
| Questions | |
|---|---|
| 1. 各个变量的变化 | Intermediate 1, 3, 5, 7, 9, 11 *第五题和第七题的答案反了 |
| 2. For loop 循环 (Array 题型) | Intermediate 2, 4, 6, 8, 10, 12 |
3.4 做题方法
WDTPD题型一般出现在ACSL最后一道题，代码会比较长，所以一种方法是在纸上面记录下来所有变量现在的值，这样可以尽可能减少出错的概率
3.5 题目
Senior 和 Intermediate 都做下面这份习题
如果下面的文档无法显示，点击这里下载文件
4. 编程题
4.1 Java中进制转化的方法
4.1.1 Dec to Oct
int number = 8 + 4;
String octNumber = Integer.toOctalString(number);
System.out.println(octNumber);
Output
14
4.1.2 Dec to Hex
int number = 16 + 12
String hexNumber = Integer.toHexString(number);
System.out.println(hexNumber);
Output
1C
5. 练习题答案
5.1 Computer Number System
5.1.1 Intermediate Solution
如果下面的文档无法显示，点击这里下载文件
5.1.2 Senior Solution
如果下面的文档无法显示，点击这里下载文件
5.2 Recursive Function
5.2.1 Intermediate Solution
如果下面的文档无法显示，点击这里下载文件
5.2.2 Senior Solution
如果下面的文档无法显示，点击这里下载文件
5.3 What Does This Program Do
如果下面的文档无法显示，点击这里下载文件
