算法分析与设计PPT学习教案

1、会计学1 算法分析与设计算法分析与设计 南京邮电大学计算机学院 7/20/2021 教材： 陈慧南.算法设计与分析-C+语言描述 先修课： 面向对象程序设计语言C+，数据结构 性质： 计算机科学与技术中处于核心地位的一 门专业基础课。 第1页/共48页 南京邮电大学计算机学院 7/20/2021 目的：通过学习掌握算法设计的主要方法，并对算法的时、空复杂性有正确分析的能力，能够针对具体的应用问题选择合适的数据结构和设计结构清晰、正确有效的算法，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。 基本任务: 介绍算法的基本概念、算法设计的基本策略和方法，同时介绍算法复杂性的概念、性能分析的

2、具体方法和技巧。 教学重点: 算法设计的基本思想和策略，以及算法性能分析的方法等。 第2页/共48页 南京邮电大学计算机学院 7/20/2021 第3页/共48页 南京邮电大学计算机学院 7/20/2021 基本要求： 本章概述算法问题、求解方法等重要 概念和方法。掌握算法的基本概念，了解 使用计算机求解问题的过程和方法。 第4页/共48页 南京邮电大学计算机学院 7/20/2021 第5页/共48页 南京邮电大学计算机学院 7/20/2021 第6页/共48页 南京邮电大学计算机学院 7/20/2021 算法Algorithm 第7页/共48页 南京邮电大学计算机学院 7/20/2021 算

3、法+数据结构=程序 第8页/共48页 南京邮电大学计算机学院 7/20/2021 第9页/共48页 南京邮电大学计算机学院 7/20/2021 input)：算法有零个或多个输入量； (output)：算法至少产生一个输出量； (definiteness)：算法的每一条指令都有确切的定义，没有二义性； (effectiveness)：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现； (finiteness)：算法必须总能在执行有限步之后终止。 算法的五个特征: 第10页/共48页 南京邮电大学计算机学院 7/20/2021 第11页/共48页 南京邮电大学计算机学

4、院 7/20/2021 第12页/共48页 南京邮电大学计算机学院 7/20/2021 gcd(24, 60) =gcd(60 mod 24, 24) =gcd(24 mod 12, 12)=12 反复执行：gcd(m, n)=gcd(n mod m, m) 直到：n mod m=0 时的n =gcd(12, 24) =gcd(0, 12) 第13页/共48页 南京邮电大学计算机学院 7/20/2021 欧几里德递归算法 int RGcd(int m, int n) if(m=0) return n; return RGcd(n%m, m); int Gcd(int m, int n) if

5、(mn) Swap(m, n); / 保证mn return RGcd(m, n); 第14页/共48页 南京邮电大学计算机学院 7/20/2021 欧几里德迭代算法 int Gcd(int m, int n) if(m=0) return n; if(n=0) return m; if(mn) Swap(m, n); while(m0) int c=n%m; n=m; m=c; return n; gcd(m, n)=gcd(n mod m, m) 第15页/共48页 南京邮电大学计算机学院 7/20/2021 gcd的连续整数检测算法 最大公约数不会超过两数中的较小者， 即不会超过t=mi

6、nm,n(确定初值) 执行 while (m%t | n%t) t-; gcd(9, 27) , gcd(4, 6) 如t=4, (4%4|6%4)0 , t- t=3，(4%3|6%3)0 , t- t=2, (4%2|6%2)=0 , 故最大公约数为2 第16页/共48页 南京邮电大学计算机学院 7/20/2021 Gcd的连续整数检测算法 1、一个问题可以设计不同的算法； 如欧几里德，连续整数检测。 2、一个算法可以采用不同的形式； 如递归，迭代。 int Gcd(int m, int n) if (m=0) return n; if (n=0) return m; int t=mn?n

7、:m; / t=minm,n while (m%t | n%t) t-; return t; 第17页/共48页 南京邮电大学计算机学院 7/20/2021 第18页/共48页 南京邮电大学计算机学院 7/20/2021 假设某一负责人交给你一个很难的任务，几天后询问你问题 解决了没有？可能会发生如下图这样的情况： 问：“交给你的问题，解决方案设计出来了吗？” 答：“我找不到一个有效的算法来解决它，没能完成任务。 ” 第19页/共48页 南京邮电大学计算机学院 7/20/2021 问：“交给你的问题，解决方案设计出来了吗？” 答： “我找不到一个有效的算法来解决它，因为这样的算 法是不存在的。

8、” 不过，要证明一个问题不 存在有效算法，往往跟寻 找有效算法一样难。 第20页/共48页 南京邮电大学计算机学院 7/20/2021 问：“交给你的问题，解决方案设计出来了吗？” 答： “我找不到一个有效的算法来解决它，但不是我不行， 因为所有这些名人也都找不到解决它的有效算法。” 如果是你的话，你 愿意是哪种结果？ 第21页/共48页 南京邮电大学计算机学院 7/20/2021 第22页/共48页 南京邮电大学计算机学院 7/20/2021 第23页/共48页 南京邮电大学计算机学院 7/20/2021 第24页/共48页 南京邮电大学计算机学院 7/20/2021 第25页/共48页 南

9、京邮电大学计算机学院 7/20/2021 第26页/共48页 南京邮电大学计算机学院 7/20/2021 第27页/共48页 南京邮电大学计算机学院 7/20/2021 理解问题 选择求解方法 确定数据结构 设计算法 正确性证明 分析算法 编写代码 第28页/共48页 南京邮电大学计算机学院 7/20/2021 第29页/共48页 南京邮电大学计算机学院 7/20/2021 对于最优化问题，一个算法如果致力于 寻找近似解而不是最优解，被称为 （approximation algorithm）。 如果在算法中需做出某些随机选择，则 称为（randomized algorithm）。 第30页/共

10、48页 南京邮电大学计算机学院 7/20/2021 第31页/共48页 南京邮电大学计算机学院 7/20/2021 第32页/共48页 南京邮电大学计算机学院 7/20/2021 第33页/共48页 南京邮电大学计算机学院 7/20/2021 第34页/共48页 南京邮电大学计算机学院 7/20/2021 第35页/共48页 南京邮电大学计算机学院 7/20/2021 第36页/共48页 南京邮电大学计算机学院 7/20/2021 斐波那契数列 1 nFFF 1, F0F 2n1nn 10 第37页/共48页 南京邮电大学计算机学院 7/20/2021 当一个算法采用递归方式定义时便成为。一个

11、递归算法是指直接或间接调用自身的算法。 求Fn long Fib( long n) if(n=1) return n; else return Fib(n-2)+Fib(n-1); 第38页/共48页 南京邮电大学计算机学院 7/20/2021 第39页/共48页 南京邮电大学计算机学院 7/20/2021 第40页/共48页 南京邮电大学计算机学院 7/20/2021 第41页/共48页 南京邮电大学计算机学院 7/20/2021 第42页/共48页 南京邮电大学计算机学院 7/20/2021 第43页/共48页 南京邮电大学计算机学院 7/20/2021 汉诺塔问题 enum tower

12、A=X, B=Y, C=Z; void Move(int n,tower x,tower y) /将第n个圆盘从塔座x移到塔座y的顶部 cout The disk n is moved from char(x) to top of tower char(y) endl; 第44页/共48页 南京邮电大学计算机学院 7/20/2021 void Hanoi(int n, tower x, tower y, tower z) /将x上部的n个圆盘移到y上，顺序不变。 if (n) Hanoi(n-1, x, z, y); Move(n,x,y); Hanoi(n-1, z, y, x); 第45页/共48页 南京邮电大学计算机学院 7/20/