程序与递归组合抽象与构造.ppt

《程序与递归组合抽象与构造.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第6讲程序与递归：组合-抽象与构造--程序是实现系统复杂功能的一种重要手段--程序的本质是组合、抽象与构造--构造的基本手段是递归，一种表达相似性对象及动作的无限性构造的方法程序与递归：组合-抽象与构造1.程序的作用和本质?程序的作用和本质----计算系统与程序----程序：组合、抽象与构造首先，设计并实现系统可以执行的基本动作(可实现的)，例如“与”动作“或”动作“非”动作“异或”动作那么，复杂的动作呢？系统需要提供复杂的动作复杂的动作千变万化复杂的动作随使用者使用目的的不同而变化复杂的动作是通过

2、对基本动作进行各种组合来实现的1.程序的作用和本质1.1怎样设计并实现一个计算系统?如何设计实现一个基本计算系统？已知的基本事实是:“加减乘除运算都可转换为加法运算来实现”“加法运算又可以转换为逻辑运算来实现”“基本的逻辑运算与、或、非、异或等可通过门电路予以实现”则基本计算系统可以如下实现……指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDORNOT系统((AANDB)ANDC)OR(NOTC))复杂动作拆解开X=AANDBX=XANDCY=NOTCX=XORY程序:由基本动作指令

3、构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作如何设计实现一个基本计算系统？1.程序的作用和本质1.2什么是程序?指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDORNOT系统((AANDB)ANDC)OR(NOTC))复杂动作程序执行机构自动解释程序中的各种组合,并按次序调用指令(基本动作)予以执行程序:由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作如何设计实现一个基本的计算系统？1.程序的作用和本质1.3程序能否自动执行?基本动作对基本动作的

4、抽象与控制“与”动作AND“或”动作OR“非”动作NOT复杂动作=基本动作的各种方式的组合(AiXORBi)XORCi((AiXORBi)ANDCi)OR(AiANDBi)……解释这种组合,并按次序调用基本动作予以执行程序执行机构程序指令计算系统=基本动作+指令+程序执行机构指令=对可执行基本动作的抽象，即控制基本动作执行的命令程序=基本动作指令的一个组合或执行序列,用以实现复杂的动作程序执行机构=负责解释程序即解释指令之间组合，并按次序调用指令即调用基本动作执行的机构基本动作1.程序的作用和本质1

5、.4计算系统与程序?基本动作对基本动作的抽象与控制“加”动作+“减”动作-“乘”动作x“除”动作复杂动作=基本动作的各种方式的组合(V1+V2)x(V3V4)V5(V1(V2x(V3+V4))-(V5xV6)……解释这种组合,并按次序调用基本动作予以执行程序程序执行机构指令一种较高抽象层次的系统抽象抽象：将经常使用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层次系统的指令被使用一种较低抽象层次的系统1.程序的作用和本质1.5程序：组合-抽象-构造?程序构造示例(I)----运算组

6、合式的表达----组合、抽象与构造----命名计算对象和构造中使用名字及计算中以计算对象替换名字程序与递归：组合-抽象与构造2.程序构造示例(I)2.程序构造示例(I)2.1运算组合式?(100+205)由数值，到基本运算组合式中缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在中间(+100205)100205实际的数值前缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在前面将运算符表示的操作应用于后面的一组数值上，求出结果(+10020530040051304)一个运算符

7、可以表示连加，连减等情况，(+100205)(-20050)(*2005)(*20542)(-20542)(+20542)一起练习,书写程序,……由数值，到基本运算组合式2.程序构造示例(I)2.1运算组合式?运算组合式的“嵌套”及其计算过程(+100205)(+(+6040)(-305100))(*(*3(+(*24)(+35)))(+(-107)6))计算过程(*(*3(+(*24)(+35)))(+(-107)6))(*(*3(+88))(+36))(*(*316)9)(*489)4322.程

8、序构造示例(I)2.2如何构造运算组合式---组合(defineheight2)(+(+height40)(-305height))名字的定义：定义名字height与2关联,以后可以用height来表示2一种类型的名字：数值型的名字(+(*50height)(-100height))名字的使用注意：不同类型的对象可以有不同的定义方法。这里统一用define来表示，在具体的程序设计语言中是用不同的方法来定义的命名计算对象和构造中使用名字及计算中以计算对象替换名字2.程序