CS22计导复习笔记

/* 题量：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)\)

def arctan(x):
	ACCURRACY = 1e-14
    nume = x
    deno = 1
    term = nume/deno
    ansr = x
    while term > ACCURRACY:
        nume *= -x**2
        deno += 2
        term = nume/deno
        ansr += term
    return ansr

【牛顿迭代式】

> 如何推演

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

def ssort(L):
    L = L[:]
    if len(L) <= 1: return L
	min = 0
    for i in range(1, len(L)):
        if L[i] < L[min]:
            min = i
    L[min], L[0] = L[0], L[min]
    return [L[0]] + ssort(L[1:])

• 插入：

def isort(L):
    def r(R,L):
        if len(L) == 0:
            return R
        for i in range(0,len(R)):
            if L[0] <= R[i]:
                return r(R[0:i]+[L[0]]+R[i:],L[1:])
        return r(R+[L[0]],L[1:])
    return r([],L)

• 归并：

def msort(L):
    x = len(L)
    if x <= 1: return L
	L1 = msort(L[0:x//2])
    L2 = msort(L[x//2:])
    return merge(L1,L2)
def merge(L1,L2):
    x = len(L1)
    y = len(L2)
    if x == 0: return L1
	if y == 0: return L2
	if L1[0] <= L2[0]:
        return L1[0] + merge(L1[1:x],L2)
    else:
        return L2[0] + merge(L2[1:y],L1)

• 快排：划分层数 log₂n，理想比较次数 nlog₂n

def qsort(L):
    if len(L)<=1: return L
	a = L[0]; L0 = []; L1 = []
    for e in L[1:]:
        if e <= a:
            L0.append(e)
        else:
            L1.append(e)
    return qsort(L0)+[a]+qsort(L1)

【SEAL】

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

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

mov R1,R2  # R2←R1

add R1,R2,R3  # R1←R2+R3
sub R1,R2,R3  # R1←R2-R3

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

beqz R1,L1  # if R1 = 0 goto L1
bneqz R1,L1  # if R1 != 0 goto L1

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

_data first_address,[a0,a1,...,an]
_pr

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

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

【SEAL】

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

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

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

push R3  # 传参b
push R2  # 传参a

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

goto Lprint

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

# 函数的结束
Lreturn:
pop R4  # 恢复原来存入栈的R4、R3、R2的值
pop R3
pop R2
mov sp,R15  # 令fp=sp（sp拉下来）
pop R15 # 归位fp（fp下去调用函数之前fp的位置）
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 的下一条指令。

【递归. python程序设计】

1. 确定终止条件
2. 确定递推公式

【用stack实现程序】

> push & pop