算法问题求解基础

1、第1章 算法问题求解基础 1 第1章 算法问题求解基础 2 平时要求：平时要求： 按时上下课、课堂不吵闹、手机调成非铃声状态按时上下课、课堂不吵闹、手机调成非铃声状态 考试成绩：考试成绩： 平时表现（考勤、随堂提问、作业等）：平时表现（考勤、随堂提问、作业等）：20%20% 期末考试：期末考试：80%80% 第1章 算法问题求解基础 3 课程简介课程简介 课程名称：课程名称：算法设计与分析算法设计与分析 Design and Analysis of Algorithms Design and Analysis of Algorithms 先修课程：先修课程： 面向对象程序设计语言面向对象程序设

2、计语言C+C+，数据结构，数据结构， 离散结构离散结构 第1章 算法问题求解基础 4 第1章 算法问题求解基础 第1部分 算法和算法分析 1.1 算法概述 1.2 问题求解方法 1.3 算法设计与分析 1.4 递归和归纳 第1章 算法问题求解基础 5 1.1.1 什么是算法 算法是计算机学科的一个重要分支，它是计算机科学的 基础，更是计算机程序的基石。算法是计算机求解问题 的特殊方法。学习算法，一方面需要学习求解计算领域 中典型问题的各种有效算法，还要学习设计新算法和分 析算法性能的方法。 1.1 算法概述 算法（algorithm)：一个算法是对特定问题求解步骤的 一种描述，它是指令的有限序

3、列。 中国的珠算口诀可视为典型的算 法，它将复杂的计算描述为一系 列的算珠拨动动作。 第1章 算法问题求解基础 算法具有下列5个特征： 6 输入（input）：算法有零个或多个输入量； 输出（output）：算法至少产生一个输出量； 确定性（definiteness）：算法的每一条指令都有确切 的定义，没有二义性； 能行性（effectiveness）：算法的每一条指令必须足 够基本，它们可以通过已经实现的基本运算执行有限次 来实现； 有穷性（finiteness）：算法必须总能在执行有限步之 后终止。 第1章 算法问题求解基础 7 最早的算法是欧几里德的“求最大公因子算法” 辗转相除法 欧几

