SICP学习

前几天无聊的时候在B站看了一下SICP的视频,就看了三四集,感觉获益匪浅,故打算认真学习一下.

¶Lisp概述

如何对计算过程进行形式化表述,如何解决问题,并结合两者发展一套对问题处理过程精确表述的方法.

关键的是计算过程,即process.

程序,procedure,应理解为a pattern of rules that directs a process.

计算机科学的真正议题:形式化这种如有关"怎么做"的指令性知识,并将之付诸实际.

形式化是一个难点,另一个难点则来自于当过程非常复杂的时候.

第一个控制复杂度的方法: 黑盒抽象.

对于一个过程,你可以将其分为几个子过程,并且假设这几个子过程是正确的.

例如对于求x的平方根算法:

猜一个初值s
改进初值为$s+\frac{x}{s}$
不断改进s,直至s足够好

这里算法可以由三个黑盒构成:

猜初值s
改进s
判断s是否足够好

这三个黑盒都可以看作是一个对象,也就是一个procedure.

除了这三个对象之外,这个算法本身也有一个procedure,它将这三个对象组合在一起,形成了求x的平方根算法这个大的procedure.

从上面这个例子来看,抽象出procedure这个概念是有利于理解算法的.

但是否总是如此呢?这个算法本身偏向于数学.

让我们看看其他算法.例如最小生成树算法,该算法可以表述为:

找到所有边,然后进行排序
依次选取最小的边,尝试加入最小生成树,如果最小生成树不成立,则跳过这条边,选取下一条边.

这个算法是否可以用黑盒抽象来理解?

可以看作四个盒子:

对所有边进行排序
寻找最小的边
加入最小生成树,判断是否有环路
判断边数是否为n-1(n为点的个数)

很显然,在这个算法中的抽象并不如平方根算法的抽象更为完美,例如寻找最小的边和加入最小生成树,判断是否有环路这两个黑盒并非完全独立.它们有着数据的交换.并且对于寻找最小的边这个过程,看作一个黑盒也十分勉强,因为它像是"自运行的",没有输入值,但是每次返回的结果都不一致.

同样的,在平方根算法的抽象之中,也有一个地方我并不觉得完美.那就是三个黑盒的组合过程,这个算法本身.

所以黑盒抽象的难点在于:如何控制黑盒内的小黑盒之间的组合过程的复杂度

究其根本,大概还是因为,人类的对于静态思维更容易接受,而对于动态的组合过程就差一点.

后面视频中,老师对黑盒抽象的内容做了列举:

基本对象:
- 基本数据
- 基本过程
过程的组合和抽象
数据的组合
高阶过程

控制复杂度的第二种方法,接口约定.

TODO 很显然这部分你听不明白

控制复杂度的第三种方法,定义新的语言.

TODO 很显然这部分你也听不懂

第二节课就是讲解lisp本身了.

基本数据: 3,3.14

基本过程:+

组合式:(+ 3 4)

¶个人思考

来对一道实际的题目做一个分析.

化学方程式,CSP认证试题,编号201912-3.

给出一个化学方程式,判断其是否配平.

题目描述如下图

这是你当时提交的python代码.评测结果为70分.

# 读入数据
N=int(input())

equations=[]
for i in range(N):
    equations.append(input())


def exprsplit(expr):
    ans=expr.split('+')
    return ans

def isnumber(c):
    if c<='9' and c>='0':
        return True
    else:
        return False

def isUpper(c):
    if c<='Z' and c>='A':
        return True
    else:
        return False

# 这个函数输入一个化学方程式,返回一个字典,键为其元素,值为元素的个数.
def countelements(term):
    ans={}
    if len(term)==0:
        return ans
    if len(term)==1:
        ans[term]=1
        return ans
    if isUpper(term[0]):
        if isUpper(term[1]):
            another=countelements(term[1:])
            if term[0] in another.keys():
                another[term[0]]+=1
            else:
                another[term[0]]=1
            return another
        
        if isnumber(term[1]):
            n=''
            i=1
            while True:
                n+=term[i]
                i+=1
                if i==len(term):
                    break
                if not isnumber(term[i]):
                    break
            n=int(n)
            another=countelements(term[i:])
            if term[0] in another.keys():
                another[term[0]]+=n
            else:
                another[term[0]]=n
            return another
        
        if len(term)>2 and isnumber(term[2]):
            n=''
            i=2
            while True:
                n+=term[i]
                i+=1
                if i==len(term):
                    break
                if not isnumber(term[i]):
                    break
            n=int(n)
            another=countelements(term[i:])
            if term[0:2] in another.keys():
                another[term[0:2]]+=n
            else:
                another[term[0:2]]=n
            return another 
        else:
            another=countelements(term[2:])

            if term[0:2] in another.keys():
                another[term[0:2]]+=1
            else:
                another[term[0:2]]=1
            return another
    elif term[0]=='(':
        i=1
        k=1
        while True:
            if term[i]=='(':
                k+=1
            if term[i]==')':
                k-=1
                if k==0:
                    break
            i+=1
        another=countelements(term[1:i])
        j=i+1
        while True:
            if j==len(term):
                break
            if isnumber(term[j]):
                j+=1
                continue
            else:
                break
        if i+1<j:
            nu=int(term[i+1:j])
            for k in another.keys():
                another[k]*=nu
        
        another2=countelements(term[j:])
        k1=another.keys()
        k2=another2.keys()
        kall=list(k1)+list(k2)
        ans={}
        for k in kall:
            ans[k]=0
        for k in kall:
            if k in k1:
                ans[k]+=another[k]
            if k in k2:
                ans[k]+=another2[k]
        return ans
    else:
        i=0
        n=''
        while True:
            n+=term[i]
            i+=1
            if i==len(term):
                break
            if not isnumber(term[i]):
                break
        n=int(n)
        ans=countelements(term[i:])
        for k in ans.keys():
            ans[k]*=n
        return ans

