第6讲软件开发与软件工程ppt课件.ppt

《第6讲软件开发与软件工程ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6讲软件开发与软件工程1算法(3.3)2程序设计(3.3)3软件工程(补充)开发计算机软件的过程(1)确定并理解问题(2)寻找解决问题的方法与步骤，并将其表示成算法(algorithm)(3)程序设计：使用某种程序设计语言描述该算法及其处理的对象,并编译成目标程序(4)调试(debug)和运行(run)程序，获得问题的解答(5)进行评估,改进算法和程序1.算法什么是算法？——算法是解决问题的方法与步骤例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：按给定条件进行操作明确而有序地进行共享智能(任何人均可进行)开始C是伪币B是

2、伪币A是伪币A＝B？A＝C？是否否是ABC解决问题必须找到算法！例1：买鸡问题公元5世纪末(南北朝)，我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”假设:公鸡数目为x，母鸡数目为y，则小鸡数目为(100-x-y)则：5x+3y+(100-x-y)/3=100，即7x+4y=100这是2元一次不定方程,共有有3组解：(4,18，78)、(8，11，81)、(12，4，84)用“枚举法”解决买鸡问题开始NY5x+3y+z/3＝100？x+y＝100？x+y＝100？结束x=0,y=0x+

3、1x=0,y+1z=100-x-yNY输出x,y,zNY假设:公鸡数目为x，母鸡数目为y，则小鸡数目z=100-x-y从x=0,y=0开始，反复检查各种可能的组合是否所求答案：x=0,y=0、x=1,y=0······x=100,y=0x=0,y=1、x=1,y=1···x=99,y=1···x=0,y=99、x=1,y=99x=0,y=100直到找出全部答案为止！枚举法也叫做“穷举法”或Brute-force例2：货郎担问题(TSP-TravelingSalesmanProblem)售货员从城市A出发，到B、C、D等若干城市销售货物。已知各城市之间的距离，要求选择一条旅行路线，使总路程最

4、短。条件：每个城市只能经过一次，最后仍回到出发城市A。用枚举法解决TSP问题TSP问题与组合爆炸4个城市，共有3！=6种路径5个城市，共有4！=24种路径10个城市，共有9！=36万种路径50个城市，有49！=1062路径……f(n)=(n－1)!2019年解决了15112个城市之间的TSP问题，使用110台计算机，共费时2.5月（组合爆炸）理论上，枚举法可以解决可计算领域的许多问题实际上，枚举法仅适用于解决一些较小规模的问题33x23x2x1例3：寻找最大数（分治法）再分组：[49，38][65，97][76，13][27]49977627每一组找大数：归并成1组[97，76]原始数据为

5、：49,38,65,97,76,13、27分成2组：[49，38，65，97][76，13，27][49，97][76，27]归并成2组：9776每一组找大数：97找出最大数：分治法的基本思想例：找最大/最小数；合并排序；矩阵乘法；二分法搜索等把问题分解为若干个规模较小的同一问题原始问题规模较小的子问题问题规模缩小之后很容易得到解答子问题的解从子问题的解可以很容易地推导出原始问题的解原始问题的解例4：迷宫问题(回溯法、试探法)出口入口迷宫问题将问题的候选解按某种顺序逐一检验，在检验过程中取消上一步或几步、再寻找下一个可能候选解的过程叫做“回溯”DemoBacktracking例5：Hano

6、i塔问题（递归法）设A,B,C是3个塔座，塔座A上有一叠由小到大叠在一起的n个圆盘，现要求将塔座A上的这一叠圆盘移到塔座C上，并仍按同样顺序叠置。移动规则是：(1)每次只能移动1个圆盘(2)不允许大盘压在小盘上ABCCAB2个圆盘的情况abc0abc1abc2abc3一共需要搬动3次！3个圆盘的情况abc0abc搬3次3abc4abc再搬3次7一共需要搬动7次！4个圆盘的情况abc8ABC0abc7搬7次15CAB再搬7次一共需要搬动15次！Hanoi塔问题分析假定每秒移动一次，一年有31536000秒，则需要花费大约5849亿年的时间假定计算机以1000万次/s的速度进行传送操作，则需要

7、大约58490年的时间若n=100，在运算速度是1012/s（1万亿次/秒），该算法需要运行4x1010年，几乎是宇宙年龄设圆盘数目为n，移动次数为h(n),则h(n)=2h(n-1)+1=2(2h(n-2)+1)+1=22h(n-2)+2+1=23h(n-3)+22+2+1……=2nh(0)+2n-1+…+22+2+1=2n-1+…+22+2+1=2n-1当n=64时，需要移动盘子的次数为：264-1=18446744