从零到一：「计算机导论」课程笔记

944 字

5 分钟

从零到一：「计算机导论」课程笔记

2022-12-20

/

一家之言，仅供参考，以实际为准。有疑义，是你对。
——LeeHero

/* 题量：8题 */

【for循环. python程序设计】#

> eg.算e/pi > 要求精简，不能重复计算

$arctanx=x-\frac{1}{3}x^3+\frac{1}{5}x^5-...+(-1)^n\frac{x^{2n+1}}{2n+1}+...(-1≤x≤1)$

1
def arctan(x):
2
  ACCURRACY = 1e-14
3
    nume = x
4
    deno = 1
5
    term = nume/deno
6
    ansr = x
7
    while term > ACCURRACY:
8
        nume *= -x**2
9
        deno += 2
10
        term = nume/deno
11
        ansr += term
12
    return ansr

【牛顿迭代式】#

> 如何推演

1
def ans(c):
2
    ACCURACY = 1e-14
3
    g = c/2
4
    i = 0
5
    while abs(f(g) - c) > ACCURACY:
6
        g = h(g)  # 牛顿迭代式：右边的g带到曲线中，该点切线与x轴的焦点为新的g
7
        i += 1
8
    return g

【正负数的表示】#

> 加法/测溢出.etc

对于n位计算机，正整数x： $-x = 2^n-x$ ；本质为二进制取反码+1，获得补码。
补码表示n位带符号整数范围： $[-2^{n-1},2^{n-1}-1]$
正数相加，二进制最高位若为1，发生正溢出。
负数相加，二进制最高位若为0，发生负溢出。
正负相加，不会溢出

【排序方法】#

> highlight: 插入/归并/快排

选择：比较次数 1+2+…+( n-1 ) = n( n-1 ) / 2

1
def ssort(L):
2
    L = L[:]
3
    if len(L) <= 1: return L
4
  min = 0
5
    for i in range(1, len(L)):
6
        if L[i] < L[min]:
7
            min = i
8
    L[min], L[0] = L[0], L[min]
9
    return [L[0]] + ssort(L[1:])

插入：

1
def isort(L):
2
    def r(R,L):
3
        if len(L) == 0:
4
            return R
5
        for i in range(0,len(R)):
6
            if L[0] <= R[i]:
7
                return r(R[0:i]+[L[0]]+R[i:],L[1:])
8
        return r(R+[L[0]],L[1:])
9
    return r([],L)

归并：

1
def msort(L):
2
    x = len(L)
3
    if x <= 1: return L
4
  L1 = msort(L[0:x//2])
5
    L2 = msort(L[x//2:])
6
    return merge(L1,L2)
7
def merge(L1,L2):
8
    x = len(L1)
9
    y = len(L2)
10
    if x == 0: return L1
11
  if y == 0: return L2
12
  if L1[0] <= L2[0]:
13
        return L1[0] + merge(L1[1:x],L2)
14
    else:
15
        return L2[0] + merge(L2[1:y],L1)

快排：划分层数 log2n，理想比较次数 nlog2n

1
def qsort(L):
2
    if len(L)<=1: return L
3
  a = L[0]; L0 = []; L1 = []
4
    for e in L[1:]:
5
        if e <= a:
6
            L0.append(e)
7
        else:
8
            L1.append(e)
9
    return qsort(L0)+[a]+qsort(L1)

【SEAL】#

> 如quiz，用SEAL写python程序 > for? if-else?

1
# SEAL指令精简统合
2
load R1,(address)  # R1←(address) 即主存adress中的变量
3
load R1,offset(R2)  # R1←(R2+offset)
4
store (address),R1  # (address)←R1
5
store offset(R2),R1  # (R2+offset)←R1
6

7
mov R1,R2  # R2←R1
8

9
add R1,R2,R3  # R1←R2+R3
10
sub R1,R2,R3  # R1←R2-R3
11

12
slt R1,R2,R3  # if R2<R3, R1←1 else R1←0
13
sle R1,R2,R3  # if R2<=R3, R1←1 else R1←0
14

15
beqz R1,L1  # if R1 = 0 goto L1
16
bneqz R1,L1  # if R1 != 0 goto L1
17

18
call L1  # 调用L1标签下的函数
19
ret  # 返回并继续call下一条语句
20

21
_data first_address,[a0,a1,...,an]
22
_pr
23

24
# 连招：
25
sle R4,R2,R3  # 若R2<=R3, R4←1, 继续执行，否则跳转L100
26
beqz R4,L100
27

28
xor R6,R4,1  # 若R4=1，R6=0
29
beqz R6,L1  # 若R6!=0，继续执行，否则跳转L1

【SEAL】#

> 函数如何调用 > 栈帧如何建立

1
# （主）函数的开始
2
mov R15,300  # 代表fp，基地址300
3
mov sp,R15  # sp=fp
4
sub sp,sp,3  # sp向上3个单位，开辟空间存a,b,c
5

6
mov R2,7  # R2 ← a=7
7
mov R3,18  # R3 ← b=18
8
mov R4,9  # R4 ← c=9
9
store -1(R15),R4  # c、b、a倒序存参
10
store -2(R15),R3
11
store -3(R15),R2
12

13
push R3  # 传参b
14
push R2  # 传参a
15

16
call Lmax  # 调用函数 (Lmax标签下部分)
17

18
goto Lprint
19

20
# 函数的开始
21
Lmax:
22
push R15  # 存旧的fp
23
mov R15,sp  # 复位fp，令fp=sp（fp拉上去）
24
push R2  # 把函数会被更改的R2,R3,R4存入栈（存档）
25
push R3
26
push R4
27
load R2,2(R15)  # 存函数第一个参数
28
load R3,3(R15)  # 存函数第二个参数
29
...
30

31
# 函数的结束
32
Lreturn:
33
pop R4  # 恢复原来存入栈的R4、R3、R2的值
34
pop R3
35
pop R2
36
mov sp,R15  # 令fp=sp（sp拉下来）
37
pop R15 # 归位fp（fp下去调用函数之前fp的位置）
38
ret

最前三个指令：
1. 定位 fp，即确定基地址
2. 令 fp=sp （fp 拉上去）
3. 令 sp-n，即开拓局部变量存储的 n 个空间，sp 指向栈顶
最后三个指令：
1. 令 fp=sp，释放建立的栈帧（sp 拉下来）
2. 弹出旧的fp，令fp回复函数调用之前的位置
3. ret，即pop pc，（与call L 相对应。call L 相当于 push pc 并跳转并执行函数L）返回到 call 的下一条指令。