伯克利CS61A:Lisp解释器开发系列(四):递归解决计数与组合问题
日拱一卒,伯克利YYDS,用Python写一个Lisp解释器(四)
大家好,我是唐亮。
本文源自公众号梁码
我们继续伯克利CS61A方案项目吧,这是该项目的第四篇文章。
课程链接
原始项目文档
Github
在上一篇文章中,我们完整实现了schema渲染器功能,在这篇文章中,我们用我们刚刚开发的翻译器来问一些问题。
我们可以注意到,模式解释器本身不仅是一个递归树程序,而且它在处理其他递归问题时也非常灵活。
您将在Question.scm文件中实现几个未来的问题
尽管您已经完成了模式解释器的开发,但可能存在潜在的错误。
因此,建议先使用通用模式解释器来实现,然后使用新开发的解释器进行测试,以确保您的代码可以正常工作。
实现计数过程,该过程接受一个列表并返回一个二进制列表。
这个二进制列表中的每个元素都是签名和值的组合,如:
开发完成后,测试:
python3ok-q17答案Lisp也有循环语法如果使用循环会简单很多。
但是老师讲的没有涉及到循环,所以我们只能用递归来解决。
如果要递归处理,必然会遇到一个问题,即枚举函数的输入参数只是一个列表,而输出必须带符号。
但问题是我们在递归过程中无法获取实际的签名变量。
所以可以认为只有一个参数的递归是无法解决的,我们至少需要两个参数。
在不改变原有函数签名的情况下,唯一的办法就是使用高阶函数。
在函数内部定义另一个函数,然后我们调用这个函数。
递归逻辑其实并不难。
你可以参考代码,我就不多说了。
实现改变列表的过程,给出总计和分母,总计代表总金额,分母代表我们有的名义值,而标称值为按降序排列。
我们要返回所有能够组成总面值的方式。
例如,总数为10,分母为(25,10,5,1),则答案为:
例如,总数为5,标签为(4,3,2,1),答案为:
在实现过程中,需要用到一个辅助函数:cons-全部。
要实现cons-all功能,必须使用内置的map进程。
cons-all接受一个元素和一个列表,并将该元素插入到列表中每个元素的开头。
例如:
开发后测试:
python3ok-q18解答我们先实现一下总之,这个函数的逻辑并不复杂。
将每个元素传递到占位符中,然后将第一个元素连接在一起。
这个问题提醒我们可以使用内置地图。
映射过程将给定过程应用于列表的所有元素。
当然,我们只需要实现一个函数先加入元素,然后调用map,不需要递归。
我们在任务4的前面用Python编写了一个类似的查询。
我不'不知道你是否还印象深刻。
但是,要求的是所有可能的数量,而且面额限制略有不同,而不是固定的数字,给出了一个整数m,以及当时所有小于m的面额代码:
defcount_partitions(n,m):""Countthewaystopartitionnusingpartsuptom."""ifn==0:return1elifn<0 xss=clean>我们改变位我们将其编写为Python版本:
defconcat(v):returnlambdax:[v]+xdefcount_partitions(n,m):"""Countthewaystopartitionnusingpartsuptom."""ifn==0:return[[]]ifm==0orn<0>=m:ret=list(map(concat(m),count_partitions(n-m,m)))returnret+count_partitions(n,m-1)else:returncount_partitions(n,m-1)接下来你需要做的就是替换上面的代码Python转换为Lisp实现其实只要Python能写,Lisp也能写,虽然语法不同,但核心原理是一样的。
由于Lisp递归还涉及计算参数,因此将它们写在一起会显得非常非常笨拙。
所以这里我们使用define语句来简化代码的编写。
任何非本地表达式都可以写成一个Schemelist。
所以我们可以实现一个可以像生成原理图一样生成另一个程序的过程。
代码重写非常有用,比如我们可以只实现解释器的核心功能,然后通过运行时转码将其他功能转换为解释器支持的核心组件。
这可以简化翻译器的开发。
我不确定这是否是Lisp语言设计逻辑的一部分,但这确实让我感到惊讶。
例如,let语句相当于一个lambda表达式,两者都是根据当前环境创建一个新的框架。
你可以回顾一下Problem15中let语法的定义。
这两个表达式可以用下图表示:
使用此规则来实现let-to-lambda过程,该过程将特殊的let类型转换为lambda表达式。
如果我们引用一个let表达式并将其传递给这个过程,那么我们将得到一个等效的lambda表达式,例如:
为了发挥作用,let-to-lambda必须具有架构语法意识。
由于模式表达式是递归嵌套的,因此let-to-lambda也必须是递归的。
实际上,let-to-lambda结构与scheme_eval函数类似,只不过是用scheme语言实现的。
提示:单个元素包括数字、布尔值、零和符号。
提示:需要先应用zip过程,map过程非常有用
在编码之前,回答确保问题得到解答正确理解
python3ok-q19-u编码后,尝试:
python3ok-q19回答我们先看一下zip过程zip方法的输入是一个nx2的二维列表。
我们返回的结果是一个二维2xn列表。
相当于对数据进行了行列变换。
那么我们需要做的就是从每一行中提取第一个和第二个元素形成两个列表,然后将两个列表连接在一起。
如果不使用循环,看起来就无从下手。
幸运的是,问题提醒我们可以使用地图。
代码如下:
(define(zippairs)(list(mapcarpairs)(mapcadrpairs)))然后let-to-lambda
老师已经给我们定下了这个问题的框架,列出了所有需要考虑的情况。
我们分别看一下这几种情况:
(atom?expr)表达式是一个原子,即数字、符号、零或布尔值,不能再是收到结果后直接返回即可。
该表达式是一个引用语句,与本问题无关。
不需要任何处理,直接返回。
表达式是lambda还是define语句,无法直接判断是否存在关联。
因为define和lambda语句都可以嵌套,并且嵌套语句可以包含let语句,所以我们必须返回嵌套部分。
老师用let语句为我们提取了形状、参数和主体。
形状是类型,参数是参数,主体是主题。
只有body可以嵌套,所以我们必须递归调用body。
我们要处理的核心关键是let语句有两部分,一是值,二是主体。
我们看一下let语句的语法,它首先定义了符号和值之间的一些映射,然后定义了符号计算方法。
我们需要做的是将符号和值映射为lambda过程的形式和参数,将主体映射为lambda过程的主体。
但是最麻烦的是三者之间可能存在嵌套,所以我们不得不使用递归。
否则,由于我们只判断了careexpr,所以需要不断递归调用来判断后面的内容。
这里我直接使用了map过程
更多详情参考代码:
(define(enumerates);BEGINPROBLEM17(define(enum-itterns)(if(null?s)nil(vs(listn(cars))(enum-iter(+n1)(cdrs))))))(enum-iter0s))0这里,这三个即使查询是完成的。
虽然只有三道题,但是完成后还是很有用的。
不仅是方案的语言,还有译者的项目都让我加深了认识。
数值传热学|Python编程实现导热的数值计算——第一类与第三类边界条件
采用数值方法求解热传导问题时,通常将区域划分为网格,分离控制方程,得到网格上温度等物理量的数学公式。在离散和显式解中,前一个时间步的结果用于求解下一个时间步的结果。
相比之下,隐式分离和隐式求解涉及以当前时间步结果作为未知量求解联立方程,尽管其时间步不受约束,但需要迭代求解才能实现方程闭合。
在处理二维静态导热微分控制方程时,可以通过隐式微分法得到具体的公式。
在计算过程中,要注意不同网络节点(m,n)之间的相互作用。
对于第一类边界条件,通过直接设定温度值来求解,而对于第三类边界条件,必须考虑能量守恒问题,保证边界处的能量平衡。
这包括对对流传热、导热率和温度变化的综合研究。
对于角点处的第三类边界条件,求解时需要额外注意能量守恒关系的表达,以保证边界处理的准确性。
在解决具体问题时,例如用隐式离散法解决铝铸件冷却问题时,必须考虑铝的导热系数、密度、比热容和热扩散率等参数。
通过确定计算场的大小、初始铸造温度和环境温度以及对流传热系数,可以创建问题的数学模型。
以陶老师2021年数值传热任务中的第一题为例。
这个问题是基于铝铸件的冷却。
导热系数为237W/(m·K),密度为2700kg/m3。
铝材料的比热容为880J/(kg·K),热扩散率为9.975×10-5m2/s,解决了0.2m×0.2m²计算面积内的散热问题。
初始条件确定铸造温度为900K,环境冷却液温度为300K,对流传热系数为10^6W/(m2K)。
通过数值方法求解,可以获得铸件冷却过程的温度分布结果。
![](https://tse2-mm.cn.bing.net/th/id/OIP-C.XJi4kzvPWbyrdOGqnSR7bwHaDN?w=.jpg)
Python完成期末大作业:简易计算器【案例分享】
在本次分享中,我们将讨论如何使用Python来解决最终的任务——一个简单的计算器案例。首先,我们需要明确我们的目标:完成一个简单的计算器,可以进行加减乘除运算,并提供清晰的按钮功能。
接下来我们开始编写代码。
我们首先导入必要的模块,例如用于界面设计的Tkinter模块。
接下来,指定形状对象并设置窗口的大小和位置,例如长和宽为300x300,距窗口左上角的距离为150+150。
定义一个列表,收集输入内容,实现数字显示功能。
对于加减乘除运算,我们可以直接使用Python运算符进行计算。
为了简化用户的操作,添加相同的按钮来计算结果和清除按钮来清除列表。
在界面设计中,保证美观和实用,比如按钮布局、字体大小等。
最后,不要忘记包含一个消息循环,以保持窗口始终显示,以方便用户。
今天的文章到此结束,我希望它能激励您完成期末作业。
我是小熊猫,期待下一篇文章见到你!
相关文章
![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
SQL数据库误删恢复攻略:备份与数据恢复...
2024-12-16 08:54:51![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
Windows环境下MySQL服务管理:...
2024-12-15 17:38:13![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
MySQL数据恢复攻略:误删数据、表恢复...
2024-12-14 21:59:00![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
轻松解决10061 MySQL错误:实用...
2024-12-21 13:48:22![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
SQLServer本地数据库访问指南:启...
2024-12-18 03:31:09![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
深入解析MySQL事务隔离级别:从REP...
2024-12-18 15:34:08![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
SQL Server远程连接配置指南:轻...
2024-12-16 01:42:38![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
SQL合并字段技巧:轻松实现数据连接与显...
2024-12-17 10:58:25![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)
MySQL数据存储解析:文件类型及默认位...
2024-12-15 18:14:48![](https://www.occasioneitalia.net/static/assets/images/nopic.gif)