计算机导论-第7章算法

第7第页 *7.4页7.5*7.6算法的定

什么叫算第页 第页1用M除以NR为M除以N3 3MN问题第页 问题第页 页 3算法的可执行性保证了所有操作步骤都是在计算机上页算法的基本元要解决算法的表示问题，第一步需要确定算法的基元素算法的基本元素的两个含6 算法的五类基本元6 变变第 第 于求解同类型的各种具体问题的号N赋ASSIGNnameASSIGNname 页 页ASSIGNage ASSIGNage9页 个数学表达式9页IF（condition）THENELSE 执行过程如图7-1（a）所示IF（condition）THEN否否是是否

图7-1分支语句的执行过（a）分支类型1；（b）分支类型IF（x>0）THENASSIGNyELSEASSIGNy第页例如，下边例子描述了当x大于10时y等于y+1，IF（x>10）THENASSIGNyy+1IF（x==0）THENASSIGNy IF（x<0）ASSIGNy ASSIGNyx- x+1；当x大于100WHILE（condition）DO 循环语句的含 条件条件成立否是循环过程页图7-2程ASSIGNsumASSIGNxWHILE（x<=100）{ASSIGNsum}ASSIGNx}第 语句ASSIGNsumsum+x完成累加运算语句ASSIGNxx+1既完成变量数值增1，又完成对条件x<=100作某种改变，并使这种改变每次都更近条件x<=100不成立。改变每次都更近条件x100不成立（若语句为ASSIGNxx-1，就不会更近条件x<=100不成立）。则上述算法就不会结束。第页 PROCEDURE{过程体 一个问题表示成带一个参数的过程PROCEDURE{ASSIGNsumASSIGNxWHILE（x<=n）{ASSIGNsum ASSIGNx }xx否是sum=sum+xx=x+1sum=x=页图7-3图PROCEDURE{ASSIGNsum0ASSIGNxn1WHILE（{ x<=n2）{页ASSIGNsumASSIGNx}}符号Sum2PROCEDURE{ASSIGNsumASSIGNx{WHILE（x<=100）{第 ASSIGNsumASSIGNx}} 过程还有其它名字，如函数、子程序、子例程等，算法的表一个相同含义的算法第页 2码形第 伪码形PROCEDURE{IF(m<n){ASSIGNtempASSIGNmASSIGNn} ASSIGNr WHILE(r!=0){ASSIGNmnASSIGNnrASSIGNrm%n}} 伪码形式的算法主要用在人类之间传递思想和 第页页intCommDivisor(intm,int{inttemp,if(m<{temp=m=n=} r=m%页 while(r!=页{m=n=r=m%}return} 具体大小 在上边的例子中，语句“inttempr”表示给变节的单元空间。第页 参数m和参数n也是变量，参数m和参数n前边的空间大小为4个字节。页函数名CommDivisor分配的空间大小为4例如，C语言程序中的语句“tempm;”就表示伪码形式算法的语句“ASSIGNtempm”。 便于计算机对程序语句的“识别”*7.4循环和递本节主要内第1.第页 2.递归算页包含循环结构的算1循环结构算法的设第 第 最后一个数据元素比较 （2）继续执行页 4如果temp的数值等于变量x数值，则查找成功；否则页 例7-2设计计算阶乘n!下边给出计算阶乘n 例如，语句“pro=1”等同于语句“ASSIGNproPROCEDURE{WHILE(m<=n)DO{ }2循环结构算法的执行流由于m=1n=4m<n，所以执行和 由于m=2,n=4,m<n，所以执行 和由于m=3,n=4,m<n，所以执行和由于m=4,n=4m==n（符号==表示等于）由于m=5n=4m>n， 循环过程 mm否是pro=m=pro=m=页图7-4阶乘问题算法的流程 递

递归算递归算第递归算法举第页 页1递归算法的设 如果数据元素x小于该数据元素，则调用自身页 页有序大大页

小(

有序

比较有序表(c图7-5递归算法查找成功过程示 页 页比比大有序 xx页 比页小

大

(b (c)图7-6递归算法查找失败过程示

(d) 页 页IF（有序表空）THENTHEN查找成功，结束；页 页例7-4n! 下边给出计算阶乘nPROCEDURE{IF(n==1)THENELSEy=n*Factorial2(n-}第页2递归算法的执行流由于n=4，条件n==1 页 页第第 页第 y=3*

Factrial{...y=4*Factrial2(3)6…6}{Factrial2(2{{2y=2*2

{y=3*…}Factrial2(11y=1 图7-7算法的效

7.5算法的效 时间资 指的是运行算法所花费的时间，是算法设计时要考虑的空间资算法的时间效举例分析算法的时间 全部100万册就有100万条记录页当一本书被借阅时，需要把相应的记录修改为已经借算法一：无序表的顺序查找算 页 第页 页第页一半，所以对100万条记录来说，的情况下比较14次（13<lb <14）即可。属的查找工作需要耗时10-5秒，则在情况下查 页结第页算法时间效率表 折半查找算法 个数n的lbn。用函数O(f(n))来表示数据个数n的数量级为函数f(n顺序查找算法的时间效率就可以表示为O(n折半查找算法的时间效率就可以表示为O(lbn时间效率函数还有O(n2)，O(n3)，O(nlbn)等优劣排列次序是：O(lbn)，O(n)，O(nlbn)，算法分第 第 不同的算法空间的差别不是很大，所以除特殊应可计算的问

*7.6计算的限不可计算的问难解的问 些问题为难解的问题本节主要内容 难解的问 不可解的问页难解的问算法的理论可终止性例7-5 页 页第第页 页n 前n-1第n

(a

n

(b图7-8n- n-(c)

n图7-8n

(d（c）第n个到C柱（d）前n-1个到C 求解n个圆盘的汉诺塔问题的递归算法为 1递归调用n-1个圆盘的汉诺塔问题算法，把上面当n=4时，需要移动15次圆盘，……移动圆盘的次数和圆盘个数n第第 当n=2时，移动圆盘的次数为2