4、里德算法(辗转相除法) 计算两个整数m和n（0mn)的最大公约数，记为gcd(m, n)。 其计算过程是重复应用下列等式，直到n mod m=0. gcd(m,n)=gcd(n mod m,m),对于m0 (1-1) 式中，n mod m表示n除以m之后的余数。 因为gcd(0,n)=n,n的最后取值也就是m和n最大公约数。 例如， gcd(24,60)=gcd(12,24)=gcd(0,12)=12 第1章 算法问题求解基础 8 【程序1-1】 欧几里德递归算法 void Swap(inta=b;b=c; int RGcd(int m,int n) if(m=0) return n; ret

5、urn RGcd(n%m,m); int Gcd(int m,int n) if (mn) Swap(m,n); return RGcd(m,n); 第1章 算法问题求解基础 9 【程序1-2】 欧几里德迭代算法 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; 第1章 算法问题求解基础 10 迭代和递归的区别 迭代和递归各基于一种控制结构，都涉及到循环，都可无限进行。 迭代是循环求值，递归是调用本身； 迭代使用循环

6、结构，递归使用选择结构； 迭代是当循环条件不满足时终止，递归是当满足基本条件时终 止； 迭代是用计数器控制循环，不停地修改计数器的值，直到不满 足条件为止； 递归是逐渐逼近基本条件而终止，不断的对问题进行简化直到 可以直接计算基本问题为止。 第1章 算法问题求解基础 11 最大公约数问题还有其他算法。程序1-3的连续整数检测法的 依据直接来自最大公约数的定义：m和n的最大公约数是能够同 时整除它们的最大正整数。 【程序1-3】 Gcd的连续整数检测算法 int Gcd(int m,int n) if (m=0)return n; if (n=0)return m; int t=mn?n:m;

7、while (m%t | n%t) t-; return t; 第1章 算法问题求解基础 12 1.1.2 为什么学习算法 算法是计算机科学的基础，更是程序的基石，只有具有良好的 算法基础才能成为训练有素的软件人才。 对于计算机专业的学生来说，学习算法的理由是非常充分的。 因为你必须知道来自不同计算领域的重要算法，你也必须学 会设计新的算法、确认其正确性并分析其效率。 随着计算机应用的日益普及，各个应用领域的研究和技术人员 都在使用计算机求解他们各自专业领域的问题，他们需要设 计算法，编写程序，开发应用软件，所以学习算法对于越来 越多的人来说变得十分必要。 第1章 算法问题求解基础 Donal

8、d E. Knuth 13 l 计算机科学大师、“算法分析之父”唐德纳（1938年1 月10日-）现与其妻Jill生活于斯坦福校园内。 l 1974年美国计算机协会图灵奖 (ACM Turing Award) l 1979年美国前总统卡特授予的科学金奖(Medal of Science) l 1996年11月由于发明先进技术荣获极受尊重的京都奖 (Kyoto Prize)。 第1章 算法问题求解基础 14 1.2.1 问题和问题求解 1.2 问题求解方法 问题求解（problem solving）是寻找一种方法来实现目标。 问题求解过程（problem solving process）是人们通

9、过使用 问题领域知识来理解和定义问题，并凭借自身的经验和知 识去选择和使用适当的问题求解策略、技术和工具，将一 个问题描述转换成问题解的过程。 计算机求解问题的关键之一是寻找一种问题求解策略 （problem solving strategy），得到求解问题的算法， 从而得到问题的解。 第1章 算法问题求解基础 15 1.2.2 问题求解过程 问题求解的四步法简述如下： 理解问题（understand the problem） 设计方案（devise a plan） 实现方案（carry out the plan） 回顾复查（look back） 第1章 算法问题求解基础 16 1.2.3 系

10、统生命周期 划分为: 分析（analysis） 设计（design） 编码（coding or programming） 测试（testing） 维护（maintenance） 等5个阶段。前4个阶段属于开发期，最后一个阶段处于运 行期。 一个计算机程序的开发过程就是使用计算机求解问题的 过程。软件工程将软件开发和维护过程分成若干阶段， 称为系统生命周期或软件生命周期 第1章 算法问题求解基础 算法设计的整个过程，可以包含 问题需求的说明 数学模型的建立 算法的详细设计 算法的正确性验证 算法的实现 算法分析 程序测试 文档资料的编制 在此我们只关心算法的设计和分析。 17 第1章 算法问题求

11、解基础 18 1.3.1 算法问题求解过程 算法一般分为两类：精确算法和启发式算法。 精确算法（exact algorithm）总能保证求得问题的解。 启发式算法（heuristic algorithm）通过使用某种规则、 简化或智能猜测来减少问题求解时间。 1.3 算法设计与分析 第1章 算法问题求解基础 19 1.3.2 如何设计算法 使用计算机的问题求解策略主要指算法设计策略 （algorithm design strategy）。 算法设计技术（也称“策略”）是使用算法解题的一般性方 法，可用于解决不同计算领域的多种问题。 一般来说，算法的设计是一项创造性活动，但学习一些基本 的算法设

12、计策略是非常有用的。 算法设计方法主要有：递归法、分治法、贪心算法、动态规 划法、回溯法、分支限界法等，我们将在后面的章节中陆 续介绍。 第1章 算法问题求解基础 20 1.3.3 如何表示算法 算法的基本结构 用自然语言表示 用流程图表示 用N-S流程图表示 用伪代码表示 用计算机语言表示 第1章 算法问题求解基础 21 1.3.4 如何确认算法 确认一个算法是否正确的活动称为算法确认。 使用数学方法证明算法的正确性，称为算法证明。 程序测试（program testing）是指对程序模块或程序总 体，输入事先准备好的样本数据（称为测试用例，test case），检查该程序的输出，来发现程序

13、存在的错误及 判定程序是否满足其设计要求的一项积极活动。 第1章 算法问题求解基础 22 1.3.5 如何分析算法 算法分析（algorithm analysis）活动是指对算法的执行 时间和所需空间的估算。 在算法写成程序后，便可使用样本数据，实际测量一个程 序所消耗的时间和空间，这称为程序的性能测量 （performance measurement）。 第1章 算法问题求解基础 23 算法的正确性。 算法的时间复杂度：一个算法在计算机上运行所花费 的时间。 算法的空间复杂度：在存储器上所占用的存储空间 （主要考虑在算法运行过程中临时占用的存储空间的 大小）。 算法的易读性。 1.3.6 算

14、法评价 第1章 算法问题求解基础 24 1.4.1 递归 1.递归定义 递归（recursive）定义是一种直接或间接引用自身的定 义方法。 一个合法的递归定义包括两部分：基础情况和递归部分。 1.4 递归和归纳 第1章 算法问题求解基础 25 例1-1 斐波那契数列 根据这一定义，可以得到一个无穷数列 0,1,1,2,3,5,8,13,21,34,55，称为斐波那契数列。 1 10 21 10 nFFF , FF nnn 第1章 算法问题求解基础 26 2.递归算法 当一个算法采用递归方式定义时便成为递归算法。 一个递归算法是指直接或间接调用自身的算法。 【程序1-4】 求Fn long F

15、ib( long n) if(n=1) return n; else return Fib(n-2)+Fib(n-1); 第1章 算法问题求解基础 27 可以用递归树（recursive tree）来描述程序1-4的函数 Fib执行时的调用关系。 图图1-2 1-2 计算计算FibFib（4 4）的递归树）的递归树 第1章 算法问题求解基础 递归方法的主要优点：结构清晰、可读性强，而且 容易用数学归纳法证明算法的正确性，因此为设计 算法、调试程序带来了很大的方便。 递归算法的缺点：由于不断地函数调用，需要保存中间结果 以及进行参数的传递，递归方法算法的运行效率较低，无 论耗费的计算时间还是占用

16、的存储空间都比非递归算法要 多。 28 第1章 算法问题求解基础 29 1.4.2 递归算法示例 例1-2 逆序输出正整数的各位数 【程序1-5】 void PrintDigit(unsigned int n) cout=10) PrintDigit(n/10); /以逆序输出前k-1位数 第1章 算法问题求解基础 例1-3 汉诺塔问题（tower of Hanoi） 假定有三个塔座：X，Y，Z，在塔座X上有n个直径大小各不 相同，按圆盘大小从小到大编号为1，2，n的圆盘。 现要求将X塔座上n个圆盘移到塔座Y上，并仍按同样顺序 叠排。 圆盘移动时必须遵循下列规则： （1）每次只能移动一个圆盘；

