计算机科学导论-计算思维程序实践 课件全套 第1-20讲-从小白鼠验毒到数据传输校验-初识计算思维 -深度学习是怎样提高智能的-神经网络与深度学习

第1讲从小白鼠验毒到数据传输校验

—初识计算思维哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣什么是计算思维？计算机，仅仅是这样的吗？计算机不仅仅是编程，还有计算思维。计算思维是人们普适的思维方式思维有多远，决定你能走多远有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时内就会死亡，问：至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？测试一下你的思维…一个示例【问题】小白鼠验毒问题？012997有毒998999111110011111111001101111100101000000001000000000010000000000【求解】小白鼠验毒问题之求解一个示例00000101001110010111011100011011013位23=8个2位22=4个1位21=2个9位29=512个10位210=1024个这里用到了递推，也是计算思维012997有毒998999111110011111111001101111100101000000001000000000010000000000B9B8B7B6B5B4B3B2B1B0M9M8M7M6M5M4M3M2M1M0B9=1B8=1B7=1B6=1B5=1B4=1B3=1B2=1B1=1B0=11000瓶水分给10只小白鼠喝，分配原则是：如一瓶水的Bi位为1，则给Mi小白鼠喝一口；哪些小白鼠死掉了?死掉为1，不死为0：M9M8M7M6M5M4M3M2M1M0=1111100101有什么启示吗?【求解】小白鼠验毒问题之求解一个示例难度：【0和1的多种语义的组合应用】小白鼠“喝”与“不喝”与小白鼠“死”与“活”，水的“有毒”与“无毒”不同的两种状态都可表达为0和1小白鼠-“死”与“活”；小白鼠对某瓶水-“喝”与“不喝”；水“有毒”与“无毒”用0/1编码串表示不同的含义000010对应第(000010的十进制)瓶水000010第i位对应第i只小白鼠，1喝0不喝；000010第i位对应第i只小白鼠，死1

活0

；000010多种不同的含义统一在一个01串中，可无缝隙实现含义转换多种不同的含义均用01串表达计算思维理解的关键点示例背后的思维0和1

1000瓶分为A1组500瓶,B1组500瓶500瓶分为A2组250瓶,B2组250瓶250瓶分为A3组125瓶,B3组125瓶2瓶分为A10组1瓶，B10组1瓶二分法思维示例背后的思维二分法ABCDE二分法为什么不行呢？二分法-串行使用小白鼠1只能区分2瓶，2只能区分4瓶，…,n只能区分2n瓶二分法与二进制思维二分法-并行使用小白鼠“组合”识别水瓶，n位编码能区分出2n瓶的某一瓶示例背后的思维二进制与并行二分法串行-并行也是计算思维用二进制编码作并行划分也是计算思维过程化思维水瓶十进制编号(所有)

二进制编码

分配给小白鼠喝(第i位对应第i只小白鼠，1喝0不喝)

小白鼠死与活

再形成二进制编码(第i位对应第i只小白鼠，死1活0)

十进制编号(有毒编号的水瓶)。符号变换与逻辑推理由小白鼠的死活用计算的手段推断第几瓶水有毒符号变换：十进制变换为二进制，二进制再变换为十进制。过程化与符号变换思维示例背后的思维符号变换与过程化【计算思维】是运用计算科学的基础概念去求解问题、设计系统和理解人类行为。From周以真，前卡耐基.梅隆大学计算机系系主任教授、前微软公司高级副总裁、前美国国家科学基金会助理局长。她在世界范围内推动了计算思维教育，尤其强调在大学低年级以及中学阶段进行计算思维教育，她认为到21世纪中叶计算思维能力是人人都应具备的一种基本能力。计算思维是一种科学与工程思维，是未来可以转化为创新的思维计算思维是关于计算方法与计算系统的思维（包括设计、构造和应用）、是一种大思维而非小技巧计算思维不仅仅是程序思维、算法思维和问题求解思维（这些可被认为是计算+思维），而是覆盖计算+思维、互联网+思维、大数据思维和人工智能+思维等相对完整的计算思维内容体系怎样创新？且看下例什么是计算思维？【思维】什么是计算思维？·“偶校验规则”--使传输前和传输后相关位1的个数始终为偶数--偶数个1相加和为0；奇数个1相加和为1010110100010101001传输1001101110110111判断数据传输过程是否有错误发生？问题：数据传输的检错与纠错。【应用】通讯数据校验问题及其求解示例思维的价值7654321P4=D7+D6+D5+D4编号的第3位为1P2=D7+D6+D3+D2编号的第2位为1P1=D7+D5+D3+D1编号的第1位为11101001111P4’P2’P1’1101101数据111110101100

