计算机科学导论-计算思维程序实践 课件 第4讲-从多项式计算规则变化看自动计算-规则与迭代

第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（比特）计算机器计算机：能够自动执行程序的机器计算机器概念计算机与现实中典型的个人计算机两个对象：数据与计算规则三个机制:表示-存储-执行数据

的表示计算规则的表示：程序数据与计算规则的