Back
Featured image of post American Computer Science League (ACSL) 速成笔记
Computer Science

American Computer Science League (ACSL) 速成笔记

包含了 ACSL 的所有考点，线上考试要点

本笔记直接从 Notion 签出，格式混乱，内容或有错误，仅供参考

Computer Number Systems

Computer Number Systems - ACSL 官方文档

  • 进制转换可以直接用计算器

  • 可能有设 \(x\) 的题，需要练习

  • 快速入门

    • 前20位各进制对照表

    • 从 任意进制 到 十进制

      • 多项式表达

      \[\underbrace{\overline{abcd\cdots n}_{\text{base} = p}}_{\text{length}=l} = a \times p^{l-1} + b \times p^{l-2} + c \times p^{l-3} + \cdots + n \times p^0\]

      • 例

      \[12345_{10} = 1×10^{4}+ 2×10^{3}+ 3×10^{2}+ 4×10^{1}+ 5×10^{0} = 10000 + 2000+ 300 +40+5 = 12345_{10} \\ \; \\ 1101_{2} = 1 × 2^3 + 1 × 2^2 + 0 × 2^1 + 1 × 2^0 = 8 + 4 + 0 + 1 = 13_{10} \\ \; \\ 175_{8} = 1 × 8^2 + 7 × 8^1 + 5 × 8^0 = 1 × 64 + 7 × 8 + 5 × 1 = 64 + 56 + 5 = 125_{10} \\ \; \\ \text{A5E}_{16} = 10 × 16^2 + 5 × 16^1 + 14 × 16^0 = 10 × 256 + 5 × 16 + 14 × 1 = 2560 + 80 + 14 = 2654_{10}\]

    • 从 十进制 到 任意进制

      • 短除法，除 底数 取余，一直除到 \(0\) 为止，然后倒序排列。
      • 例

      \[ \begin{aligned} 42 \div 2 = 21 \cdots 0 \\ 21 \div 2 = 10 \cdots 1 \\ 10 \div 2 = 5 \cdots 0 \\ 5 \div 2 = 2 \cdots 1 \\ 2 \div 2 = 1 \cdots 0 \\ 1 \div 2 = 0 \cdots 1 \\ \Rightarrow 42_{10} =101010_2 \end{aligned} \]

      • 短除法形式

    • 二进制 与 八进制 与 十六进制 之间的分组转换 3 \[\begin{aligned} 75_{8} &= \ \ 011\ \ \ 111\ \ \ 101_{2} = 11111101_2 \\ \text{FD}_{16} &= \ \ 1111\ \ \ 1101_{2} = 11111101_2 \\ 10000001111000101100 &= 10\ 000\ 001\ 111\ 000\ 101 \ 100 = 2017054_8 \\ 10000001111000101100 &= 1000\ 0001\ 1110\ 0010\ 1100 = \text{81E2C}_{16} \end{aligned}\]

    • 通过 十六进制 表示 \(\text{RGB}(r, g, b)\) 颜色

    \[\text{RGB}(r_{10}, g_{10}, b_{10}) = \text{RR}_{16} \text{GG}_{16} \text{BB}_{16}\]

  • Kotlin 进制转换方法 (TODO)

    • 如 Ascending Digits 这种题目，就需要写代码了

