程序与递归-组合-抽象与构造.ppt
《程序与递归-组合-抽象与构造.ppt》由会员分享,可在线阅读,更多相关《程序与递归-组合-抽象与构造.ppt(56页珍藏版)》请在咨信网上搜索。
1、第6讲 程序与递归:组合-抽象与构造-程序是实现系统复杂功能的一种重要手段-程序的本质是组合、抽象与构造-构造的基本手段是递归,一种表达相似性对象及动作的无限性构造的方法程序与递归:组合-抽象与构造1.程序的作用和本质?程序的作用和本质-计算系统与程序-程序:组合、抽象与构造首先,设计并实现系统可以执行的基本动作(可实现的),例如“与”动作“或”动作“非”动作“异或”动作那么,复杂的动作呢?系统需要提供复杂的动作复杂的动作千变万化复杂的动作随使用者使用目的的不同而变化复杂的动作是通过对基本动作进行各种组合来实现的1.程序的作用和本质1.1 怎样设计并实现一个计算系统?如何设计实现一个基本计算系
2、统?已知的基本事实是:“加减乘除运算都可转换为加法运算来实现”“加法运算又可以转换为逻辑运算来实现”“基本的逻辑运算与、或、非、异或等可通过门电路予以实现”则基本计算系统可以如下实现 指令:控制基本动作执行的命令“与”动作“或”动作“非”动作ANDOR NOT系统(A AND B)AND C)OR(NOT C)复杂动作拆解开X=A AND B X=X AND CY=NOT C X=X OR Y程序:由基本动作指令构造的,若干指令的一个组合或一个执行序列,用以实现复杂动作如何设计实现一个基本计算系统?1.程序的作用和本质1.2 什么是程序?指令:控制基本动作执行的命令“与”动作“或”动作“非”动
3、作ANDOR NOT系统(A AND B)AND C)OR(NOT C)复杂动作程序执行机构自动解释程序中的各种组合,并按次序调用指令(基本动作)予以执行程序:由基本动作指令构造的,若干指令的一个组合或一个执行序列,用以实现复杂动作如何设计实现一个基本的计算系统?1.程序的作用和本质1.3 程序能否自动执行?基本动作 对基本动作的 抽象与控制“与”动作 AND“或”动作 OR“非”动作 NOT复杂动作=基本动作的各种方式的组合(Ai XOR Bi)XOR Ci(Ai XOR Bi)AND Ci)OR(Ai AND Bi)解释这种组合,并按次序调用基本动作予以执行程序执行机构程序指令计算系统=基
4、本动作+指令+程序执行机构指令=对可执行基本动作的抽象,即控制基本动作执行的命令程序=基本动作指令的一个组合或执行序列,用以实现复杂的动作程序执行机构=负责解释程序即解释指令之间组合,并按次序调用指令即调用基本动作执行的机构基本动作1.程序的作用和本质1.4 计算系统与程序?基本动作 对基本动作的 抽象与控制“加”动作 +“减”动作 -“乘”动作 x“除”动作 复杂动作=基本动作的各种方式的组合(V1+V2)x(V3 V4)V5(V1 (V2 x(V3+V4)-(V5 x V6)解释这种组合,并按次序调用基本动作予以执行程序程序执行机构指令一种较高抽象层次的系统抽象抽象:将经常使用的、可由低层
5、次系统实现的一些复杂动作,进行命名,以作为高层次系统的指令被使用一种较低抽象层次的系统1.程序的作用和本质1.5 程序:组合-抽象-构造?程序构造示例(I)-运算组合式的表达-组合、抽象与构造-命名计算对象和构造中使用名字及计算中以计算对象替换名字程序与递归:组合-抽象与构造2.程序构造示例(I)2.程序构造示例(I)2.1 运算组合式?(100+205)由数值,到基本运算组合式 中缀表示法,用运算符(即前述的指令)将两个数值组合起来,运算符在中间(+100 205)100205实际的数值前缀表示法,用运算符(即前述的指令)将两个数值组合起来,运算符在前面将运算符表示的操作应用于后面的一组数值
6、上,求出结果(+100 205 300 400 51 304)一个运算符可以表示连加,连减等情况,(+100 205)(-200 50)(*200 5)(*20 5 4 2)(-20 5 4 2)(+20 5 4 2)一起练习,书写程序,由数值,到基本运算组合式 2.程序构造示例(I)2.1 运算组合式?运算组合式的“嵌套”及其计算过程(+100 205)(+(+60 40)(-305 100)(*(*3 (+(*2 4)(+3 5)(+(-10 7)6)计算过程(*(*3 (+(*2 4)(+3 5)(+(-10 7)6)(*(*3 (+8 8)(+3 6)(*(*3 16)9)(*48 9
7、)4322.程序构造示例(I)2.2 如何构造运算组合式-组合(define height 2)(+(+height 40)(-305 height)名字的定义:定义名字height与2关联,以后可以用height来表示2一种类型的名字:数值型的名字(+(*50 height)(-100 height)名字的使用注意:不同类型的对象可以有不同的定义方法。这里统一用define来表示,在具体的程序设计语言中是用不同的方法来定义的命名计算对象和构造中使用名字及计算中以计算对象替换名字2.程序构造示例(I)2.3 如何用名字简化运算组合式的构造?-抽象(define pi 3.14159)(defi
8、ne radius 10)(*pi (*radius radius)(define circumference (*2 pi radius)(*circmference 20)命名计算对象和构造中使用名字及计算中以计算对象替换名字2.程序构造示例(I)2.3 如何用名字简化运算组合式的构造?-抽象程序构造示例(II)-组合、抽象与构造-命名新运算符和构造中使用新运算符及执行中以过程替换新运算符-带有条件的运算组合式程序与递归:组合-抽象与构造3.程序构造示例(II)(define(square x)(*x x)名字的定义:定义名字square为一个新的运算,即过程或称函数另一种类型的名字:运算
9、符型的名字名字的使用注意:不同类型的对象可以有不同的定义方法。这里统一用define来表示,在具体的程序设计语言中是用不同的方法来定义的新运算符,即过程名或函数名形式参数,使用时将被实际参数所替代过程体,用于表示新运算符的具体计算规则,其为关于形式参数x的一种计算组合。(square 3)(square 6)x2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符3.程序构造示例(II)3.1 如何用名字简化运算组合式的构造?-抽象名字的使用(square 10)(square (+2 8)(square (square 3)(square (square(+2 5)(define(Su
10、mOfSquare x y)(+(square x)(square y)(SumOfSquare 3 4)(+(SumOfSquare 3 4)height)x2+y2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符3.程序构造示例(II)3.2 程序构造组合与抽象(define(NewProc a)(SumOfSquare(+a 1)(*a 2)(NewProc 3)(NewProc(+3 1)(a+1)2+(a*2)2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符3.程序构造示例(II)3.2 程序构造组合与抽象(NewProc(+3 1)的两种计算过程示意(NewP
11、roc(+3 1)(NewProc 4)(SumOfSquare(+4 1)(*4 2)(SumOfSquare 5 8)(+(Square 5)(Square 8)(+(*5 5)(*8 8)(+25 64)89先求值,再代入含名字的运算组合式的计算方法:求值、代入、计算命名新运算符和构造中使用新运算符及执行中以过程替换新运算符3.程序构造示例(II)3.3 构造程序的执行求值、代入与计算(NewProc(+3 1)的两种计算过程示意(NewProc(+3 1)(SumOfSquare(+(+3 1)1)(*(+3 1)2)(+(Square (+(+3 1)1)(Square (*(+3
12、1)2)89(+(*(+(+3 1)1)(+(+3 1)1)(*(*(+3 1)2)(*(+3 1)2)(+(*(+4 1)(+4 1)(*(*4 2)(*4 2)(+(*5 5)(*8 8)(+25 64)先代入,后求值代入阶段求值阶段含名字的运算组合式的计算方法:代入、求值、计算命名新运算符和构造中使用新运算符及执行中以过程替换新运算符3.程序构造示例(II)3.3 构造程序的执行求值、代入与计算(cond ()().()(define (abs x)(cond (x 0)x)(=x 0)0)(x 0)(-x)3.程序构造示例(II)3.4 有条件的运算如何表达?带有条件的运算组合式u问题
13、1:用前缀表示法书写下述表达式 10+4+(8-(12-(6+45)3*(6-2)(12-7)u问题2:请定义一个过程,求某一数值的立方a3u问题3:进一步以问题2定义的过程,再定义一个过程,求某两个数值的立方和。进一步求 ,并模拟给出计算过程。a3+b353+833.程序构造示例(II)3.5 你能表达与构造程序吗?(cond ()().()(define (f x)(cond (x 0)(-(Square x)x)(=x 0)0)(=1时 等比数列递推公式a0=5an=an-1 20 当n=1时 第1项(或前K项)的值是已知的递推基础;由第n项或前n项计算第n+1项递推规则/递推步骤;由前
14、向后,可依次计算每一项等差数列的产生a0=5a1=a0+3=8a2=a1+3=11a3=a2+3=14a4=a3+3=17 28数学中的数学归纳法u数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法,该方法能用有限的步骤解决无穷对象的论证问题。u由归纳基础和归纳步骤构成:l假定对一切正整数n,有一个命题P(n),若以下证明成立,则P(n)为真。l(1)归纳基础:证明P(1)为真;l(2)归纳步骤:证明对任意的i,若P(i)为真,则P(i+1)也为真。证明:(1)归纳基础:当n=1时,等式成立即1=1;(2)归纳步骤:设对任意k,P(k)成立,即1+3+5+(2K-1)=K2.则 P(K
15、+1)=1+3+5+(2K-1)+(2(K+1)-1)=K2+2K+1=(K+1)2,则当P(k)成立时P(K+1)也成立,根据数学归纳法该命题得证。证毕。求证命题P(n)“从1开始连续n个奇数之和是n的平方”即公式:1+3+5+(2n-1)=n2成立。4.递归的概念4.3 如何表达延续不断却相似或重复的事物或过程?什么是递归?递归的思想源于数学的递推式和数学归纳法。递归是一种表达相似性对象及动作的无限性构造的方法。u递归是一种关于抽象的表达方法-用递归定义无限的相似事物u递归是一种算法或程序的构造技术-自身调用自身,高阶调用低阶,构造无限的计算步骤u递归是一种典型的计算过程-由后向前代入,再
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序 递归 组合 抽象 构造
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【1587****927】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【1587****927】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。