011

010

001数据位二进制编号D7D6D5D4D3D2D1P4P2P1数据位校验位1101101111传输P4’=D7+D6+D5+D4+P4P2’=D7+D6+D3+D2+P2P1’=D7+D5+D3+D1+P1小白鼠“喝”与“不喝”小白鼠“死”与“活”11

1110【应用】通讯数据校验问题及其求解示例思维的价值传输7654321P4=D7+D6+D5+D4编号的第3位为1P2=D7+D6+D3+D2编号的第2位为1P1=D7+D5+D3+D1编号的第1位为11001101111P4’P2’P1’1101101101数据111110101100011010

001数据位二进制编号D7D6D5D4D3

D2D1P4P2P1数据位校验位1101101111P4’=D7+D6+D5+D4+P4P2’=D7+D6+D3+D2+P2P1’=D7+D5+D3+D1+P1小白鼠“喝”与“不喝”小白鼠“死”与“活”111换一位出错是否能判断？【应用】通讯数据校验问题及其求解示例思维的价值传输传输P8=编号的第4位为1的位相加=D11+D10+D9=0P4=编号的第3位为1的位相加=D7+D6+D5=0P2=编号的第2位为1的位相加=D11+D10+D7+D6+D3=1P1=编号的第1位为1的位相加=D11+D9+D7+D5+D3=110001100111P8’P4’P2’P1’101011001100111

P8’=D11+D10+D9+P8=1P4’=D7+D6+D5+P4=0P2’=D11+D10+D7+D6+D3+P2=1P1’=D11+D9+D7+D5+D3+P1=0小白鼠“喝”与“不喝”小白鼠“死”与“活”如果校验位出错怎么办？

23

22

21

20

111098

7654

3

2

1D11D10D9P8

D7D6D5P4

D3P2

P11011101010011000011101100101010000110010000111001101111P8’=D11+D10+D9+P8=0P4’=D7+D6+D5+P4=1P2’=D11+D10+D7+D6+D3+P2=0P1’=D11+D9+D7+D5+D3+P1=0【应用】通讯数据校验问题及其求解示例思维的价值小白鼠验毒问题检错与纠错问题如果7瓶水中有2瓶有毒，则需几只小白鼠，才能确定是哪2瓶有毒？如果7位二进制位传输过程中有2位出差错，则需几位校验位才能判断是哪2位有差错？编码效率问题？01324567 x%3=0 x%3=1x%3=2x/3=0 001

001(0)001010

(1)001100

(2)x/3=1 010

001

(3)

010010

(4)

010100

(5)x/3=2

100

001

(6)

100010

(7)

计算vs.检错/纠错

计算机/通讯领域重要的发明【应用】通讯数据校验问题及其求解示例思维的价值图灵奖获得者理查德·汉明【汉明码/海明码】学而有用学而有索趣味故事

思维挖掘

价值再现

对比联想

计算与专业融合学而有趣学而有思什么是计算思维？【小结】从示例中，你学到了什么？第2讲从数学和计算机看方程求解

—最基本的计算思维：枚举-计算-验证哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣求ax2+bx+c=0的根怎样求解一元二次方程？人计算与机器计算人计算与机器计算在思维上什么差异？例如：求ax2+bx+c=0的根人-计算机器-计算(1)从-n到n，产生x的每一个整数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是

利用上述公式计算得到x值怎样求解一元二次方程？人计算与机器计算人-计算一条规则可能很复杂,但计算量却可能很小人需要知道具体的计算规则特定规则，只能求:a1x2+a2x=c机器-计算每条规则可能很简单,但计算量却很大机器也可以采用人所使用的计算规则一般性的规则，可以求任意:a1x1b1+a2x2b2+…+anxnbn=c枚举-计算-验证蛮干思维怎样求解一元二次方程？人计算与机器自动计算的差别人快速获得结果的方法为什么规则要简单？复杂规则怎么办--重复运用简单规则人设计规则-人计算获得结果人设计规则-机器自动计算获得结果机器是如何自动计算的机器自动计算用符号型指令表达规则算法（计算规则）用01编码的指令表达规则用函数/积木块表达规则用语句表达规则机器程序如何执行？CPU(中央处理单元)和存储器(内存/主存)执行程序—芯片级，机器相关各种应用高级语言程序—独立于具体机器高级语言程序如何执行？高端智能机械互联网+高端机械(群)组合-重复表达上，是组合简单规则形成复杂规则执行上，是重复执行简单规则来完成复杂规则无人机例如：求ax2+bx+c=0的根人-计算机器-计算(1)从-n到n，产生x的每一个整数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是