进制转换

  • 需要关注的例题 （4题）

    • 设 \(x\) 的题

      Solve for \(X_{16}: X_{16}*2+11011010_2=4320_8\)

      • Answer

        \(X_{16}=3FB_{16}\)

      Solve for \(X_2:31_8*X_2+12_{16}=28_{16}*X_2-1001000_2\)

      • Answer

        \(X_2=110_2\)

      (转换成10进制因式分解）Solve for \((X_{16})^2-1010101_2*X_{16}+1356_8=0\)

      • Answer: \(A \text{ or } 4B\)
        • (X inside expression) Solve for \(X:1X6_{16}=X26_8\)
      • Answer
        • 等式两边皆转换成10进制然后解方程
        • \(X = 5\)

Recursive Function

Recursive Functions - ACSL 官方文档

  • 大多数可以直接写个代码跑出来
  • 注意一些图像题

What Does This Program Do?

What Does This Program Do?

ACSL 官方文档

  • 大多数可以直接执行
  • 注意数组和字符串操作题
    • Index 均以 0 为起点
    • A(n) 同 arr[n]
    • A(r, c) 同 arr[r][c]
    • S[:n] 同 str.substring(n);
    • S[n:] 同 str.substring(n, str.length());
    • S[l:r]
  • 注意运算优先级

Prefix / Infix / Postfix Notation

Prefix/Infix/Postfix Notation - ACSL 官方文档

  • 打括号可以解决 \(99\%\) 的题
  • 大多数可以直接跑出来

prefix postfix infix online converter

中后缀转换器，里面还有其他的转换，包括前中，前后等等

  • 需要关注的例题 (2题）

    • （新概念符号）Suppose @ is a ternary operator whose value is the minimum of its three operands. Evaluate the following postfix expression:

    \[73+26*23\uparrow 3+@\]

    • Answer: \(10\)

    • Translate the following infix expression to postfix:

      \[\frac {(A^2+B)^2-(AB+B^2)^{1/2}}{A/B^2+A^2B/C}\]

    • Answer: \(A2\uparrow B+2\uparrow AB *B2\uparrow +12/\uparrow -AB2\uparrow/A2\uparrow B*C/+/\)

Bit-String Flicking

Bit-String Flicking

ACSL 官方文档

  • 比较简单，就不找工具了，多刷题
  • 快速入门

  • 注意运算优先级

    • NOT > SHIFT > CIRC > AND > XOR > OR

  • 需要关注的例题 （1题）

    • The two arguments in the expression below are hexadecimal representations of bit strings that are 12-bits long. Evaluate the expression and express your answer as a 3-digit hexadecimal string.

    \[(A26) XOR (7B5)\]

    - Answer: $D93$
    • (设 \(x\)）List all of the values of X (a 5-bit string) that satisfy:

    \[\text{RCIRC}-2~~(\text{RSHIFT}-1~~X))=(\text{RSHIFT}-1~ 10101)~~OR~~(\text{LCIRC}-2~~01010)\]

    - Answer: $1101*$

LISP

LISP

ACSL 官方文档

  • 大多数可以直接跑出来
  • 快速入门：

    • Basic Functions

      1. SET: set ’a = b
      2. SETQ: 默认被赋值的是字符（was quoted)
      3. ATOM：不是 list 的就叫做 atom
      4. EVAL：等同于print，evaluation，返回值

    • List Functions

      1. CAR：取出 list 第一个
      2. CDR：去除 list 第一个，返回新 list
      3. CONS：两个 args，将第一个 arg 加到第二个list第一个位置
      4. REVERSE：将list里的elements按倒序排列
  • 需要注意的是，ACSL 的 LISP 语法与现实中的 LISP 有所不同
    • 需要将 LISP 表达式中的 ADD, SUB, MULT, DIV 数学操作符改为 +, -, *, /
  • ACSL LISP 不会打印出结果，需要在表达式前面加一个 print 函数
  • 所有函数大小写无关（如 print, car, cdr ... )
; ACSL LISP
(MULT (ADD 6 5 0) (MULT 5 1 2 2) (DIV 6 (SUB 2 5)))

; Common LISP, final executed
(print (* (+ 6 5 0) (* 5 1 2 2) (/ 6 (- 2 5))))

在线 LISP 运行

Boolean Algebra

Boolean Algebra - ACSL 官方文档

  • 大多数可以直接跑出来
  • 注意运算优先级: not, and, xor/xnor, or
  • 快速入门

    • \(\overline A \quad \neg A\)，NOT，取反，\(0\) 变 \(1\)，\(1\) 变 \(0\)

      • 实际意义，如 if (!arr.isEmpty()) 则是判断数组如果不是空的话

    • \(AB \quad A\land B\)，且，两个都为 \(1\) 结果为 \(1\)

    • \(A + B \quad A \vee B\)，或，任意一个为 \(1\) 结果为 \(1\)

    • \(A \oplus B \quad A\veebar B\)，异或，两个不同结果就是 \(1\)

      • 实际意义，如 if (mode == A ^ mode == B) 要么选择 A 模式， 要么选择 B 模式（因为运算优先级不用加括号）

    • \(A \odot B \quad A\overline\veebar B\)，同或，两个相同结果就是 \(1\)

      • 实际意义，如，要么同时有账号密码（以用户访问），要么同时没有（以游客访问）

  • 需要注意的是，下文提到的计算器的 Overline 通过 ! 输入（英文，半角字符）
    • 而且需要把 ! 当成括号使用

Boolean Algebra Solver - Boolean Expression Calculator

