20140501-大学计算机第3讲-程序与递归-组合-抽象-构造分解

计算系统与程序---程序的作用和本质ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授首先，设计并实现系统可以执行的基本动作(可实现的)，例如“与”动作“或”动作“非”动作“异或”动作那么，复杂的动作呢？系统需要提供复杂的动作复杂的动作千变万化复杂的动作随使用者使用目的的不同而变化计算系统与程序-程序的作用和本质(1)怎样设计并实现一个计算系统?如何设计实现一个基本计算系统？已知的基本事实是:“加减乘除运算都可转换为加减法运算来实现”“加减法运算又可以转换为逻辑运算来实现”“与”“或”“非”战德臣教授指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDORNOT系统((AANDB)ANDC)OR(NOTC))复杂动作拆解开X=AANDBX=XANDCY=NOTCX=XORY程序:由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作如何设计实现一个基本计算系统？计算系统与程序-程序的作用和本质(2)什么是程序?战德臣教授指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDORNOT系统((AANDB)ANDC)OR(NOTC))复杂动作程序执行机构自动解释程序中的各种组合,并按次序调用指令(基本动作)予以执行程序:由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作如何设计实现一个基本的计算系统？计算系统与程序-程序的作用和本质(3)程序能否自动执行?战德臣教授基本动作对基本动作的抽象与控制“与”动作AND“或”动作OR“非”动作NOT复杂动作=基本动作的各种方式的组合(AiXORBi)XORCi((AiXORBi)ANDCi)OR(AiANDBi)……解释这种组合,并按次序调用基本动作予以执行程序执行机构程序指令计算系统=基本动作+指令+程序执行机构指令=对可执行基本动作的抽象，即控制基本动作执行的命令程序=基本动作指令的一个组合或执行序列,用以实现复杂的动作程序执行机构=负责解释程序即解释指令之间组合，并按次序调用指令即调用基本动作执行的机构基本动作计算系统与程序-程序的作用和本质(4)计算系统与程序?战德臣教授基本动作对基本动作的抽象与控制“与”动作AND“或”动作OR“非”动作NOT解释这种组合,并按次序调用基本动作予以执行程序执行机构指令基本动作复杂动作=基本动作的各种方式的组合……程序(AiXORBi)XORCi((AiXORBi)ANDCi)OR(AiANDBi)基本动作对基本动作的抽象与控制“加”动作+“减”动作-“乘”动作x“除”动作复杂动作=基本动作的各种方式的组合(V1+V2)x(V3V4)V5(V1(V2x(V3+V4))-(V5xV6)……解释这种组合,并按次序调用基本动作予以执行程序程序执行机构指令一种较高抽象层次的系统抽象抽象：将经常使用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层次系统的指令被使用一种较低抽象层次的系统计算系统与程序-程序的作用和本质(5)程序：组合-抽象-构造?战德臣教授组合抽象构造什么是程序?程序的本质是什么?计算系统与程序-程序的作用和本质(6)小结运算式的组合-抽象与构造---程序构造示例I-计算对象的定义-构造与计算ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授运算式的组合-抽象与构造---程序构造示例(1)运算组合式?(100+205)由数值，到基本运算组合式中缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在中间([phone]实际的数值前缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在前面将运算符表示的操作应用于后面的一组数值上，求出结果(+10020530040051304)一个运算符可以表示连加，连减等情况，战德臣教授(+100205)(-20050)(*2005)(*20542)(-20542)(+20542)一起练习,书写程序,……由数值，到基本运算组合式运算式的组合-抽象与构造---程序构造示例(1)运算组合式?战德臣教授运算组合式的“嵌套”及其计算过程(+100205)(+(+6040)(-305100))(*(*3(+(*24)(+35)))(+(-107)6))计算过程(*(*3(+(*24)(+35)))(+(-107)6))(*(*3(+88))(+36))(*(*316)9)(*489)432运算式的组合-抽象与构造---程序构造示例(2)如何构造运算组合式---组合战德臣教授(defineheight2)(+(+height40)(-305height))名字的定义：定义名字height与2关联,以后可以用height来表示2一种类型的名字：数值型的名字(+(*50height)(-100height))名字的使用注意：不同类型的对象可以有不同的定义方法。这里统一用define来表示，在具体的程序设计语言中是用不同的方法来定义的命名计算对象和构造中使用名字及计算中以计算对象替换名字运算式的组合-抽象与构造---程序构造示例(3)如何用名字简化运算组合式的构造?--抽象?战德臣教授(definepi3.14159)(defineradius10)(*pi(*radiusradius))(definecircumference(*2piradius))(*circmference20)命名计算对象和构造中使用名字及计算中以计算对象替换名字(*pi(*radiusradius))(*pi(*1010))(*pi100)(*3.14159100)314.159计算运算式的组合-抽象与构造---程序构造示例(3)如何用名字简化运算组合式的构造?--抽象(*circmference20)(*(*2piradius)20)(*(*23.1415910)20)(*62.831820)1256.636计算运算式的组合-抽象与构造---程序构造示例II-运算符的定义-构造-与计算ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授(define(squarex)(*xx))名字的定义：定义名字square为一个新的运算，即过程或称函数另一种类型的名字：运算符型的名字名字的使用注意：不同类型的对象可以有不同的定义方法。这里统一用define来表示，在具体的程序设计语言中是用不同的方法来定义的新运算符，即过程名或函数名形式参数，使用时将被实际参数所替代过程体，用于表示新运算符的具体计算规则，其为关于形式参数x的一种计算组合。(square3)(square6)x2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符运算式的组合-抽象与构造---程序构造示例(4)如何定义、使用和执行新运算符?战德臣教授名字的使用(square10)(square(+28))(square(square3))(square(square(+25)))(define(SumOfSquarexy)(+(squarex)(squarey))(SumOfSquare34)(+(SumOfSquare34)height)x2+y2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符运算式的组合-抽象与构造---程序构造示例(4)如何定义、使用和执行新运算符?战德臣教授(define(NewProca)(SumOfSquare(+a1)(*a2)))(NewProc3)(NewProc(+31))(a+1)2+(a*2)2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符运算式的组合-抽象与构造---程序构造示例(4)如何定义、使用和执行新运算符?战德臣教授(NewProc(+31))的两种计算过程示意(NewProc(+31))(NewProc4)(SumOfSquare(+41)(*42))(SumOfSquare58)(+(Square5)(Square8))(+(*55)(*88))(+2564)89先求值，再代入含名字的运算组合式的计算方法：求值、代入、计算命名新运算符和构造中使用新运算符及执行中以过程替换新运算符运算式的组合-抽象与构造---程序构造示例(5)新运算符的计算/执行方法?战德臣教授(NewProc(+31))的两种计算过程示意(NewProc(+31))(SumOfSquare(+(+31)1)(*(+31)2))(+(Square(+(+31)1)(Square(*(+31)2)))89(+(*(+(+31)1)(+(+31)1))(*(*(+31)2)(*(+31)2)))(+(*(+41)(+41))(*(*42)(*42)))(+(*55)(*88))(+2564)先代入，后求值代入阶段求值阶段含名字的运算组合式的计算方法：代入、求值、计算命名新运算符和构造中使用新运算符及执行中以过程替换新运算符运算式的组合-抽象与构造---程序构造示例(5)新运算符的计算/执行方法?运算式的组合-抽象与构造---程序构造示例III-条件组合式的构造及总结ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授(cond(p1e1)(p2e2)...(pnen))(define(absx)(cond((x0)x)((=x0)0)((x0)(-x))))带有条件的运算组合式运算式的组合-抽象与构造---程序构造示例(7)带有条件的运算组合式如何表达?战德臣教授问题1：用前缀表示法书写下述表达式10+4+(8-(12-(6+45)))3*(6-2)(12-7)问题2：请定义一个过程，求某一数值的立方a3问题3：进一步以问题2定义的过程，再定义一个过程，求某两个数值的立方和。进一步求，并模拟给出计算过程。a3+b353+83运算式的组合-抽象与构造---程序构造示例(6)训练一下?战德臣教授0000)(22xifxxxifxifxxxf(cond(p1e1)(p2e2)...(pnen))(define(fx)(cond((x0)(-(Squarex)x))((=x0)0)((x0)(-x(Squarex)))))问题4：请定义一个过程，计算下列函数运算式的组合-抽象与构造---程序构造示例(7)带有条件的运算组合式如何表达?战德臣教授组合抽象构造运算式的组合-抽象与构造---程序构造示例(8)小结计算对象运算符(即函数)定义构造执行递归的概念ResearchCenteronIntelligentComputingforEnterprises&Services,HarbinInstituteofTechnology战德臣哈尔滨工业大学教授.博士生导师教育部大学计算机课程教学指导委员会委员OKZhanDCOKZhanDC战德臣教授26递归(Recursion)“从前有座山，山里有座庙，庙里有个老和尚，