利用上述公式计算得到x值机器-难于计算(1)在实数空间内，以δ为步长，产生x的每一个数值；(2)将其依次代入到方程中计算;(3)如果其值使方程式成立，则即为其解；否则不是。注意：δ可以是0.1，0.01，…，0.000001，…步长越小，求解精度越高，但计算量也越大。机器能在有限时间内完成计算吗？枚举-计算-验证蛮干

优化可求解与难求解机器一定能计算出结果吗？最基本的计算思维：枚举-计算-验证人快速获得结果的方法算法与算法复杂性x一定是整数解吗？0<=x<=20

0<=y<=33

0<=z=100-x-y0<=x<=100

0<=y<=100

0<=z<=100其他示例最基本的计算思维：枚举-计算-验证【示例1】公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，问：用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各能买多少只？设公鸡x

只，母鸡y

只，小鸡z

只，方程式组：

5x+3y+z/3=100

x+y+z=100

0<=x<=100

0<=y<=100

0<=z<=100优化算法：减少无效计算量基本算法：枚举-计算-验证其他示例最基本的计算思维：枚举-计算-验证【示例2】123456789给出一个排列来，使得前n位组成的整数能被n整除(n=1,2,3,…,9)。A*108+B*107+C*106+D*105+E*104+F*103+G*102+H*101+I*100（1）A%1=0；(2)

（A*101+B*100）%2=0；(3)（A*102+B*101+C*100）%3=0（4）…;(5)(A*104+B*103+C*102+D*101+E*100)%5=0;(6)…;(7)…;(8)…;（9）%9=0A到I取其中之一{1，2，3，4，5，6，7，8，9}优化算法：减少无效计算量基本算法：枚举-计算-验证A-I,任意组成一个排列：不重复计算并依次检查条件(1)-(9)哪些排列是没有意义的,是不需要计算和验证。(1)前5位组成的数能被5整除，第5位只能是5。(2)前2、4、6、8位组成的数能被2、4、6、8整除，则第2、4、6、8位只能是偶数，所以第1、3、7、9位只能是奇数。A={1,3,7,9},B={2,4,6,8},C={1,3,7,9},D={2,4,6,8},E=5,F={2,4,6,8},G={1,3,7,9},H={2,4,6,8},I={1,3,7,9}此时，还要考虑A、C、G、I不能重复，B、D、F、H不能重复。其他示例最基本的计算思维：枚举-计算-验证【示例3】给出⼀个整数n，找到所有的0~9的排列，使得前五个数构成的整数能够整除后五个数构成的整数A*10000+B*1000+C*100+D*10+EF*10000+G*1000+H*100+K*10+J（A*10000+B*1000+C*100+D*10+E）%（F*10000+G*1000+H*100+K*10+J）==0注：%为取余数运算A、B、C、D、E

={5，6，7，8，9}F、G、H、K、J={0，1，2，3，4}优化算法：减少无效计算量基本算法：枚举-计算-验证把握计算思维的核心脉络与本质由计算+，到互联网+、大数据和人工智能+人-计算机器-自动计算机器-难于计算自然/社会问题计算自然/社会问题的求解结果数学计算机科学1、社会/自然问题如何计算?2、计算与计算机的本质？1、计算如何与社会/自然进行融合?2、针对具体的自然/社会问题如何计算?互联网+/大数据/人工智能+/软件思维/安全+计算+1、程序是如何被机器自动执行的：机器程序及其执行?2、从思维角度看计算环境的演变：计算资源管理及其程序执行

3、如何编写机器可以执行的程序：高级语言程序及其执行1、怎样构造求解问题的算法2、可求解vs.难求解-难解性问题求解思路3、算法与计算环境之间的关系?1、学科研究对象与研究方法?2、核心课程及其作用？

