计算思维导论 课件 第3、4讲-组合-抽象-递归与迭代、机器程序执行-CPU与存储器

第3讲程序与递归战德臣哈尔滨工业大学计算学部教学委员会主任国家教学名师组合抽象构造递归迭代用递归定义用递归构造递归计算/执行计算系统程序计算对象运算符(即函数)定义构造执行递归/迭代基础递归/迭代步骤程序与递归概述程序构造思维概述体验示例第3讲程序与递归一、计算系统与程序-程序的作用和本质二、程序构造示例—利用运算组合式进行构造三、什么是递归四、两种不同的递归函数--递归与迭代首先，设计并实现系统可以执行的基本动作(可实现的)，例如： “与”动作、 “或”动作、 “非”动作、 “异或”动作“与”动作“或”动作“非”动作系统那么，复杂的动作呢？已知：（1）“加减乘除运算都可转换为加减法运算来实现”（2）“加减法运算又可以转换为逻辑运算来实现”计算系统与程序怎样构造一台计算机器？“与”“或”“非”指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDOR

NOT系统((AANDB)ANDC)OR(NOTC))复杂动作拆解开X=AANDBX=XANDCY=NOTCX=XORY程序:由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作计算系统与程序构造计算机器的基本思维：程序指令：控制基本动作执行的命令“与”动作“或”动作“非”动作ANDOR

NOT系统((AANDB)ANDC)OR(NOTC))复杂动作拆解开X=AANDBX=XANDCY=NOTCX=XORY程序:由基本动作指令构造的，若干指令的一个组合或一个执行序列，用以实现复杂动作程序执行机构自动解释程序中的各种组合,并按次序调用指令(基本动作)予以执行计算系统与程序自动计算机器：程序与程序执行机构基本动作对基本动作的

抽象与控制“与”动作AND“或”动作OR“非”动作NOT复杂动作=基本动作的各种方式的组合(AiXORBi)XORCi((AiXORBi)ANDCi)OR(AiANDBi)……解释这种组合,并按次序调用基本动作予以执行程序执行机构程序指令计算系统

=基本动作+指令+程序执行机构指令

=对可执行基本动作的抽象，即控制基本动作执行的命令程序=基本动作指令的一个组合或执行序列,用以实现复杂的动作程序执行机构=负责解释程序即解释指令之间组合并按次序调用指令即调用基本动作执行的机构基本动作计算系统与程序-程序的作用和本质(4)计算系统与程序?计算系统与程序自动计算机器：程序与程序执行机构分层式构造基本动作对基本动作的

抽象与控制“加”动作+“减”动作-“乘”动作x“除”动作

复杂动作=基本动作的各种方式的组合(V1+V2)x(V3

V4)