def countallelements(formula):
    ans={}
    for term in formula:
        t=countelements(term)
        for k in t.keys():
            if k not in ans.keys():
                ans[k]=t[k]
            else:
                ans[k]+=t[k]
    return ans
def judge(equation):
    expr1,expr2=equation.split('=')

    formula1=exprsplit(expr1)
    formula2=exprsplit(expr2)
    t1=countallelements(formula1)
    t2=countallelements(formula2)
    if t1==t2:
        return 'Y'
    else:
        return 'N'



ans=[]
for i in range(N):
    ans.append(judge(equations[i]))

print('\n'.join(map(str,ans)),end='')

怎么说呢,这个代码一眼看过去就不算是好的代码,函数countelements写得比较差.

现在让你来写一遍,又该怎么分析呢?

首先思路大概是这样:

对一个化学方程式,分解为左右两个表达式
对每一个表达式,分解为多个化学式,对每个化学式,求解其元素种类和对应的个数,然后求解整个表达式元素种类和对应的个数
然后判断左右两边元素种类和对应的个数是否相等.

这个思路中,黑盒抽象都没有问题.除了第二个黑盒以外,其他的黑盒都是很容易构建的.

所以关键是化学式的分析.

以下是化学式的结构组成.

尝试构建一下求解化学式A的方法:

分解A为coef和formula
对一个formula,拆解出一个子formula和term+coef
返回term的element

…显然你构建的方法并不好,各个过程之间是连接的,而并非独立…

再尝试一下:

分解A为coef和formula
对一个formula求解其元素组成
对formula的元素组成乘上coef

这个明显比上面的好一点,但是第二个黑盒仍然需要继续拆解.

对一个formula求解其元素组成的过程可拆解为:

将formula划分为子formula和term和coef
将term划分为element
对子formula的求解其元素组成
将term的元素组成乘上coef然后加上子formula的元素组成

这个过程还是比较清晰的,但是第二个黑盒还需要继续拆解.

将term划分为element可拆解为:

判断term是否为一个element
如果为element,返回该元素
如果不是element,返回该formula的元素组成

大概整个过程就是如此.感觉思路上还是挺清晰的.

N = int(input())

equations = []
for i in range(N):
    equations.append(input())


def isnumber(c):
    if c <= '9' and c >= '0':
        return True
    else:
        return False


def isUpper(c):
    if c <= 'Z' and c >= 'A':
        return True
    else:
        return False


def f10(A):
    coef, formula = f11(A)
    if len(coef) == 0:
        coef = 1
    else:
        coef = int(coef)
    elementdict = f12(formula)
    for k in elementdict.keys():
        elementdict[k] *= coef
    return elementdict


def f11(A):
    coef = ''
    i = 0
    while isnumber(A[i]):
        coef += A[i]
        i += 1
    formula = A[i:]
    return coef, formula

# 求解一个formula的元素组成
def f12(formula):
    if len(formula) == 0:
        return {}
    subformula, term, coef = f21(formula)
    element = f22(term)
    subelementdict = f12(subformula)
    elementdict = f23(element, coef, subelementdict)
    return elementdict

# 划分formula
def f21(formula):
    i = len(formula)-1
    while isnumber(formula[i]):
        i -= 1
    coef = formula[i+1:]
    # term为<element>形式
    if formula[i] != ')':
        if isUpper(formula[i]):
            term = formula[i]
            formula = formula[:i]
        else:
            term = formula[i-1:i+1]
            formula = formula[:i-1]
        return formula, term, coef
    else:
        # 找到该')'对应的'('
        j = i-1
        tmp = 1
        while tmp != 0:
            if formula[j] == ')':
                tmp += 1
            if formula[j] == '(':
                tmp -= 1
            j -= 1
        term = formula[j+1:i+1]
        formula = formula[:j+1]
        return formula, term, coef

# 将term划分为element
def f22(term):
    if f31(term):
        return {term: 1}
    else:
        formula = term[1:len(term)-1]
        return f12(formula)

# 将term的元素组成乘上coef然后加上子formula的元素组成
def f23(element, coef, subelementdict):
    if len(coef) == 0:
        coef = 1
    else:
        coef = int(coef)
    for k in element.keys():
        element[k] = element[k]*coef
    for k in element.keys():
        if k in subelementdict.keys():
            subelementdict[k] += element[k]
        else:
            subelementdict[k] = element[k]
    return subelementdict

# 判断term是否为一个element
def f31(term):
    if term[0] == '(':
        return False
    else:
        return True


def f01(expr):
    A = expr.split('+')
    ans = {}
    for a in A:
        elementdict = f10(a)
        for k in elementdict.keys():
            if k in ans.keys():
                ans[k] += elementdict[k]
            else:
                ans[k] = elementdict[k]
    return ans


def f00(equation):
    expr1, expr2 = equation.split('=')

    ans1 = f01(expr1)
    ans2 = f01(expr2)

    if ans1 == ans2:
        return 'Y'
    else:
        return 'N'


ans = []
for i in range(N):  
    ans.append(f00(equations[i]))

print('\n'.join(map(str, ans)), end='')

上面的代码取得了100分.可以说,这份代码是比第一份代码写得更好的.

TODO 总结

¶Lisp概述

¶个人思考

¶计算过程

git使用教程

从零开始的计算机组成原理课设

misaka7690