算法问题求解基础.ppt

第1章算法问题求解基础算法设计与分析DesignandAnalysisofAlgorithmInC++陈慧南编著第1章算法问题求解基础平时要求:按时上下课、课堂不吵闹、手机调成非铃声状态考试成绩:平时表现(考勤、随堂提问、作业等):20%期末考试:80%第1章算法问题求解基础课程简介课程名称:算法设计与分析Designandanalysisofalgorithms先修课程:面向对象程序设计语言0艹,数据结构,,它是计算机科学的基础,更是计算机程序的基石。算法是计算机求解问题的特殊方法。学****算法,一方面需要学****求解计算领域中典型问题的各种有效算法,还要学****设计新算法和分析算法性能的方法。算法(aIgorithm):一个算法是对特定问题求解步骤的种描述,它是指令的有限序列。中国的珠算口诀可视为典型的算法,它将复杂的计算描述为一系的算珠拨动动作。第1章算法问题求解基础算法具有下列5个特征◇输入(input):算法有零个或多个输入量◇输出(output):算法至少产生一个输出量◎确定性(definiteness):算法的每一条指令都有确切的定义,没有二义性;°能行性(effectiveness):算法的每一条指令必须足够基本,它们可以通过已经实现的基本运算执行有限次来实现;有穷性(finiteness):算法必须总能在执行有限步之后终止。第1章算法问题求解基础最早的算法是欧几里德的“求最大公因子算法辗转相除法欧几里德算法(辗转相除法)计算两个整数m和n(0≤m<n)的最大公约数,记为gcd(m,n)。其计算过程是重复应用下列等式,直到nmodm0gcd(m,n)=gcd(nmodm,m),对于m>0(1-1)式中,nmodm表示n除以m之后的余数。因为gcd(0,n)=n,n的最后取值也就是m和n最大公约数。例如,gcd(24,60)=gcd(12,24)=gcd(0,12)=12第1章算法问题求解基础【程序1-1】欧几里德递归算法voidSwap(int&a,int&bintc=aa=b:b=cintRGcd(intm,intn)if(m==0returnnreturnRGcd(n%‰m,mintGcd(intm,intn)if(m>n)Swap(m,n)returnRGcd(m,n)第1章算法问题求解基础【程序1-2】欧几里德迭代算法intGcd(intm,intn)f(m==o)returnnif(n==returnmwap(mwhile(m>0)intc=n‰m:n=m:m=creturnn第1章算法问题求解基础迭代和递归的区别迭代和递归各基于一种控制结构,都涉及到循环,都可无限进行。√迭代是循环求值,递归是调用本身√迭代使用循环结构,递归使用选择结构;√迭代是当循环条件不满足时终止,递归是当满足基本条件时终止√迭代是用计数器控制循环,不停地修改计数器的值,直到不满足条件为止√递归是逐渐逼近基本条件而终止,不断的对问题进行简化直到可以直接计算基本问题为止