V5(V1

(V2x(V3+V4))-(V5xV6)……解释这种组合,并按次序调用基本动作予以执行程序程序执行机构指令一种较高抽象层次的系统抽象抽象：将经常使用的、可由低层次系统实现的一些复杂动作，进行命名，以作为高层次系统的指令被使用一种较低抽象层次的系统计算系统与程序-程序的作用和本质(5)程序：组合-抽象-构造?高抽象层次vs.低抽象层次计算系统与程序组合抽象构造什么是程序?程序的本质是什么?计算系统与程序程序的作用和本质第3讲程序与递归一、计算系统与程序-程序的作用和本质二、程序构造示例—利用运算组合式进行构造三、什么是递归四、两种不同的递归函数--递归与迭代(100+205)由数值，到基本运算组合式中缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在中间(+100205)100205实际的数值前缀表示法,用运算符(即前述的指令)将两个数值组合起来，运算符在前面将运算符表示的操作应用于后面的一组数值上，求出结果(+10020530040051304)一个运算符可以表示连加，连减等情况程序构造示例—利用运算组合式进行构造运算组合式—一种程序的表达方法(+100205)(-20050)(*2005)(*20542)(-20542)(+20542)一起练习,书写程序,……由数值，到基本运算组合式(+100205)计算对象运算符()-组合式的边界一个组合式内只能有一个运算符，可有多个计算对象基本运算符只有+、-、*、/，可以被识别和计算。程序构造示例—利用运算组合式进行构造运算组合式—一种程序的表达方法(+100205)(+(+6040)(-305100))(*(*3(+(*24)(+35)))(+(-107)6))计算过程(*(*3(+(*24)

(+35)))(+(-107)6))(*(*3(+8

8))(+36))(*(*316)9)(*489)432(运算符1计算对象1计算对象2)(运算符2计算对象3计算对象4)(运算符1

(运算符2计算对象3计算对象4)

计算对象2)组合嵌套程序构造示例—利用运算组合式进行构造运算组合式的“组合-嵌套”（构造）及其计算过程（执行）测练题：运算组合式(+(+203040)

(*25))的结果是_____。900

10097630ABCD提交前述没有正确答案E单选题1分(defineheight2)(+(+height

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

height2)计算对象运算符程序构造示例—利用运算组合式进行构造用名字替代计算对象（构造）(definepi3.14159)(defineradius10)(*pi(*radiusradius))(definecircumference(*2piradius))(*circmference20)(*pi(*radiusradius))(*pi(*1010))(*pi100)(*3.14159100)314.159计算(*circmference20)(*(*2piradius)20)(*(*23.1415910)20)(*62.831820)1256.636计算程序构造示例—利用运算组合式进行构造用名字替代计算对象（构造）测练题：已知下列运算组合式

(defineproduct(+(*66)

(*88)))

(definesumofproduct(*productproduct))

(+sumofproduct

sumofproduct)这段运算组合式最终的计算结果是_____。20000

10000100000000400ABCD提交前述没有正确答案E单选题1分计算对象2运算符(define(squarex)(*xx))名字的定义：定义名字square为一个新的运算，即过程或称函数。另一种类型的名字：运算符型的名字名字的使用注意：不同类型的对象可以有不同的定义方法。这里统一用define来表示，在具体的程序设计语言中是用不同的方法来定义的新运算符，即过程名或函数名形式参数，使用时将被实际参数所替代过程体，用于表示新运算符的具体计算规则，其为关于形式参数x的一种计算组合。(square3)(square6)x2命名新运算符和构造中使用新运算符及执行中以过程替换新运算符(define(squarex)(*xx))计算对象1程序构造示例—利用运算组合式进行构造定义新运算符与使用新运算符（构造）(square10)(square(+28))(square(square3))(square(square(+25)))(define(SumOfSquarexy)(+(squarex)(squarey)))(SumOfSquare34)(+(SumOfSquare34)height)x2+y2程序构造示例—利用运算组合式进行构造新运算符定义与构造示例(define(NewProca)(SumOfSquare(+a1)(*a2)))(NewProc3)(NewProc(+31))(a+1)2+(a*2)2程序构造示例—利用运算组合式进行构造新运算符定义与构造示例(NewProc(+31))(NewProc4)(SumOfSquare(+41)(*42))(SumOfSquare58)(+(Square5)(Square8))(+(*55)(*88))(+2564)89先求值，再代入求值、代入、计算程序构造示例—利用运算组合式进行构造运算组合式的执行（计算方法1）代入、求值、计算(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)先代入，后求值代入阶段求值阶段代入到只有基本运算符时再开始求值程序构造示例—利用运算组合式进行构造运算组合式的执行（计算方法2）测练题：对于计算式，其正确的运算组合式(前缀表示法)为_____。(/(+10/20+84)(+*36*82)

((10+(20/(8+4)))/((3*6)+(8*2)))

(/(+10(/20(+84)))(+(*36)(*82)))(/(/20(+10(+84)))(*(+36)(+82)))ABCD提交前述没有正确答案E单选题1分对于计算式，其正确的运算组合式(前缀表示法)为_____。(A)(/(+10/20+84)(+*36*82))；(B)((10+(20/(8+4)))/((3*6)+(8*2)))；(C)(/(+10(/20(+84)))(+(*36)(*82)))；(D)(/(/20(+10(+84)))(*(+36)(+82)))。(/操作数1操作数2)(/(+10操作数a2)

(+操作数a3操作数a4))

(/(+10(/20(+84)

))

(+操作数a3操作数a4))

(/(+10

(/20(+84)

))

(+(*36)

(*82)))

程序构造示例—利用运算组合式进行构造构造与执行练习测练题：请定义一个过程，求某一数值的立方进一步以前述定义的过程，再定义一个过程，求某两个数值的立方和。进一步求，并模拟给出计算过程。(definecube(*aaa))(definesumofcube(+cubecube)(sumofcube23)35ABCD提交a3a3+b323+33(define(func1x)(*xxx))(define(func2xy)(+(func1x)(func1y)))(func223)35(define(cubex)(*aaa))(define(sofcubexy)(+(cubea)(cubeb)))(sofcube23)35(define(cubea)(*aaa))(define(sumofcubeab)(*(cubea)(cubeb)))(sumofcube23)35单选题1分第3讲程序与递归一、计算系统与程序-程序的作用和本质二、程序构造示例—利用运算组合式进行构造三、什么是递归四、两种不同的递归函数--递归与迭代(*(*(*11)2)3)(*(*11)2)(*11)27(*…(*(*(*11)2)3)…n)怎样在表达中既去掉省略号，而又能表达近乎无限的内容?怎样表达n!的计算过程什么是递归？为什么需要递归？28什么是递归？递归的典型视觉形式---自相似性事物的无限重复性构造递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由第n项或前n项定义第n+1项。即:h(n+1)

=g(h(n),n)，g是需要明确给出的，以说明h(n+1)怎样由h(n)和n构造出来。什么是递归？【基本概念】递归30(1)某人的双亲(父母)是他的祖先（递归基础）---h(1)直接给出(2)某人祖先的双亲(父母)同样是某人的祖先（递归步骤/公式）---h(n+1)=g(h(n),n)

---n:第几代；h(n)是第几代祖先；g是h(n+1)与h(n)和n的关系曾祖父曾祖母(祖父的)父(祖父的)母祖父祖母(父的)父(父的)母父母外祖父外祖母(母的)父(母的)母某人h(1)h(2)h(3)h(n)h(0)h(n+1)怎样递归？【示例】怎样定义你的祖先?递归的理解比较难递归思维是计算机最重要的特征想学计算机就要理解递归思维什么是递归？31一个数列的第n项an与该数列的其他一项或多项之间存在某种对应关系，被表达为一种公式，称为递推式等差数列递推公式

a0=5 an=an-1+3当n>=1时第1项(或前K项)的值是已知的—递推基础；由第n项或前n项计算第n+1项—递推规则/递推步骤；由前向后，可依次计算每一项等差数列的产生

a0=5 a1=a0+3=8 a2=a1+3=11 a3=a2+3=14 a4=a3+3=17

……什么是递归？数学的递推式32(运算符1操作数1操作数2)(运算符2操作数a操作数b)

(运算符1(运算符2操作数a操作数b)操作数2) (/(+205(/(+153)

(-90

(88))))

(-200(

105)))

(/(+205(/(+153-90

(88))))

(-200(

105)))

怎样表达运算组合式的层层构造--构造规则?怎样判断一个运算组合式是否符合构造规则?这个式子是有问题的哟计算规则的构造与正确性判断什么是递归？为什么需要递归？33(/操作数1操作数2)(/(+104操作数a2)

操作数2)

(/(+104(-8操作数a3))操作数2)

(/(+104(-8(-12操作数a4)))操作数2)

(/(+104(-8(-12(+6操作数a5))))操作数2)

(/(+104(-8(-12(+6(/45)))))操作数2)--------------------------------------------------------------------------(/45)(+6(/45))(-12(+6(/45)))(-8(-12(+6(/45))))(+104(-8(-12(+6(/45)))))(/(+104(-8(-12(+6(/45)))))操作数2

)h(n+1)h(1)h(0)h(2)h(n)h(n)h(n+1)h(1)h(n-1)h(0)(1)单一数值是运算组合式---h(0)直接给出，递归基础(2)如果X,Y是运算组合式，则

(+XY),(*XY),(-XY),(/XY)也是运算组合式---h(n+1)=g(h(n),n)，即递归步骤说明：这里不允许连加、连减情况发生---n:第几层；h(n)是第几层表达式；g是(运算符操作数1操作数2)，指出h(n+1)与h(n)和n的关系(/(+104(-8(-12(+6(/45)))))(-158))是运算组合式吗?什么是递归？运算组合式的递归定义示例第3讲程序与递归一、计算系统与程序-程序的作用和本质二、程序构造示例—利用运算组合式进行构造三、什么是递归四、递归与迭代35Fibonacci数列，无穷数列1，1，2，3，5，8，13，21，34，55，……，

F(0)=1; F(1)=1; F(2)=F(1)+F(0)=2; F(3)=F(2)+F(1)=3; F(4)=F(3)+F(2)=3+2=5;……递归定义递推计算/迭代计算/迭代执行递归与迭代一种类型的递归函数：定义是递归的,但执行可以是递归的也可以是迭代的计算规则的表达—告诉执行者要递归计算执行者要一步一步地完成计算获得结果36递归与迭代另一种类型的递归函数：定义是递归的,但执行也是递归的（用迭代不容易完成）阿克曼递归函数

A(1,n)=?测练题：

n+1ABCD提交n+3n+2A(1,n)=?算不出来单选题1分38递归与迭代另一种类型的递归函数：定义是递归的,但执行也是递归的（用迭代不容易完成）阿克曼递归函数

A(1,n)=A(0,A(1,n-1))

=A(1,n-1)+1

=A(0,A(1,n-2))+1

=A(1,n-2)+2=A(1,n-3)+3

=...

=A(1,n-n)+n

=A(1,0)+n

=A(0,1)+n

=2+nA(1,n)=A(0,A(1,n-1))

=A(0,A(0,A(1,n-2))) =A(0,A(0,A(0,A(1,n-3))))=...

=A(0,A(0,…A(0,A(1,n-n)))) =A(0,A(0,…A(0,A(1,0)))) =A(0,A(0,…A(0,A(0,1)))) =A(0,A(0,…A(0,2))) =A(0,A(0,…A(0,3))) =A(0,n+1)

=n+239A(1,n)=A(0,A(1,n-1))=A(0,<…代入前式计算过程>)=A(0,n+1)=n+2。A(2,1)=A(1，A(2，0))

--A(2,1)按m,n>0公式代入=A(1，A(1，1))

--A(2,0)按n=0公式代入=A(1，A(0，A(1，0)))

--A(1,1)按m,n>0公式代入=A(1，A(0，A(0，1)))

--A(1,0)按n=0公式代入=A(1，A(0，2))

--A(0,1)按m=0公式代入=A(1，3)

--A(0,2)按m=0公式代入=A(0，A(1，2))

--A(1,3)按m,n>0公式代入=A(0，A(0，A(1，1)))

--A(1,2)按m,n>0公式代入=A(0，A(0，A(0，A(1，0))))

--A(1,1)按m,n>0公式代入=A(0，A(0，A(0，A(0,1)))

--A(1,0)按n=0公式代入=A(0，A(0，A(0，2)))

--A(0,1)按m=0公式代入=A(0，A(0，3))=A(0，4)=5。--依次按m=0公式代入递归与迭代另一种类型的递归函数：定义是递归的,但执行也是递归的（用迭代不容易完成）函数本身是递归的，函数的变量也是递归的

递归定义递归计算/递归执行由后向前代入，再由前向后计算阿克曼递归函数

计算规则的表达—告诉执行者要递归计算执行者要一步一步地完成计算获得结果h(0)h(n+1)h(0)h(n+1)寻找路径沿路径计算沿一致路径计算h(0)h(n+1)可能计算路径并不同迭代/递推递归通常，只能由函数结构实现在前次结果基础上进行计算可采用循环结构实现重复性无限性构造的思维--递归与迭代?(6)两种不同的递归函数--递归与递推(迭代)的差别?递归与迭代递归与迭代的差异梵天塔(汉诺塔)问题：有三根柱子，梵天将64个直径大小不一的金盘子按照从大到小的顺序依次套放在第一根柱子上形成一座金塔，要求每次只能移动一个盘子，盘子只能在三根柱子上来回移动不能放在他处，在移动过程中三根柱子上的盘子必须始终保持大盘在下小盘在上。递归与迭代汉诺塔问题汉诺塔问题求解示意ABCABCABCABCABCABC递归与迭代ABCABCABCABCABCABC递归与迭代汉诺塔问题求解示意ABCABCABCMain(){//假设有5个盘子的汉诺塔Hanoi(5,“A”,“B”,“C”);}intHanoi(intN,intX,intY,intZ){//该函数是将N个盘子从X柱，以Z柱做中转，移动到Y柱上

IfN>1Then{//先把n-1个盘子从X放到Z上(以Y做中转) Hanoi(N-1,X,Z,Y);//然后把X上最下面的盘子放到Y上 Printf(“%d%d”,X,Y);//接着把n-1个盘子从Z上放到Y上(以X做中转) Hanoi(N-1,Z,Y,X);}Else

{//只有一个盘子时，直接把它从X放到Y上

Printf(“%d%d”,X,Y);}}

递归与迭代汉诺塔问题求解示意longintFact(intn){longintx; If(n>1){x=Fact(n-1);/*递归调用*/returnn*x;}elsereturn1;/*递归基础*/}n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(n)

递归与迭代递归法求n!的算法或程序n>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nn>1返回结果1X=Fact(n-1)NY返回结果n*X开始结束传进的参数nFact(4)4返回4!=24Fact(3)返回3!=624Fact(2)返回2!=2Fact(1)返回1!=13622114

63

22

1126递归与迭代递归程序的执行过程：利用【堆栈】保存待计算的数据123456Fact(4)的程序断点

Fact(3)的程序断点Fact(4)的程序断点

Fact(2)的程序断点Fact(3)的程序断点Fact(4)的程序断点

堆栈：后进先出longintFact(intn){intcounter；

longproduct=1;forcounter=1tonstep1{product=product*counter；}/*迭代*/returnproduct;} CounterProduct初始值1

Fact(5)的执行过程【示例】求n!的算法或程序--用迭代方法构造：循环-替代-递推递归与迭代迭代程序的执行过程?循环第1次 1 1循环第2次

2 2循环第3次

3 6循环第4次

4

24循环第5次

5

120退出循环

6

120测练题：已知右侧程序，n=4,程序执行完时,counter,product的值分别是多少？

4，24ABCD提交5，1205，246，120longintFact(intn){intcounter；

longproduct=1;forcounter=1tonstep1{product=product*counter；}/*迭代*/returnproduct;} 单选题1分递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由前n项或第n项定义第n+1项；由低阶h(k)且k<n，来构造高阶h(n+1)；即:h(n+1)=g(h(n),n)，或者h(n+1)=g(h(k),n,k)形式，g是需要明确给出的，以说明h(n+1)怎样由h(k),k和n构造出来。递归是一种关于抽象的表达方法---用递归定义无限的相似事物递归是一种算法或程序的构造技术---自身调用自身，高阶调用低阶，构造无限的计算步骤递归是一种典型的计算/执行过程---由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终结果，即由前向后计算用递归定义用递归构造递归计算/执行程序与递归关于递归的理解什么是程序?程序的本质是什么?计算系统的构造程序---对基本动作的组合计算系统---执行程序的系统程序本质---组合、抽象、构造与执行实例层面：运算组合式概念层面：计算系统与程序程序构造的基本方法：递归与迭代组合/抽象

递归递归定义、递归算法、递归计算相互关联且递进的方式展开与贯通概念/原理与案例相结合知识伴随思维，思维贯通知识程序与递归程序构造思维小结递归函数又被称为可计算函数。递归理论也被称为可计算理论。是计算机类学科理论研究的基础组合抽象构造递归迭代用递归定义用递归构造递归计算/执行计算系统程序计算对象运算符(即函数)定义构造执行递归/迭代基础递归/迭代步骤程序与递归程序构造思维小结第3讲程序与递归【自学&拓展】战德dechen@哈尔滨工业大学计算学部教学委员会主任国家教学名师第3讲程序与递归【自学&拓展】一、原始递归函数

54原始递归函数是接受自然数x或自然数的元组(x1,…xn)作为参数，并产生自然数的一个映射，记为f(x)或f(x1,…xn)。接受n个参数的函数称作n元函数。处处有定义的函数被称作全函数，未必处处有定义的函数称作半函数或部分函数。

递归基础：3个本原函数【常数函数、后继函数和投影函数】递归步骤：2个构造新函数的公式【复合--构造一个新函数、原始递归—构造系列新函数】原始递归函数

【概念】原始递归函数55最基本的原始递归函数，也被称为本原函数有三个：(1)初始函数：0元函数即常数无需计算；或者常数函数：对于每个自然数n和所有的k,有f(x1,x2,…,xK)=n。(2)后继函数：1元后继函数S，它接受一个参数并返回给出参数的后继数。例如S(1)=2,…,S(x)=x+1,其中x为任意自然数。(3)投影函数：对于所有n≥1和每个1≤i≤n的i，n元投影函数Pin，它接受n个参数并返回它们中的第i个参数，即Pin(x1，x2，…，xn)=xi

原始递归函数

递归基础：本原函数56(1)复合：给定原始递归函数f(x1,...,xk)，和k

个原始递归函数g1,...,gk，则f和g1,...,gk的复合是函数h,即

h(x1,...,xm)

=f(g1(x1,...,xm),...,gk(x1,...,xm))简单而言，复合是将一系列函数作为参数代入到另一个函数中，又被称为代入。复合是构造新函数的一种方法。复合是表达组合的一种方法。结构fvs.

构件g1,…,gkg1…,gk的组合关系fvs.

运算组合式g1,…,gkg1…,gk的指令组合关系f

vs.

基本指令g1,…,gk原始递归函数

递归步骤--复合-构造一个新函数57(2)原始递归：给定原始递归函数f和g，则新函数h可由f和g递归的定义，其中

h(0,x1,...,xk)=f(x1,...,xk)

h(S(n),x1,...,xk)=g(h(n,x1,...,xk)，n，x1,...,xk)

简单而言，定义新函数h，就是要定义h(0),h(1),…,h(n),…。h(0)直接给出。h(n+1)则由将h(n)和n代入g中来构造。原始递归是递归地构造新函数的方法，尤其是无限的相似性函数的构造方法。(*(*…(*(*(*11)2)3)…n)S(n))g(x1,x2)=(*x1S(x2))h(0)=1h(S(n))=g(h(n),n)h(0)=1h(1)=g(h(0),0)=(*11)h(2)=g(h(1),1)=(*(*11)2)h(3)=g(h(2),2)=((*(*11)2)3)…h(S(n))=g(h(n),n)原始递归函数递归步骤—原始递归-构造系列新函数58已知： f(x)=x

g(x1,x2,x3)=x1+x2+x3,其中x,x1,x2,x3均为自然数 h(0,x)=f(x)且h(S(n),x)=g(h(n,x),n,x)该函数对任一自然数的计算过程为：h(0,x)=f(x)=xh(1,x)=h(S(0),x)=g(h(0,x),0,x)=g(f(x),0,x)=f(x)+0+x=2xh(2,x)=h(S(1),x)=g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2x,1,x)=3x+1h(3,x)=h(S(2),x)=g(h(2,x),2,x)=g(g(h(1,x),1,x),2,x)=g(g(g(h(0,x),0,x),1,x),2,x) =…=4x+3……

原始递归函数

原始递归函数构造示例59已知： f(x)=2

g(x1,x2,x3)=x1,其中x,x1,x2,x3均为自然数 h(0,x)=f(x)且h(S(n),x)=g(h(n,x),n,x)该函数对任一自然数的计算过程为：h(0,x)=f(x)=2h(1,x)=h(S(0),x)=g(h(0,x),0,x)=g(f(x),0,x)=f(x)=2h(2,x)=h(S(1),x)=g(h(1,x),1,x)=g(g(f(x),0,x),1,x)=g(2,1,x)=2h(3,x)=h(S(2),x)=g(h(2,x),2,x)=g(g(h(1,x),1,x),2,x)=g(g(g(h(0,x),0,x),1,x),2,x) =…=2……原始递归函数

原始递归函数构造示例第4讲冯.诺伊曼计算机

-机器程序是如何被执行的哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣第4讲冯.诺伊曼计算机-机器程序是如何被执行的一、计算机器的功能与构成二、机器指令与机器程序三、一台典型的计算机四、机器程序的执行过程模拟五、存储器计算机器按计算规则(程序)对输入（数据）进行变换，得到输出（数据）。输入计算规则(程序&指令)输入/输出都是0和1的形式表达输出计算规则也是0和1的形式表达数据数据程序计算机器的功能与构成计算机器的基本功能运算器中央处理单元CPU控制器存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算微处理器(芯片)可能包含多个CPU（即多核，m个控制器n个运算器）计算机器的功能与构成计算机器的核心运算器中央处理单元CPU控制器存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算以【存储单元】为单位进行存储一个存储单元可以是8位、16位、32位或64位按【地址(编号)】访问存储单元以【指令】为单位进行读取并执行。一条指令可以保存在1个或多个存储单元中。基本的运算指令就是两个数的加、减、乘、除等运算。计算机器的功能与构成计算机器的核心第4讲冯.诺伊曼计算机-机器程序是如何被执行的一、计算机器的功能与构成二、机器指令与机器程序三、一台典型的计算机四、机器程序的执行过程模拟五、存储器8

32+23+6机器指令与机器程序计算机如何计算一个运算式?算法---机器可以执行的求解问题的规则及步骤。机器指令与机器程序机器级算法计算方法

Step1:取出数3至运算器中Step2:乘以数3在运算器中Step3:乘以数8在运算器中Step4:存数8*3*3至存储器中Step5:取出数2至运算器中Step6:乘以数3在运算器中Step7:加上8*3*3在运算器中Step8:加上数6在运算器中计算方法（优化）Step1:取出数3至运算器中Step2:乘以数8在运算器中Step3:加上数2在运算器中Step4:乘以数3在运算器中Step5:加上数6在运算器中问：怎么看待算法节省的步数?--算法需要优化0000010000000111操作码地址码(如取数，加法等操作)(操作中的数据的来源)机器指令--是CPU可以直接分析并执行的指令，一般由0和1的编码表示。指令

操作码+地址码；000100

0000000100000011

0000001100000011

0000001000000100

0000001010机器语言—机器能够执行的所有指令的集合。机器指令与机器程序机器指令测练题：已知指令系统如右图。如果0000110000001100是一条指令，请问该指令的功能是什么？取出12号存储单元的数与运算器中的数相加结果保留在运算器中

取出12号存储单元的数与运算器中的数乘加结果保留在运算器中

取出12号存储单元的数送到运算器中将运算器中的数保存到12号存储单元中ABCD提交单选题1分测练题：已知指令系统如右图。如果0001000000010000是一条指令，请问该指令的功能是什么？取出16号存储单元的数与运算器中的数相乘结果保留在运算器中

取出16号存储单元的数与运算器中的数相加结果保留在运算器中

取出16号存储单元的数送到运算器的16号单元中将16号运算器中的数保存到16号存储单元中ABCD提交单选题1分假设数字3、8、2、6分别存储在8号、9号、10号和11号存储单元机器级算法机器语言与机器指令机器程序00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000机器指令与机器程序机器程序：将机器级算法用机器指令进行表达计算8

32+2

3+6的程序机器程序存储器存储单元000001000000100000010000000010010000110000001010000100000000100000001100000010110000100000001100000101000000110000011000000000000000000000000011000000000000100000000000000000100000000000000110

地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据机器指令与机器程序将机器程序和数据装载进存储器中?程序与数据以同等地位存于存储器中机器指令与机器程序你能读懂这段程序吗？机器指令与机器程序换一种写法-你能读懂吗？同学要熟悉并适应这种表示方法测练题：请读一读这段程序，其功能是什么？ABCD提交存储单元00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000地址（编号）00000000000000000000000000000001000000000000001000000000000000110000000000000100000000000000010100000000000001100000000000000111000000000000100000000000000010010000000000001010000000000000101100000000000011000000000000000100000000000000010100000000000000110000000000000111计算5

42+3

4+7的程序计算4

52+3

5+7的程序计算3

82+2

8+6的程序计算8

32+2

3+6的程序单选题1分计算8

32+2

3+6的程序计算5

42+3

4+7的程序计算ax2+bx+c的程序?

机器程序存储器存储单元00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据0000000000000100000000000000010100000000000000110000000000000111机器指令与机器程序改改机器程序，体验机器程序机器指令与机器程序读一读程序，能发现什么吗？存储单元00000100000010110001000000001010000011000000100100010000000010110000110000001000000010000000110000010100000011000001100000000000地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000000000000100000000000000100000000000000010100000000000000110000000000000111取出11号存储单元的数（数字3）至运算器中乘以10号存储单元的数(数字5)得5

3在运算器中加上9号存储单元的数(数字4)得5

3+4在运算器中乘以11号存储单元的数(数字3)得(5

3+4)

3在运算器中加上8号存储单元的数(数字2)得5

32+4

3+2至运算器中将上述运算器中结果存于12号存储单元。打印12号存储单元中的数停机24537程序指令系统机器指令与机器程序读一读程序，能发现什么吗？取出8号存储单元的数（即数0000010000001000，十进制为1032）至运算器中加上9号存储单元的数(即数0000110000001001，十进制为3081）得到3081+1032，即4113在运算器中加上10号存储单元的数(即数0000110000001010，十进制为3082）得到4113+3082，即7195在运算器中将结果存入10号存储单元(即7195的二进制数，0001110000011011存储到0000000000001010号（即10号）单元)跳转到10号单元的指令继续执行(10号单元存储的是什么)…存储单元中的内容可能是指令，也可能是数据，还可能既是指令又是数据存储器中的程序是可能被修改的，即初始时是执行预期的程序，而再执行时可能就不是了当用跳转指令改变程序执行次序时，要注意其指向的是否是指令？可能会出现错误指令是一种01形式的编码机器程序是用机器指令编制的程序

CPU所能识别并执行的所有指令就称为指令系统。用该指令系统中的指令编写出的程序，该CPU能够执行数据和指令以同等地位存储于存储器中，即一个存储单元存储的可能是指令，也可能是数据，还可能既是指令又是数据存储在存储单元中的数据或指令在执行过程中可能被改变，也可能前一秒是指令，后一秒就为数据机器程序编写好后，先存于存储器中，然后CPU会一条一条的读取该程序的每一条指令予以执行—存储程序机器指令与机器程序小结中央处理单元CPU存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算第4讲冯.诺伊曼计算机-机器程序是如何被执行的一、计算机器的功能与构成二、机器指令与机器程序三、一台典型的计算机四、机器程序的执行过程模拟五、存储器(数据)寄存器

算术、逻辑及移位运算R0R1运算器(数据)寄存器算术逻辑部件R0=R1

R0(赋值,R0既是一个操作数，又保存运算结果)。其中为算术、逻辑及移位运算符一台典型的计算机运算器为什么要如此设计呢？减少指令的长度两个操作数都在存储器中：只需给出一个存储单元地址000011

0000001010利用寄存器进行腾挪时钟与节拍发生器信号控制

PCIR

算术、逻辑及移位运算R0R1控制器运算器(数据)寄存器程序计数器PC指令寄存器IR信号控制器—发出控制信号时钟与节拍发生器—控制操作次序注：PC：程序计数器---存储下一要执行指令的地址IR：指令寄存器---存储当前指令内容控制器一台典型的计算机将要执行哪一个程序，则将该程序的地址送给PC。否则PC值自动加1，按顺序执行时钟与节拍发生器信号控制

PCIR

算术、逻辑及移位运算

地址内容R0R1存储器(内存)控制器运算器(数据)寄存器存储单元地址存储单元内容存储器一台典型的计算机时钟与节拍发生器信号控制

PCIR

算术、逻辑及移位运算

地址内容R0R1存储器(内存)控制器运算器(数据)寄存器

信号控制线数据线地址线各部件的连接与控制一台典型的计算机存储器被连接到多个位置，怎么控制传送给谁？信号控制部件给谁发信号，谁就接收；否则不接收时钟与节拍发生器信号控制0000000000000000

PCIR

算术、逻辑及移位运算

0000000000000000地址内容R0R1存储器(内存)控制器运算器(数据)寄存器程序&指令数据程序与数据要存在存储器中一台典型的计算机不同的指令，由一组不同的电信号构成。有些电信号需要按次序完成。最小的时间区隔单位--时钟周期。不同的时钟周期状态称为节拍。多个节拍构成一个机器周期。一条指令占用一个或多个机器周期。同一指令的电信号在时钟与节拍的控制下按次序产生与传输。问：机器的“主频”指的是什么?时钟周期、节拍与机器周期指令执行的信号化--即在节拍控制下有序地发出各种电信号指令执行一台典型的计算机计算机各部件内部的简单构成关系运算器寄存器算术逻辑部件控制器程序计数器PC指令寄存器信号控制器时钟与节拍发生器存储器存储单元地址存储单元内容一台典型的计算机程序怎么被执行呢？测练题：请问下列部件哪些属于控制器的部件？ABCD提交数据寄存器程序计数器PC指令寄存器IR算术逻辑部件E时钟与节拍发生器F信号发生器多选题1分测练题：请问下列部件哪些属于运算器的部件？ABCD提交数据寄存器程序计数器PC指令寄存器IR算术逻辑部件E时钟与节拍发生器F信号发生器多选题1分测练题：请问CPU中保存下一条指令存放地址的部件是哪一个？ABCD提交数据寄存器DR程序计数器PC指令寄存器IR信号发生器E内容寄存器F地址寄存器单选题1分测练题：请问CPU中保存正在执行指令的部件是哪一个？ABCD提交数据寄存器DR程序计数器PC指令寄存器IR信号发生器E内容寄存器F地址寄存器单选题1分第4讲冯.诺伊曼计算机-机器程序是如何被执行的一、计算机器的功能与构成二、机器指令与机器程序三、一台典型的计算机四、机器程序的执行过程模拟五、存储器时钟与节拍发生器信号控制0000000000000000

PCIR

算术、逻辑及移位运算

地址内容R0R1(数据)寄存器程序&指令数据运算器控制器存储器机器程序的执行过程模拟初始状态时钟与节拍发生器信号控制寄存器00000000000000000000010000001000

算术、逻辑及移位运算00000100000010000000000000000000地址内容

R0R1PCIR运算器控制器存储器机器程序的执行过程模拟第1条指令：取指令（2个节拍）T1

:将PC值送存储器发控制信号通知存储器工作T2

:按地址找到存储单元并读出发控制信号通知IR接收模拟的要点：1注意存储单元的地址和内容；2注意各寄存器的变化加强理解：完成什么操作（发出什么信号）；2各信号发出的次序与控制0000010000001000时钟与节拍发生器信号控制寄存器00000000000000010000010000001000

0000000000000011

算术、逻辑及移位运算00000000000000110000000000001000地址内容

控制R0R0R1000001PCIR

0000000000000000运算器控制器存储器机器程序的执行过程模拟第1条指令：执行指令（2个节拍）T3

:IR的操作码送信号控制部件识别是取数指令，将IR地址码送存储器发控制信号通知存储器工作PC值自动加1T4

:按地址找到存储单元并读出发控制信号通知R0接收时钟与节拍发生器信号控制寄存器00000000000000010000010000001000

0000000000000011

算术、逻辑及移位运算00000000000000110000000000001000地址内容R0R1PCIR运算器控制器存储器机器程序的执行过程模拟第1条指令执行结束状态时钟与节拍发生器信号控制寄存器00000000000000010001000000001001

0000000000000011

算术、逻辑及移位运算00010000000010010000000000000001地址内容

R0R1PCIR0000010000001000运算器控制器存储器0000000000000011机器程序的执行过程模拟第2条指令：取指令（2个节拍）时钟与节拍发生器信号控制寄存器0000000000000010000100000000100100000000000010000000000000000011

R0算术、逻辑及移位运算R100000000000010000000000000001001地址内容

控制R1

000100PCIR

0000000000000001运算器控制器存储器0000010000001001机器程序的执行过程模拟第2条指令：执行指令（4个节拍）时钟与节拍发生器信号控制寄存器0000000000000010000100000000100100000000000010000000000000011000

R0算术、逻辑及移位运算R100000000000010000000000000001001地址内容

000100PCIR0000000000000011运算器控制器存储器机器程序的执行过程模拟第2条指令：执行指令（4个节拍-续）测练题：请问CPU取指令需要发出哪些信号？ABCD提交将PC的值送给存储器的地址寄存器信号控制部件发信号通知IR接收存储器内容寄存器的值传输到总线存储器按照地址寄存器的地址读取存储单元到其内容寄存器E信号控制部件发信号通知存储器开始工作FIR寄存器接收内容寄存器的值多选题1分测练题：CPU取指令通常需2个节拍。可以在第一个节拍内发出的信号有_______?ABCD提交将PC的值送给存储器的地址寄存器信号控制部件发信号通知IR接收存储器内容寄存器的值传输到总线存储器按照地址寄存器的地址读取存储单元到其内容寄存器E信号控制部件发信号通知存储器开始工作FIR寄存器接收内容寄存器的值多选题1分测练题：CPU取指令通常需2个节拍。可以在第2个节拍内发出的信号有_______?ABCD提交将PC的值送给存储器的地址寄存器信号控制部件发信号通知IR接收存储器内容寄存器的值传输到总线存储器按照地址寄存器的地址读取存储单元到其内容寄存器E信号控制部件发信号通知存储器开始工作FIR寄存器接收内容寄存器的值多选题1分第4讲冯.诺伊曼计算机-机器程序是如何被执行的一、计算机器的功能与构成二、机器指令与机器程序三、一台典型的计算机四、机器程序的执行过程模拟五、存储器程序?程序自动执行?数据计算规则表示?自动存取?自动执行?存储器回顾计算机器的基本思维存储器中央处理单元(CPU)0和1（比特）内存储器/主存储器【存储器】能够按地址读或写每一个存储单元的部件。【存储单元】一个存储单元可以保存一个m位的数据，通常记为Dm-1…D0。