布尔代数计算器

  • Cheat Sheet

    • \(x \oplus y = x\overline y + \overline x y\)
    • \(x \odot y = \overline{x \oplus y}\)
    • \(x \odot y = xy + \overline{xy}\)

  • 需要关注的例题 （1题）

    • (XOR 题）List all ordered triples (A, B, C) that makes the following expression TRUE

    \[AB\oplus \overline {C+(CB+A)}\]

    • Answer

      4 pairs: \((1,1,0), (1,1,1),(0,0,0), (0,1,0)\)

Data Structures

Data Structures - ACSL 官方文档

  • 快速入门
    • 栈，先进后出
    • 队列，先进先出
    • 链表 [ACSL Not Required]
    • 树
      • 二分查找树
      • 平衡树
      • 前序
      • 中序
      • 后序
    • 优先队列
    • 最小堆 [ACSL Not Required]

Binary Search Tree - 二分搜索树

FSAs and Regular Expressions

FSAs and Regular Expressions - ACSL 官方文档

  • Cheat Sheet

  • 快速入门

    • \(\lambda \quad \text{RE}\) 指 空
    • 如果一个输入的字符 \(a\) 不在字母表中，则认为 \(a =\lambda\)
    • 级联（Concatenation）跟随匹配，\(ab\)
      • 匹配到 \(a\) 后接着是 \(b\)，也就是匹配 \(ab\)
    • 并集，或（Union）任意匹配一种，\(a\cup b\) 或 \(a | b\)
      • 匹配 \(a\) 或者 \(b\)
    • 闭环（Closure）匹配多次重复，\(a^*\)，也称作为克莱恩星（Kleene Star）,
      • 可以匹配多个重复的 \(a\)
    • \(?\)，匹配 \(0\) 次或 \(1\) 次
      • 如 \(a?b\)，匹配 \(ab,b\)
    • \(+\)，匹配 \(1\) 次或 多次
      • 如 \(a+b\)，匹配 \(ab,aaaab\)
    • \(.\)，匹配任意字符
      • 如 \(.b\)，匹配 \(xb, yb\)
      • 如 \(.*b\) 匹配 \(xb,b,xxxxxb\)
    • \([\; ]\)，分类符，匹配括号内的任意一个
      • 如 \([abc]\) 意为，匹配 \(a, b,c\) 任意一个
      • 特殊定义 \([a-z]\) 意为，匹配所有小写字母
        • 同理 \([A-Z]\) 意为，匹配所有大小写字母
        • 同理 \([a-zA-Z]\) 意为，匹配所有字母
      • 在 分类符 中 \(|\) 表示匹配一个 \(|\) 字符，而非 或 的意思
    • \(\text{[\;\^{}\;\;]}\)，取反分类符，匹配不在括号内的任何一个字符
      • 如 \([abc]\) 意为，匹配除了 \(a,b,c\) 以外的任意一个
    • \((\;)\)，分组类，只是单纯分组，只有在现代编程语言有实际意义
    • 将 FSA Graph 转为正则表达式，如图为 01*01

Graph Theory

Graph Theory - ACSL 官方文档

  • 基本无法使用辅助工具，需要大量刷题
  • 快速入门
    • Cycle
    • 邻接矩阵

Digital Electronics

Digital Electronics - ACSL 官方文档

  • 主要思路是将电路图转换为布尔代数，然后求真值表

Boolean Algebra Solver - Boolean Expression Calculator - 布尔代数计算器

  • Cheat Sheet

Assembly Language

Assembly Language Programming - ACSL 官方文档

  • 可以通过 acsl-assembly-shell 模拟执行
  • 但是如果遇到有 \(x\) 和 input 的题目可能就不行了

GitHub - kylediaz/acsl-assembly-shell: A shell, compiler, and interpreter for the once-ficticious ACSL assembly language

acsl-assembly-shell Github 项目

  • 快速入门

    • LABEL OPCODE LOC
    • LOAD 将 ACC 内容加载到 LOC
    • STORE 将 LOC 内容存储到 ACC
    • ADD 将 ACC + LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • SUB 将 ACC - LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • MULT 将 ACC * LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • DIV 将 ACC / LOC 取整数部分，即 \(\lfloor x \rfloor\)
    • BG 如果 ACC > 0 则跳转到 LOC 指定的 LABEL 分支
    • BL 如果 ACC < 0 则跳转到 LOC 指定的 LABEL 分支
    • BE 如果 ACC = 0 则跳转到 LOC 指定的 LABEL 分支
    • READ 从输入中读取一个整数，加载到 LOC
      • 若输入值大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • PRINT 打印 LOC 的值
    • DC 将 LABEL 的数值定义为 LOC
    • END 程序结束，LOC 处必须为空

  • 需要关注的例题（1题）

comments powered by Disqus