ch1算法设计及分析基础.ppt

算法设计与分析TheDesignandAnalysisofAlgorithms凌捷广东工业大学计算机学院Date1LingJie/GDUT本课程的安排平时成绩30%(设计、作业、考勤、提问等)期末考试70%第15周周四随堂考试(考查)学****建议:1、注重算法的编程实现2、大部分内容是了解(36学时)Date2LingJie/GDUT第1章绪论主要内容:×Date3LingJie/、算法概念没有一个统一的严谨的定义。一般而言,对于计算机算法的概念是这样描述的:算法是在有限步骤内求解某一问题所使用的一组定义明确的指令。本书采用的定义:Analgorithmisasequenceofunambiguousinstructionsforsolvingaproblem=算法是求解某一问题所使用的一系列清晰的指令。Date4LingJie/GDUT2、算法的概念图注意:计算机发明以前也有算法问题算法“计算机”输出输入Date5LingJie/GDUT3、算法的三个要素1).数据:).运算:运算序列中的各种运算:赋值,算术和逻辑运算3).控制和转移:、算法的一般特征1).有穷性finiteness算法必须在执行有穷步后终止,且每一步均在有限时间内完成2).确定性definiteness算法的每个步骤必须有明确的意义,对每种可能的情况,).能行性effectiveness算法中的每个步骤是能够实现的,算法执行结果要达到预期目的4).有0个或多个输入项,:计算最大公约数的欧几里德算法ALGORITHMEuclid(m,n)//计算两个整数m、n的最大公约数gcd(m,n)//输入:非负整数m,n,其中m,n不同时为零//输出:m,n的最大公约数whilen≠0do r ←mmodn m ←n n ←rreturnmDate8LingJie/GDUT求gcd(m,n)的原理:(结构化的描述)第一步:如果n=0,返回m的值作为结果,结束;否则进入第二步。第二步:用n除m,余数赋值给r,进入第三步。第三步:将n的值赋给m,将r的值赋给n,返回第一步。例:gcd(60,24)=?1-1、m=60,n=241-2、60mod24=12,r=12,1-3、m=24,n=122-1、24mod12=0,r=02-2、m=12,n=02-3、条件“n=0”满足,返回gcd(m,n)=m=12Date9LingJie/GDUT求gcd(m,n)的其他算法算法二:连续整数检测法第一步:将min{m,n}赋值给t。第二步:m除以t,如果余数为0,进入第三步,否则进入第四步。第三步:n除以t,如果余数为0,返回t的值;否则进入第四步。第四步:把t的值减1,返回第三步。例:gcd(60,24)t=min{60,24}=24,m=60,n=2460mod24=12≠0,t=23,24mod23=1≠0t=22,24mod22=2≠0t=21,24mod21=3≠0…..t=12,24mod12=0,返回gcd(m,n)=t=12Date10LingJie/GDUT