17、 （2）圆盘可以加到塔座X，Y，Z中任意一个上； （3）任何时刻都不能将一个较大的圆盘放在较小的圆盘之 上。 30 第1章 算法问题求解基础 31 第1章 算法问题求解基础 汉诺塔的递归思想 假设有 n 个圆盘，三根相邻的柱子标号为 A，B，C，并且 A 柱上圆盘由小到大依次编号为1，2，n。现要把按 金字塔状叠放着 n 个不同大小的圆盘，一个一个移动到 柱子 C 上。 当只有一个盘子时，即 n=1，则只需经过一次移动将盘子从 A 柱到 C 柱；当 n1 时可以把最上面 n-1个圆盘看作 是一个整体。 这样 n 个圆盘就分成了两部分：上面 n-1 个圆盘和最下面 的 1 个圆盘。 32 第1章

18、 算法问题求解基础 示例：三个盘子的过程 33 ABC 初始状态 第1章 算法问题求解基础 34 第1步: A-C ABC 第1章 算法问题求解基础 35 第2步: A-B ABC 第1章 算法问题求解基础 36 第3步: C-B ABC 第1章 算法问题求解基础 37 第4步: A-C ABC 第1章 算法问题求解基础 38 第5步: B-A ABC 第1章 算法问题求解基础 39 第6步: B-C ABC 第1章 算法问题求解基础 40 第7步: A-C ABC 第1章 算法问题求解基础 41 【程序1-6】 汉诺塔问题 enum tower 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; void Hanoi(int n, tower x, tower y, tower z) /将x上部的n个圆盘移到y上，顺序不变。