北邮算法设计与分析 第一章 引言

第38页
安师大数学计算机科学学院
2014年6月28日星期六
1.4.3 归纳证明
定理1-1 对于n≥0，程序1-5是正确的。 证明：（归纳法证明） 当n是1位数时，程序显然是正确的。 假定函数PrintDigit对所有位数小于k（k＞1）的正 整数都能正确运行，当 n 的位数为 k 位时，此时有 n≥10 ，算法必定先执行语句 cout<<n%10; 然后执 行语句if(n>10) PrintDigit(n/10);。
第31页
安师大数学计算机科学学院
2014年6月28日星期六
可以用所谓的递归树（recursive tree）来描述程 序1-4的函数Fib执行时的调用关系。
图1-2 计算Fib（4）的递归树
第32页
安师大数学计算机科学学院
2014年6月28日星期六
递归数据结构 使用递归方式定义的数据结构称为递归数据结构 （recursive data structure）。
第10页
Begin
Rm%n
Y
r=0？ N
Swap(m.n)
End
安师大数学计算机科学学院
2014年6月28日星期六
假设 m=21 和 n=45，求21和45的最大公因子
第一步：r=m%n=21%45=21； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=45, n=r=21，返回第一步。 第一步：r=m%n=45%21=3； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=21 ， n=r=3，返回第一步。 第一步：r=m%n=21%3=0； 第二步：r 等于0，算法结束，3即为21和45的最大公因子。
2014年6月28日星期六

• 求gcd(m,n)的原理： （结构化的描述） • 第一步：如果n=0,返回m的值作为结果，结束；否则进 入第二步。 • 第二步：用n除m,余数赋值给r，进入第三步。 • 第三步：将n的值赋给m，将r的值赋给n，返回第一步。
例： gcd(60,24)=? 1-1、m=60, n=24 1-2、60 mod 24=12, r=12, 1-3、m=24, n=12 2-1、24 mod 12=0,r=0 2-2、m=12, n=0 2-3、条件“n=0”满足，返回gcd(m, n)=m=12
• 算法二：连续整数检测法
第一步：将min{m,n}赋值给t。 第二步：m除以t，如果余数为0，进入第三步，否则进入第 四步。 第三步：n除以t，如果余数为0，返回t的值；否则进入第四 步。 第四步：把t的值减1，返回第三步。 例：gcd(60, 24) t=min{60, 24}=24, m=60, n=24 60mod24=12≠0, t=23, 24 mod 23=1 ≠0 t=22, 24 mod 22=2 ≠0 t=21, 24 mod 21=3 ≠0 ….. t=12, 24 mod 12=0, 返回gcd(m, n)=t=12
第1章 绪论
1.1 什么是算法 1.2 算法问题求解基础 1.3 重要问题类型 1.4 基本数据结构 本章小结
1.1 算法的概念
• 没有一个统一的严谨的定义。一般而言， 对于计算机算法的概念是这样描述的：算 法是在有限步骤内求解某一问题所使用的 一组定义明确的指令。 • 本书采用的定义：An algorithm is a sequence of unambiguous instructions for solving a problem=算法是求解某一 问题所使用的一系列清晰的指令。

1.图的表示
计算机算法中,图主要可以用两种方法表示:邻接矩阵和邻接链 表。n个顶点的邻接矩阵是一个n*n的布尔矩阵，图中每个顶点都 用一行和一列来表示，如果从第i个顶点到第j个顶点之间有连接 边，则矩阵中第i行第j列的元素等于1，如果没有这样的边，则等 于0。例如，图1.6a所对应的邻接矩阵可以参见图1.7a。注意，一 个无向图的邻接矩阵总是对称的（为什么？），也就是说，当i≥0， j≤n-1时，A[i,j]=A[j,i]。
用于计算gcd(m,n)连续整数检测算法 第一步：将min{m,n}的值赋给t。 第二步：m除以t，如余数为0。进入第三步； 否则，进入第四步。 第三步：n除以t，如果余数为0，返回t的值 作为结果；否则，进入第四步。
第四步：把t的值减1。返回第二步。
中学里计算gcd(m,n)过程 第一步：找到m的所有质因数。 第二步：找到n的所有质因数。 第三步：从第一步和第二步求得的质因数分解式 中找出所有的公因数（如果p是一个公因数，而 且在m和n的质因数分解式分别出现过pm 和pn次，
1.3.2 查找
查找问题涉及到从给定的集合（或者是多重集， 它允许几个无素具有相同的值）中找寻一个给定的值， 称为查找键。对于查找来说，也没有一种算法对于任 何情况都是最适合的。有些算法速度比其他算法快， 但却需要较多的存储空间；有些算法速度非常快，但 仅适用于有序的数组，如此等等。
1.3.3 串处理
述。伪代码是自然语言和类编程语言组成的混合结构。伪代码往往比 自然语言更精确，而且伪代码生成的算法描述往往会更简洁。
1.2.7 证明算法的正确性
一旦完成了以算法的描述，我们必须证明它的正确性。也就是说， 我们必须证明对于每一个合法输入，该算法都会在有限的时间内输出

4. if i ＜ n return i
T(n) ：算法的运行时间 问题规模n的函数
输入分布：最坏情况、 最好情况、平均情况
Tmax(n), Tmin(n), Tavg(n)
算法运行时间
假设每条语句的执行 时间均为单位时间。
=
全部语句的执行时间之和
算法运行中主要影响运行 时间的语句是基本操作， 即占有最多比例的语句。
算法设计
丘奇-图灵论点：凡是可计算的函数都是一般递归函数 （或图灵机可计算函数） • 凡是可以从某些初始符号开始，而在有 限步骤内计算的函数都是递归函数。 • 计算机只能计算一般递归函数。 • 算法设计就是根据某个算法设计策略写 出递归函数或递归算法。
算法的描述方法
• 可以用自然语言、伪代码(pseudocode)或计 算机程序语言来描述算法，必须精确地描 述计算过程。
算法设计与分析
Algorithm Design And Analysis
东北大学 信息学院 计算机应用技术研究所 郭楠
2015版
教学目标及内容
• 教学内容
– 王晓东，《计算机算法设计与分析》，1~6章
• 教学目标
– 通过对典型算法的分类介绍，掌握算法设计的主要策 略以及对算法性能正确分析的能力。 策略 算法设计
– 用有限的指令和有限的存储空间可算尽一切可算之物 – 凡是可计算的过程都可用图灵机实现 – 机器能思考吗？
程序 内部状态
纸带
Here is an implementation of a Turing machine
控制器
一台图灵机是一个七元组M = (Q, Σ, Γ, Δ, q0, B, F)
– – – – Q是内部状态的有穷集合； Σ是输入符号集，其中不包含特殊的空白符； Γ是允许使用的纸带符号的有穷集合； Δ是转移函数（即程序），根据当前状态及当前输入 符号确定下一状态及读写头的动作，包括对输入符 号的运算以及读写头的移动（左移L或右移R）；