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

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:等同于printevaluation,返回值

    • 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
    • LOADACC 内容加载到 LOC
    • STORELOC 内容存储到 ACC
    • ADDACC + LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • SUBACC - LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • MULTACC * LOC
      • 若运算结果大于 1e6 则对 1e6 取模 即 \(x \bmod 10^6\)
    • DIVACC / 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 的值
    • DCLABEL 的数值定义为 LOC
    • END 程序结束,LOC 处必须为空
  • 需要关注的例题(1题)

comments powered by Disqus