学科与专业第3讲从加法自动计算看机器硬件实现

—逻辑运算与逻辑门电路哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣计算机是怎样完成计算的？示例计算机器是怎样完成加法运算的，你知道吗？0+0=00+1=11+0=11+1=10逻辑是指事物因果之间所遵循的规律，是现实中普适的思维方式逻辑的基本表现形式是命题与推理，推理即依据由简单命题的判断推导得出复杂命题的判断结论的过程。【命题】一个命题由语句表述，即内容为“真”或为“假”的一个判断语句！【命题的运算】如果命题由X,Y,Z等表示，其值可能为“真”或为“假”，则两个命题X,Y之间是可以进行运算的：【与】运算(AND):当X和Y都为真时,XANDY也为真;其他情况,XANDY均为假。【或】运算(OR):当X和Y都为假时,XORY也为假;其他情况,XORY均为真。【非】运算(NOT):当X为真时,NOTX为假;当X为假时,NOTX为真。【异或】运算(XOR):当X和Y都为真或都为假时,XXORY为假;否则,XXORY为真。“与”运算：两把钥匙都有才能开门“或”运算：只要有任何一把钥匙便能开门计算机的本质是逻辑【逻辑】与基本逻辑运算用0和1来表示逻辑运算【AND】：“与”运算有0为0，全1为1【OR】：“或”运算有1为1，全0为0【NOT】：“非”运算非0则1，非1则0【XOR】：“异或”运算相同为0，不同为1注:1表示真，0表示

假

0AND 0 0 0AND 1 0

1AND 0 0 1AND 1 1

1OR 1 1

1OR 0 1 0OR 1 1

0OR 0 0NOT 0 1NOT 1 0

1XOR 1 0

1XOR 0 1

0XOR 1 1

0XOR 0 0计算机的本质是逻辑0和1的计算：基本逻辑运算二进制的加法运算规则

Ai+BiCi+1SiSi=(AiXORBi)XORCiCi+1=((AiXORBi)ANDCi)OR(AiANDBi)Si=AiXORBiCi+1=Ai

ANDBi不考虑进位考虑进位AiBi+CiCi+1Si用基本逻辑运算实现复杂计算【示例】二进制加法运算可用逻辑计算来实现你能证明一下吗？Si=(AiXORBi)XORCiCi+1=((AiXORBi)ANDCi)OR(AiANDBi)考虑进位AiBi+CiCi+1Si用基本逻辑运算实现复杂计算【枚举-计算-验证】证明复杂逻辑运算的正确性AiBiCi

加法规则的Si

逻辑运算规则的Si

加法规则的Ci+1

逻辑运算规则的Ci+1

00000000011100010110001100111001100101001111000111111111电信号：0V（低电平）

和5V（高电平）01用二极管、三极管实现基本逻辑运算的电路【与门】电路【或门】电路【非门】电路F

=A

ANDBF

=A

ORBF

=NOTA这些电路被封装成集成电路(芯片)，即所谓的逻辑门：【与门】、【或门】和【非门】。用电子技术实现基本逻辑运算基本逻辑运算的电子实现：逻辑门1Y

=1A

AND1B2Y

=2A

AND2B3Y

=3A

AND3B4Y

=4A

AND4B【与门】电路F

=A

ANDB&【与门】电路符号左侧是输入，右侧是输出用电子技术实现基本逻辑运算集成电路示意=1&≥11【与门】电路符号【或门】电路符号【非门】电路符号【异或门】电路符号≥1注意：左侧是输入，右侧是输出输入是电信号的0或者1，输出是对输入做相应的运算，也是电信号的0或者1用电子技术实现基本逻辑运算逻辑门的符号表示注意门电路符号的左输入右输出一位加法器的示例加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现疑问1：这个电路符号是什么？疑问2：为什么前面1个非门后面又有一个非门，有意义吗？疑问3：这个电路正确吗？怎样验证其正确性呢？101101001AiBi+CiCi+1Si枚举-计算-验证：通过枚举所有可能的输入，可验证一位加法器实现的正确性1加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现多位加法器的实现用已验证正确的一位加法器，来实现更为复杂的多位加法器用已验证正确的多位加法器，来实现更为复杂的乘法器/除法器等(略)

