算法设计与分析课件01算法设计基础

算法设计与分析Design and Analysis of Algorithms 1算法设计与分析2主要内容主要内容算算法法设设计计与与分分析析算法分析体系及计量算法分析体系及计量算法算法基础基础基本算法策略基本算法策略通用通用算法算法算法设计实践算法设计实践循环与递归循环与递归数据结构数据结构基本技巧基本技巧数学模型数学模型迭迭 代代蛮蛮 力力分分 治治贪贪 婪婪动态规划动态规划回溯与分支限界回溯与分支限界商旅问题商旅问题内存移动内存移动大数运算大数运算最大子段和最大子段和背包问题背包问题广度优先广度优先深度优先深度优先随机算法随机算法最大公约数最大公约数泰勒公式泰勒公式算法设计与分析3主要内容主要内容终级目标：问题求解1.分析问题：已知条件、数据结构、问题分划2.计算模型：技术、工具、手段3.求解策略：技术路线4.编程求解：程序设计5.效率评估：算法评估手段-算法分析工具算法设计与分析4第1章 算法基础主要内容主要内容l算法描述的方法l算法设计的过程l算法的基本概念算法的基本概念l算法设计工具l基本的数据结构算法设计与分析5难！太难！（1）What?解决问题方法（2）why？更好地解决问题（3）how？（1）理解与分析问题（2）相似问题相似解法，设计算法（3）算法优化，评估-优化算法策略数学工具算法设计与分析62022/9/30学习目标：用计算机更好地求解问题学习目标：用计算机更好地求解问题=算法的基本概念算法的基本概念=l算法（算法（Algorithm）对解解题方案准确而完整的描述，是一系列解决方案准确而完整的描述，是一系列解决问题的清的清晰指令，代表着用系晰指令，代表着用系统的方法描述解决的方法描述解决问题的策略机制。的策略机制。“算法是计算机科学的核心”“没有算法，就没有计算机程序”“软件开发，算法先行”“算法是计算机软件的灵魂”l算法定位：算法定位：工业自动化控制电子工业医疗卫生航空航天经济商务l算法应用领域：算法应用领域：算法设计与分析【例1-1】求任意两个非负整数最大公约数(greatest common divisor,gcd)。问题分析问题分析 1)解决办法：质因数分解法、欧几里德算法(辗转相除法)、更相减损法 2)共同特点：使用公约数公约数公约数公约数不断进行约简，约简的次数(迭代)越少，算法的效率越高。计算模型计算模型设a,b 0 1)穷举法7=算法的基本概念算法的基本概念=算法设计与分析8=算法的基本概念算法的基本概念=设a、b的最大公约数为d,表示为d|a,d|b设 a/b=mr a=b*m+r因为 d|a,d|ba%d=0 (b*m+r)/d=0 b*m%d=0,r%d=0所以 d|r 证明算法设计与分析【例1-1】求任意两个非负整数最大公约数算法设计与描述算法设计与描述9穷举法法欧几里德算法欧几里德算法输入入：a,bZ输出出：a,b的最大公的最大公约数数r或或bstep1:取取r=mina,b；step2:测试amodr=0andbmodr=0，成成立立，执行行step4，否否则执行行step3；step3:执行行r=r-1,返返回回step2继续执行；行；step4:输出出r，算法停止。，算法停止。step 1:执行r=a mod b，若r=0，则执行step3，否则执行step2；step 2:执行a=b、b=r,返回step1继续执行；step 3:输出b，算法停止。=算法的基本概念算法的基本概念=思考题：本描述有哪些特点？算法设计与分析【例1-1】求任意任意两个非负整数最大公约数算法分析算法分析效率效率设a=21,b=141)穷举法：穷举法：r=14,21 mod 14=7 and 14 mod 14=0,r=14-1=13；21 mod 13=8 and 14 mod 13=1,r=13-1=12；21 mod 8=5 and 14 mod 8=6,r=8-1=7 21 mod 7=0 and 14 mod 7=0,输出r。2)欧几里德算法欧几里德算法：r=21 mod 14=7,a=14,b=r=7；r=14 mod 7=0输出b。10=算法的基本概念算法的基本概念=Error！21、14仅为a、b的实例例之一之一算法设计与分析11=算法的基本概念算法的基本概念=算法设计与分析【例1-1】求任意任意两个非负整数最大公约数算法分析算法分析效率效率12=算法的基本概念算法的基本概念=2)欧几里德算法分析欧几里德算法分析设ab=1，构造数列un：u0=a,u1=b,uk=uk-2 mod uk-1，其中k=2。若算法需要n次模运算,则有，un=gcd(a,b),un+1=0（un+1=un-1 mod un）比较数列un和菲波那契数列Fn,可得，F0=1=un,F1=1=uk+1+uk+2由数学归纳法容易得到uk=Fn-k,于是得到a=u0=Fn,b=u1=Fn-1算法设计与分析【例1-1】求任意任意两个非负整数最大公约数13=算法的基本概念算法的基本概念=算法设计与分析算法实现算法实现14=算法的基本概念算法的基本概念=思考题：设计算法求多个数的最大公约数？算法设计与分析15=算法的基本概念算法的基本概念=必须确定算法所处理的输入值域对于输出有明确的要求，输出=f(输入)并在有限步骤内结束算法设计必须是严谨、可行且正确的算法每一个步骤都有确切的含义同一算法可以用几种不同的形式来描述同一问题，可能存在几种不同的算法针对同一问题的不同算法，其运算效率也不一样算法设计与分析16第1章 算法基础主要内容主要内容l算法描述的方法算法描述的方法l算法设计的过程l算法的基本概念l算法设计工具l基本的数据结构算法设计与分析自然语言描述程序流程图NS流程图伪代码程序设计语言17=算法描述的方法算法描述的方法=思考题：你常用哪几种方法？它们有什么优缺点？算法设计与分析18第1章 算法基础主要内容主要内容l算法描述的方法l算法设计的过程算法设计的过程l算法的基本概念l算法设计工具l基本的数据结构算法设计与分析19【例1-2】交通指挥灯问题交通指挥灯问题。一个具有五条通路的交叉路口，当允许某些通路上的车辆在交叉路口通行时，必须对其他通路上的车辆加以限制，不许同时在交叉路口通行，以免发生碰撞。(1)交通指挥灯示意图交通指挥灯示意图问题分析问题分析ABCDE=算法设计的过程算法设计的过程=问题：如何依题意建立一个问题：如何依题意建立一个可以求解不同颜色灯的数量可以求解不同颜色灯的数量来指挥交通的来指挥交通的模型模型？算法设计与分析20【例1-2】交通指挥灯问题交通指挥灯问题。一个具有五条通路的交叉路口，当允许某些通路上的车辆在交叉路口通行时，必须对其他通路上的车辆加以限制，不许同时在交叉路口通行，以免发生碰撞。(1)交通指挥灯示意图交通指挥灯示意图问题分析问题分析ABCDE(2)交通指挥灯交通指挥灯抽象抽象图图EDABACADBABDDADBDCEAEBECBC=算法设计的过程算法设计的过程=算法设计与分析21【例1-2】交通指挥灯问题交通指挥灯问题。一个具有五条通路的交叉路口，当允许某些通路上的车辆在交叉路口通行时，必须对其他通路上的车辆加以限制，不许同时在交叉路口通行，以免发生碰撞。(1)交通指挥灯示意图交通指挥灯示意图问题分析问题分析ABCDE(2)交通指挥灯交通指挥灯抽象抽象图图EDABACADBABDDADBDCEAEBECBC=算法设计的过程算法设计的过程=算法设计与分析22【例1-2】交通指挥灯问题交通指挥灯问题。一个具有五条通路的交叉路口，当允许某些通路上的车辆在交叉路口通行时，必须对其他通路上的车辆加以限制，不许同时在交叉路口通行，以免发生碰撞。3.解决方法：解决方法：1.穷举法；2.特殊解法；3.贪心算法贪心算法(1)交通指挥灯示意图交通指挥灯示意图问题分析问题分析ABCDE(2)交通指挥灯交通指挥灯抽象抽象图图EDABACADBABDDADBDCEAEBECBC=算法设计的过程算法设计的过程=算法设计与分析23（1）结点编码）结点编码 AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED=0,1,2,3,4,5,6,7,8,9,10,11,12（2）数据结构数据结构-图：邻接矩阵表示法图：邻接矩阵表示法G=(V,E)V:struct Nodechar name10;/表示道路名称，如AB int color;/表示灯的颜色编号v13;E:e1313;/1为相邻，0表示不相邻=算法设计的过程算法设计的过程=模型建立模型建立算法设计与分析24=算法设计的过程算法设计的过程=矩阵的值如下所示：矩阵的值如下所示：模型建立模型建立算法设计与分析25=算法设计的过程算法设计的过程=算法设计与描述算法设计与描述intmain(intargc,constchar*argv)inti,j,cnt_color=1;for(i=0;i13;i+)intflag=1;if(vi.color=0)vi.color=cnt_color;printf(第第%d种颜色：种颜色：%s,cnt_color,vi.name);for(j=1;j13;j+)/不相不相邻邻且没有着色且没有着色结结点点jif(eij=0&vj.color=0)for(inth=0;h13;h+)/考察与考察与j相相邻邻的的顶顶点的点的颜颜色色if(ejh=1&vh.color=cnt_color)/若有，若有，则则j不能着色不能着色flag=0;ct+;/没有相没有相邻邻且涂同一且涂同一颜颜色的色的结结点，可以点，可以给给j/着色着色if(flag=1)vj.color=cnt_color;printf(%s,vj.name);/用一种用一种颜颜色能涂都涂完，色能涂都涂完，贪贪心心cnt_color+;printf(n);printf(总总共共%d种种颜颜色色n,cnt_color-1);return0;算法设计与分析26运行结果运行结果=算法设计的过程算法设计的过程=颜色色通路通路额外通路外通路蓝AB,AC,AD,BA,DC,ED-红BC,BD,EABA,DC,ED绿DA,DBAD,BA,DC,ED黄EB,ECBA,DC,EA,ED算法分析算法分析贪心算法策略：(1)要考察第一个节点，最外层循环，n=13；(2)找到一个未着色的节点，着色，考察相邻结点，内1层循环，n=13；(3)考察(2)中找到的节点的不相邻节点是否涂了相同颜色，内2层循环，n=13；综上，每次考察一个外层结点，内层都要全部遍历其它结点，因而执行效率可以描述为：n*n*n算法设计与分析271.算法设计过程含几个步骤？2.你认为哪几个步骤是必？为什么？3.你在程序设计中用哪几个？4.在交通指挥灯问题的算法分析中分析的主要对象是什么？5.交通指挥灯问题的是否是唯一的？为什么？思考题=算法设计的过程算法设计的过程=算法设计与分析28问题分析问题分析算法策略算法策略/建立建立计算模计算模型型算法设计算法设计与与描述描述算法分析算法分析评价评价-算法选择算法选择算法实现算法实现测试测试结果整理与文档编制结果整理与文档编制=算法设计的过程算法设计的过程=1 1.不要信息丢失不要信息丢失不要信息丢失不要信息丢失2.2.挖掘隐含信息挖掘隐含信息挖掘隐含信息挖掘隐含信息3.3.抽象出数据结构抽象出数据结构抽象出数据结构抽象出数据结构算法设计与分析296.下图是中国行政区域地图。图中，任意两个相邻的行政区域颜色均不同，请仿照“交通指挥灯问题”的算法设计与分析的步骤，完成地图的着色 思考题=算法设计的过程算法设计的过程=算法设计与分析30第1章 算法基础主要内容主要内容l算法描述的方法l算法设计的过程l算法的基本概念l算法设计工具算法设计工具l基本的数据结构算法设计与分析311.循环设计循环设计=算法设计工具算法设计工具=(1)设计思维设计思维自底向上的设计（Down-Top Design）先找出某个问题的子问题或若干特殊问题，以定性、定量的方式去描述和解决这些