【分层构造】低层电路已验证正确，可被封装起来；用已封装的已验证的低层电路可构造更为复杂的高层电路；如此一层层构造。用逻辑实现加法，用硬件实现加法?(5)如何用已实现的基本逻辑运算(门电路)来实现更复杂的运算?0

01

0

1

1

100+110A3A2A1B3B2B1S3S2S1+C4C3C2C1加法运算是这样实现的二进制加法运算用逻辑门电路的组合来实现A1B1C1S1C2A2B2C2S2C3A3B3C3S3C4摩尔定律：芯片可容纳的晶体管数目大约每经过18个月便会增加一倍：2021年达到的规模一块芯片4.6万亿颗晶体管集成电路是这样复杂起来的集成电路是这样的…疑问：为什么需要这么多晶体管？语义符号化

符号计算化

计算0(和)1化0(和)1自动化

分层构造化

构造集成化计算机的本质是逻辑小结：符号化、计算化与自动化第4讲从多项式计算规则变化看自动计算

—规则与迭代哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣两个对象：数据与计算规则三个机制:表示-存储-执行数据

的表示：进位制与编码计算规则的表示：程序数据与计算规则的自动存储计算规则/程序的

自动执行两对象-三机制自动计算要解决什么问题规则越简单，越容易造出机器单一规则简单，但可重复运用能够自动计算的机器-怎样造?nn2一阶差分

n=n2-(n-1)2二阶差分

n=n-n-1

0 01 12 43 94 165 25135792222(n+1)2=n2+

n+n用简单计算规则（如加减法运算）求解复杂计算问题（如乘方运算和多项式运算）例如：求n2示例：怎样计算多项式的值-差分法计算规则nF(n)一阶差分

n=F(n)-F(n-1)二阶差分

n=n-n-1

0 31 62 113 184 275 383579112222F(n+1)=F(n)

+

n+n例如:求F(x)=x2+2x+3初始值不一样，可计算不同的多项式用简单计算规则（如加减法运算）求解复杂计算问题（如乘方运算和多项式运算）计算规则示例：怎样计算多项式的值-差分法/*类C语言表达的计算规则—程序Main(){intk,n,F[],alpha[],beta[];inputk;F[0]=3;F[1]=6;F[2]=11;alpha[1]=3;forn=2tok-1{alpha[n]=F[n]-F[n-1];beta[n]=alpha[n]-alpha[n-1];F[n+1]=F[n]+alpha[n]+beta[n];

}outputF[k]; }F[0]保存F(0)的值F[1]保存F(1)的值F[2]保存F(2)的值F[3]……F[4]F[5]…数组变量，可以按序号保存多个值能够保存数据能够完成计算能够重复进行变量，是程序执行过程中其值可发生变化的量计算规则表达与执行计算规则表达【程序】与计算规则执行【计算机器】Q：保存的数据随K值增大而增多,怎么办?T：输入不同的初始值便可计算不同的一元二次多项式的值/*类C语言表达的计算规则—程序Main(){intk,n,F_nminus1,F_n,F_nplus1,intalpha_nminus1,alpha_n,beta_n;inputk;F_nminus1=1;F_n=4;alpha_nminus1=1;forn=2tok-1{alpha_n=F_n–F_nminus1;beta_n=alpha_n–alpha_nminus1;F_nplus1=F_n+alpha_n+beta_n;F_nminus1=F_n;F_n=F_nplus1; alpha_nminus1=alpha_n;}outputF_nplus1; }F_nminus1类似的，就是一个变量名，可任意命名，可保存一个数值F[0]保存F(0)的值F[1]保存F(1)的值F[2]保存F(2)的值F[3]……F[4]F[5]…占用n个变量保存n个数值F_n只用1个变量保存当前数值计算规则表达与执行怎样用更少的变量来实现自动计算—降低机器构造的复杂性？保存的数据不随K值变化而变化轮流计算新值为下次计算保留相关数据nF_nalpha_nbeta_nF_nminus1alpha_nminus1F_nplus1294131239453216492575216516369722536925

计算规则表达与执行迭代式方法的执行过程由机械计算机到电子计算机自动计算的探索巴贝奇现代计算机：一般程序--任意可变的计算规则Pascal机械计算机:第一台机械计算机-能够自动完成计算Babbage分析机:特定程序--可有限变化的计算规则莱布尼茨机械计算机:自动计算--固定的计算规则电子计算机的元件探索自动计算的探索超大规模集成电路(VLSI)电子管:可自动控制0和1变化的元件集成电路:可自动实现一定变换的元件晶体管：可自动控制0和1变化的元件电子管计算机ENIAC,1946年,17468只电子管人类第一只电子管(真空二极管),1895人类第一只晶体管(点接触晶体管),1947第一台晶体管计算机TRADIC，1953集成电路的发明,1959第三代计算机IBM360,1964第四代计算机—个人计算机,1981VLSI出现,1974计算机器计算程序?程序自动执行?数据计算规则表示?自动存取?自动执行?计算机器计算机器的探索思路二进制元器件系统表示?自动存取?自动执行?存储器输入输出个人计算机内存/主存外存中央处理单元(CPU)微处理器(单核/多核)0和1（比特）计算机器计算机：能够自动执行程序的机器计算机器概念计算机与现实中典型的个人计算机两个对象：数据与计算规则三个机制:表示-存储-执行数据

的表示计算规则的表示：程序数据与计算规则的自动存储计算规则/程序的

自动执行小结如何降低计算机器制造难度规则越简单，越容易造出机器单一规则简单，但可重复进行能够自动计算的机器-怎样造?迭代可大幅度减少待保存的数据量，有利于大规模问题的计算计算规则要尽量简单。可以由简单计算规则来构造复杂规则。第5讲从两种不同的递归函数看规模化计算的规则表达与执行--递归与迭代哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣55递归的概念递归的典型视觉形式自相似性事物的无限重复性构造递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由第n项或前n项定义第n+1项。即:h(n+1)

=g(h(n),n)，g是需要明确给出的，以说明h(n+1)怎样由h(n)和n构造出来。递归的概念什么是递归？57(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)用递归进行定义怎样递归？【示例】怎样定义你的祖先?递归的理解比较难递归思维是计算机最重要的特征想学计算机就要理解递归思维58Fibonacci数列，无穷数列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;……递归定义递推计算/迭代计算/迭代执行体验两种不同的递归函数一种类型的递归函数：定义是递归的,但执行可以是递归的也可以是迭代的计算规则的表达—告诉执行者要递归计算执行者要一步一步地完成计算获得结果59A(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)两种不同的递归函数--递归与递推(迭代)的差别?两种不同的递归函数：递归与迭代递归与迭代的差异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递归是表达相似性对象及动作的无限性重复性构造的方法。递归基础：定义、构造和计算的起点，直接给出。即h(0)。递归步骤：由第n项或前n项定义第n+1项的一个或一组公式。递归是一种关于抽象的表达方法用递归定义无限的相似事物递归是一种算法或程序的构造技术自身调用自身，高阶调用低阶，构造无限的计算步骤递归是一种典型的计算/执行过程由后向前代入，直至代入到递归基础，再由递归基础向后计算直至计算出最终结果，即由前向后计算数学上用递归定义，但算法上有些可由递归算法/程序实现，有些可由迭代算法/程序实现。迭代算法/程序的执行效率要远高于递归算法/程序，因此能用迭代实现的尽量不用递归。能用迭代算法实现的，都能用递归算法实现；而能用递归算法实现的，却未必都能用迭代算法实现。递归算法是用【函数】结构来表达的，而迭代算法是用【循环】结构来表达的。递归算法执行需要【堆栈】（一种后进先出的数据结构）予以支持。用递归定义用递归构造递归计算/执行递归与迭代小结第6讲从学生宿舍管理看存储器

—基于编码的管理思维哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣程序?程序自动执行?数据计算规则表示?自动存取?自动执行?计算机器回顾计算机器的基本思维存储器中央处理单元(CPU)0和1（比特）内存储器/主存储器【存储器】能够按地址读或写每一个存储单元的部件。【存储单元】一个存储单元可以保存一个m位的数据，通常记为Dm-1…D0。【地址】是一个n位的0/1编码，每一个编码指向一个存储单元，通常记为An-1…A0。存储器的基本概念什么是存储器？存储器宿舍楼存储单元房间存储位(存0或存1)床位(住人/不住人)地址编码An-1…A0房间号单元控制线Wi房间钥匙输出缓冲器公共的走廊及大门………概念映射从存储器与宿舍楼的概念对比中，你能发现什么异同吗？存储器的基本概念对比宿舍楼，理解存储器的相关概念同一时刻只能有一个W有效（接通存储单元）存储单元(的内容)(存储单元的)地址地址空间存储字长存储容量地址编码n位：An-1…A0地址空间：

00000000…0000000000000000…00000001

……11111111…11111111存储字长m位：Dm-1…D0

每个存储单元都是m位存储容量=2n

mBit(位)

=2n

m/8Byte（字节)存储容量的单位：210为换算单位2n个存储单元DB、NB、BB、YB、ZB、EB、PB、TB、GB、MB、KB、Byte存储器的基本概念存储器的容量

存储器内部的实现示例当单元控制线W和数据线D间连接有二极管时，则存储的是1，否则，存储的是0。这是只读存储器（ROM，只能读出不能写入）示例。二极管ROM结构示例(2位地址控制4个存储单元,每个存储单元是4位0/1)一个存储单元自动存取：存储器的工作原理存储器是怎样存储0和1的?又是怎样控制存取的?二极管ROM结构示例(2位地址控制4个信息单元,每个信息单元是4位0/1码)111010110010111111000001010101自动存取：存储器的工作原理存储器是怎样存储0和1的?又是怎样控制存取的?

存储器内部的实现示例当单元控制线W和数据线D间连接有二极管时，则存储的是1，否则，存储的是0。这是只读存储器（ROM，只能读出不能写入）示例。当单元控制线W和数据线D间连接有二极管时，由单元控制线决定其是输出1或0，即：当单元控制线为1（高电压）时，则输出1（高电压），而当单元控制线为0（低电压）时，则输出0（低电压）。没有连接的，则不受单元控制线影响，始终输出0（低电压）。

W3,W2,W1,W0随着A1A0的值同时只能有一个为1（高电压）其它为0（低电压），即控制一个存储单元所有位的读写。尽管所有存储单元的第i位都连接到Di，但只有将读取存储单元的第i位对Di产生作用。Dj是数据线Ak是地址编码线Wi是单元控制线存储矩阵：一种【与或逻辑】阵列【地址编码线】与【单元控制线】有黑点则连接，无黑点则不连接。【单元控制线】与【数据线】有黑点则连接，无黑点不连接。高/低电压信号，即0,1，通过连接点相互传递。上半部是【与】阵列，下半部是【或】阵列。存储器实现的逻辑控制存储矩阵的逻辑控制关系Dj是数据线Ak是地址编码线Wi是单元控制线11001000W0=(NOTA0)AND(NOTA1)W1=A0AND(NOTA1)W2=(NOTA0)ANDA1W3=A0ANDA1译码器：将A1A0地址编码翻译到只有一条单元控制线Wi为1,其它为0。【与】阵列，表述了如何由A1A0的值产生W0,W1,W2,W3的值（只能有一条线为1），由横线向纵线传输信号—上半部。同一【单元控制线】上各连接点之间是

“与”关系。即只有各连接点都为1时，该单元控制线的信号为1，否则为0。存储器实现的逻辑控制存储矩阵的逻辑控制关系Dj是数据线Ak是地址编码线Wi是单元控制线11001000输出矩阵：将Wi为1的单元控制线控制的存储单元的值进行输出。【或】阵列，表述了如何由W3W2W1W0的值产生D3,D2,D1,D0的值。单元控制线与数据线之间有黑点连接的，表示存储的是1，其能否输出取决于单元控制线是1还是0。由纵线向横线传输信号—下半部。同一【数据线】上各连接点之间是

“或”关系。即各连接点只要有一个为1时，该数据线的信号为1，否则为0。D3=W0ORW2D2=W1ORW2ORW3D1=W1ORW2D0=W0ORW1ORW30101存储器实现的逻辑控制存储矩阵的逻辑控制关系每个房间8个人，16个房间D7D6…D0A3A2A1A04位房间号8个人-出与入楼控MA3A2A1A000000001…011110001001…11112568RAMI/O0I/O1I/O2I/O3I/O4I/O5I/O6I/O7A0A1A2A3A4A5A6A7R/WCS地址编码线8位（编码256个地址）数据线8位（即D7D6D5D4D3D2D1D0）控制存储单元的读或写当加高电压(1)时读出，当加低电压(0)时写入。芯片是否工作的控制。当加高电压(1)时不工作，当加低电压(0)时工作。168标准宿舍楼存储器容量不够怎么办？存储器芯片vs.标准宿舍楼每个房间8个人，16个房间D7D6…D0A3A2A1A04位房间号8个人-出与入楼控M168标准宿舍楼一个标准宿舍楼：16个房间，每个房间住8人

A3A2A1A0D7…D0住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0E15…E8E7…E0存储器容量不够怎么办？一个宿舍楼不够怎么办？住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0

E15…E8E7…E0解决方案第1步：2个标准宿舍楼对应相同地址B3B2B1B0的房间构成一个大房间，其中编号为E15…E8住上面的楼，而E7…E0住下面的楼，确保他们的地址A3A2A1A0在同一时刻是相同的，即同时进出。E7E6…E0E15E14…E8B3B2B1B0存储器容量不够怎么办？多个宿舍楼拼接在一起使用住宿需求：64个大房间，每个大房间住16人？B5B4B3B2B1B0

E15…E8E7…E0解决方案第2步：2个标准宿舍楼为一组，64个房间则需要4组（每组16个房间）。用楼控信号控制哪一组。楼控信号为0,1,2,3，使用B5B4来产生楼控信号，使用B3B2B1B0来产生楼内的地址。编号0-7的人编号8-15的人32103210存储器容量不够怎么办？多组宿舍楼联合使用存储器容量不够怎么办？用多个标准宿舍楼可组合出容量更大的宿舍楼编号0-7的人编号8-15的人32103210B5B4B3B2B1B0楼号楼内房间号E15E14…E8E7E6…E016个人的编号10110100连到所有下层楼的D7D6…D0连到所有组上层楼的D7D6…D0连到所有组所有楼的A3A2A1A011-1101：3号楼13号房间110111利用8个16x8的标准楼扩展出64x16的宿舍楼的编码控制图存储器容量不够怎么办？用多个存储器芯片可搭建容量更大的存储器32103210B5B4B3B2B1B0片地址片内地址E15E14…E8E7E6…E0一个存储单元的16位数据10110100110111连到所有芯片的A3A2A1A0连到所有下层芯片的D7D6…D0连到所有上层芯片的D7D6…D0利用8个16x8存储器芯片扩展出64x16位存储器的电路控制图111101：3号片13号单元【看山不是山、看水不是水】既是学习芯片扩展的思维，也是学习科学管理的思维从宿舍楼管理到存储器芯片第7讲从多项式自动计算看机器程序

--编码-指令与机器程序哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣计算机器按计算规则(程序)对输入（数据）进行变换，得到输出（数据）。输入计算规则(程序&指令)输入/输出都是0和1的形式表达输出计算规则也是0和1的形式表达数据数据程序计算机器的功能与构成计算机器的基本功能运算器中央处理单元CPU控制器存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算微处理器(芯片)可能包含多个CPU（即多核，m个控制器n个运算器）计算机器的功能与构成计算机器的核心运算器中央处理单元CPU控制器存储器(主存或内存)程序数据程序与数据的保存程序执行与数据计算以【存储单元】为单位进行存储一个存储单元可以是8位、16位、32位或64位按【地址(编号)】访问存储单元以【指令】为单位进行读取并执行。一条指令可以保存在1个或多个存储单元中。基本的运算指令就是两个数的加、减、乘、除等运算。计算机器的功能与构成计算机器的核心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机器语言—机器能够执行的所有指令的集合。机器指令与机器程序机器指令假设数字3、8、2、6分别存储在8号、9号、10号和11号存储单元机器级算法机器语言与机器指令机器程序00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000机器指令与机器程序机器程序：将机器级算法用机器指令进行表达计算8

32+2

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

地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据机器指令与机器程序将机器程序和数据装载进存储器中?程序与数据以同等地位存于存储器中机器指令与机器程序你能读懂这段程序吗？机器指令与机器程序换一种写法-你能读懂吗？计算8

32+2

3+6的程序计算5

42+3

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

机器程序存储器存储单元00000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000地址（编号）000000000000000000000000000000010000000000000010000000000000001100000000000001000000000000000101000000000000011000000000000001110000000000001000000000000000100100000000000010100000000000001011000000000000110000000100000010000001000000001001000011000000101000010000000010000000110000001011000010000000110000010100000011000001100000000000程序数据00