计算机程序设计基础 第四章算法.ppt

《计算机程序设计基础 第四章算法.ppt》由会员分享，可在线阅读，更多相关《计算机程序设计基础 第四章算法.ppt（71页珍藏版）》请在三一办公上搜索。

1、计算机程序设计基础,第四章 算 法,提 纲,4.1 算法概念与特征（阅读）4.2 算法描述（阅读）4.3 算法设计与实现（阅读）4.4 递归算法4.5 容 错4.6 算法复杂度本章小结,4.1 算法概念与特征,算法基本概念算法定义：解决问题的方法与步骤设计算法的目的：给出解决问题的逻辑描述，根据算法描述进行实际编程算法特征有穷性：算法在每种情况下都可以在有限步后终止确定性：算法步骤的顺序和内容没有二义性输入：算法有零个或多个输入输出：算法至少具有一个输出有效性：所有操作具有明确含义，并能在有限时间内完成正确性不是算法的特征，算法的正确性需要数学证明！,算法示例一：幻方,算法示例一：幻方,算法示

2、例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,算法示例一：幻方,三阶幻方填充步骤,步骤1：把 1 写在第一行中间一格步骤2：在该格右上方的那一格中写入下一自然数在此过程中，若该数已超出 3 3 幻方范围，则将该数书写在其所在的那一排或列的另一端格子中每写完三个数，将第四个数写在第三个数下面格子中步骤3：重复步骤2，直到所有格子均填满,算法示例二：查英文单词,步骤1：翻开词典任意一页步骤2：若所要的词汇按字母排列顺序在本页第一个单词之前，则往前翻开任意

3、一页，重复步骤2；若所查词汇在本页最后一个单词之后，则往后翻开任意一页，重复步骤2步骤3：若上述两条件均不满足，则该单词要么在本页上，要么词典中不存在依次比较本页单词，或者查出该单词，或者得到该单词查不到的结论,算法描述,伪代码混合自然语言与计算机语言、数学语言的算法描述方法优点：方便，容易表达设计者思想，能够清楚描述算法流程，便于修改缺点：不美观，复杂算法不容易理解流程图（程序框图）使用图形表示算法执行逻辑优点：美观，算法表达清晰缺点：绘制复杂，不易修改，占用过多篇幅,伪代码,顺序结构分支结构循环结构,执行某任务执行下一任务,if(条件表达式)switch(条件变量)处理条件为真的情况cas

4、e 常量表达式 1:处理分支 1elsecase 常量表达式 2:处理分支 2 处理条件为假的情况default:处理默认分支,for(初始化表达式;条件表达式;步进表达式)|while(条件表达式)循环体内部代码逻辑描述,流程图,常用流程图的框图与符号,幻方流程图,查单词流程图,4.3 算法设计与实现,算法设计与实现构造算法解决问题按照自顶向下、逐步求精的方式进行使用程序设计语言编程实现典型示例素性判定问题最大公约数问题,素性判定问题,判断给定的某个自然数 n（大于 2）是否为素数算法逻辑输入：大于 2 的正整数 n输出：该数是否为素数，若为素数返回 TRUE，否则返回 FALSE步骤 1：

5、设除数 i 为 2步骤 2：判断除数 i 是否已为 n，若为真返回 TRUE，否则继续步骤 3：判断 n%i 是否为 0，若为 0 返回 FALSE，否则继续步骤 4：将除数 i 递增，重复步骤 2,素性判定函数入门版,验证其为算法：对照算法五个基本特征证明算法正确测试算法,BOOL IsPrime(unsigned int n)unsigned int i=2;while(i n)if(n%i=0)return FALSE;i+;return TRUE;,C语言基本类型：int(long,short)char double float 定义类型：enum BOOL FALSE,TRUE;定义

6、布尔类型定义变量：enum BOOL bool;/缺点是每次定义变量，都需要书写 enum，很不方用typedef定义类型：typedef enum _BOOL FALSE,TRUE BOOL;,素性判定函数家庭基本版,为什么可以使用 sqrt(n)代替 n？sqrt 为标准库中的求平方根函数,BOOL IsPrime(unsigned int n)unsigned int i=2;while(i=(unsigned int)sqrt(n)if(n%i=0)return FALSE;i+;return TRUE;,素性判定函数家庭高级版,家庭高级版有什么改进？,BOOL IsPrime(uns

7、igned int n)unsigned int i;if(n%2=0)return FALSE;i=3;while(i=(unsigned int)sqrt(n)if(n%i=0)return FALSE;i+=2;return TRUE;,BOOL IsPrime(unsigned int n)unsigned int i=2;while(i=(unsigned int)sqrt(n)if(n%i=0)return FALSE;i+;return TRUE;,素性判定函数小型企业版,小型企业版有什么改进？,BOOL IsPrime(unsigned int n)unsigned int i

8、;if(n%2=0)return FALSE;i=3;while(i=(unsigned int)sqrt(n)+1)if(n%i=0)return FALSE;i+=2;return TRUE;,BOOL IsPrime(unsigned int n)unsigned int i;if(n%2=0)return FALSE;i=3;while(i=(unsigned int)sqrt(n)if(n%i=0)return FALSE;i+=2;return TRUE;,素性判定函数大型企业版,大型企业版有什么改进？,BOOL IsPrime(unsigned int n)unsigned in

9、t i,t;if(n%2=0)return FALSE;i=3;t=(unsigned int)sqrt(n)+1;while(i=t)if(n%i=0)return FALSE;i+=2;return TRUE;,BOOL IsPrime(unsigned int n)unsigned int i;if(n%2=0)return FALSE;i=3;while(i=(unsigned int)sqrt(n)+1)if(n%i=0)return FALSE;i+=2;return TRUE;,算法选择,算法选择的权衡指标正确性：算法是否完全正确？效率：在某些场合，对程序效率的追求具有重要意义可

10、理解性：算法是否容易理解，也是必须要考虑的算法评估：衡量算法的好坏，主要是效率,最大公约数问题,求两个正整数 x 与 y 的最大公约数函数原型设计unsigned int gcd(unsigned int x,unsigned int y);,最大公约数函数：穷举法,unsigned int gcd(unsigned int x,unsigned int y)unsigned int t;t=x y?x:y;while(x%t!=0|y%t!=0)t-;return t;,最大公约数函数：欧氏算法,输入：正整数 x、y输出：最大公约数步骤 1：x 整除以 y，记余数为 r步骤 2：若 r 为

11、0，则最大公约数即为 y，算法结束步骤 3：否则将 y 作为新 x，将 r 作为新 y，重复上述步骤unsigned int gcd(unsigned int x,unsigned int y)unsigned int r;while(TRUE)r=x%y;if(r=0)return y;x=y;y=r;,4.4 递归算法,递归问题的引入递推公式：数学上非常常见例一：阶乘函数：0!=1，n!=n(n-1)!例二：斐波那契数列函数：f(1)=f(2)=1，f(n)=f(n-1)+f(n-2)递推函数一定是分段函数，具有初始表达式递推函数的计算逻辑：逐步简化问题规模递归的工作步骤递推过程：逐步分解

12、问题，使其更简单回归过程：根据简单情形组装最后的答案,阶乘函数,使用循环实现unsigned int GetFactorial(unsigned int n)unsigned int result=1,i=0;while(+i=n)result*=i;return result;使用递归实现unsigned int GetFactorial(unsigned int n)unsigned int result;if(n=0)result=1;elseresult=n*GetFactorial(n-1);return result;,斐波那契数列函数：f(1)=f(2)=1，f(n)=f(n-1

13、)+f(n-2),用递归方式实现:unsigned int GetFibonacci(unsigned int n)if(n=2|n=1)return 1;else return GetFibonacci(n-1)+GetFibonacci(n-2);,斐波那契数列函数,使用循环实现unsigned int GetFibonacci(unsigned int n)unsigned int result,i,f1,f2;if(n=2|n=1)return 1;f2=1;f1=1;for(i=3;i=n;i+)result=f1+f2;f1=f2;f2=result;return result;使

14、用递归实现unsigned int GetFibonacci(unsigned int n)if(n=2|n=1)return 1;elsereturn GetFibonacci(n-1)+GetFibonacci(n-2);,循环与递归的比较,循环使用显式的循环结构重复执行代码段，递归使用重复的函数调用执行代码段循环在满足其终止条件时终止执行，而递归则在问题简化到最简单情形时终止执行循环的重复是在当前迭代执行结束时进行，递归的重复则是在遇到对同名函数的调用时进行循环和递归都可能隐藏程序错误，循环的条件测试可能永远为真，递归可能永远退化不到最简单情形理论上，任何递归程序都可以使用循环迭代的方法

15、解决递归函数的码更短小精悍一旦掌握递归的思考方法，递归程序更易理解,递归函数调用的栈框架,#include#include zylib.hvoid PrintWelcomeInfo();unsigned int GetInteger(STRING prompt);unsigned int GetFactorial(unsigned int n);int main()unsigned int n,result;PrintWelcomeInfo();n=GetInteger(Input a non-negative number:);result=GetFactorial(n);printf(%d

16、!=%d.n,n,result);return 0;void PrintWelcomeInfo()printf(The program gets a number and computes the factorial.n);,递归函数调用的栈框架,unsigned int GetInteger(STRING prompt)unsigned int t;printf(prompt);t=GetIntegerFromKeyboard();return t;unsigned int GetFactorial(unsigned int n)unsigned int result;if(n=0)resu

17、lt=1;else result=n*GetFactorial(n-1);return result;,函数调用栈框架,3,n,result,main,main 函数栈框架,函数调用栈框架,GetFactorial,第一次以 3 为参数调用 GetFactorial，进入函数时,3,n,result,函数调用栈框架,GetFactorial,第二次以 2 为参数调用 GetFactorial，进入函数时,GetFactorial,2,n,result,函数调用栈框架,GetFactorial,第三次以 1 为参数调用 GetFactorial，进入函数时,GetFactorial,GetFac

18、torial,1,n,result,函数调用栈框架,GetFactorial,第三次以 1 为参数调用 GetFactorial，退出函数前,GetFactorial,GetFactorial,1,1,n,result,函数调用栈框架,GetFactorial,第二次以 2 为参数调用 GetFactorial，退出函数前,GetFactorial,2,2,n,result,函数调用栈框架,GetFactorial,第一次以 3 为参数调用 GetFactorial，退出函数前,3,6,n,result,函数调用栈框架,3,6,n,result,main,递归调用结束后的 main 函数栈框架

19、,汉诺塔问题,假设有三个分别命名为 X、Y 和 Z 的塔座，在塔座 X 上插有 n 个直径大小不同、依小到大分别编号为 1,2,.,n 的圆盘，如图所示：要求将塔座X上的 n 个圆盘移动到塔座 Z 上并按相同顺序叠放，圆盘移动时必须遵循下述规则：每次只能移动一个圆盘；圆盘可以插在X、Y与Z中的任意塔座上；任何时刻都不能将较大的圆盘压在较小的圆盘上。如何实现移动圆盘的操作呢？,问题分析,待解决的问题Q1：是否存在某种简单情形，问题很容易解决Q2：是否可将原始问题分解成性质相同但规模较小的子问题，且新问题的解答对原始问题有关键意义解答方案A1：只有一个圆盘时是最简单情形A2：对于 n 1，考虑 n

20、 1 个圆盘，如果能将 n-1 个圆盘移动到某个塔座上，则可以移动第 n 个圆盘策略：首先将 n 1 个圆盘移动到塔座 Y 上，然后将第 n 个圆盘移动到 Z 上，最后再将 n-1 个圆盘从 Y 上移动到 Z 上,汉诺塔演示,伪代码,void MoveHanoi(unsigned int n,HANOI from,HANOI tmp,HANOI to)if(n=1)将一个圆盘从 from 移动到 to else 将 n 1 个圆盘从 from 以 to 为中转移动到 tmp 将圆盘 n 从 from 移动到 to 将 n-1个圆盘从 tmp 以 from 为中转移动到 to,程序代码,#inc

21、lude#include zylib.h/*枚举类型 HANOI，其文字分别表示三个圆柱的代号*/typedef enum X,Y,Z HANOI;void PrintWelcomeInfo();unsigned int GetInteger(STRING prompt);void MoveHanoi(unsigned int n,HANOI from,HANOI tmp,HANOI to);STRING ConvertHanoiToString(HANOI x);void MovePlate(unsigned int n,HANOI from,HANOI to);int main()unsi

22、gned int n;PrintWelcomeInfo();n=GetInteger(Input number of plates:);MoveHanoi(n,X,Y,Z);return 0;,程序代码,void PrintWelcomeInfo()printf(The program shows the moving process of Hanoi Tower.n);unsigned int GetInteger(STRING prompt)unsigned int t;printf(prompt);t=GetIntegerFromKeyboard();return t;STRING Co

23、nvertHanoiToString(HANOI x)switch(x)case X:return X;case Y:return Y;case Z:return Z;default:return Error;,程序代码,void MovePlate(unsigned int n,HANOI from,HANOI to)STRING from_str,to_str;from_str=ConvertHanoiToString(from);to_str=ConvertHanoiToString(to);printf(%d:%s-%sn,n,from_str,to_str);void MoveHan

24、oi(unsigned int n,HANOI from,HANOI tmp,HANOI to)if(n=1)MovePlate(n,from,to);else MoveHanoi(n-1,from,to,tmp);MovePlate(n,from,to);MoveHanoi(n-1,tmp,from,to);,递归信任,递归实现是否检查了最简单情形在尝试将问题分解成子问题前，首先应检查问题是否已足够简单在大多数情况下，递归函数以 if 开头如果程序不是这样，仔细检查源程序是否解决了最简单情形大量递归错误是由没有正确解决最简单情形导致的最简单情形不能调用递归递归分解是否使问题更简单只有分解出的

25、子问题更简单，递归才能正确工作，否则将形成无限递归，算法无法终止,递归信任,问题简化过程是否能够确实回归最简单情形，还是遗漏了某些情况如汉诺塔问题需要调用两次递归过程，程序中如果遗漏了任意一个都会导致错误子问题是否与原始问题完全一致如果递归过程改变了问题实质，则整个过程肯定会得到错误结果使用递归信任时，子问题的解是否正确组装为原始问题的解将子问题的解正确组装以形成原始问题的解也是必不可少的步骤,4.5 容 错,容错的定义：允许错误的发生错误的处理很少见的特殊情况或普通错误：忽略该错误不对程序运行结果产生影响用户输入错误：通知用户错误性质，提醒用户更正输入致命错误：通知用户错误的性质，停止执行典

26、型容错手段数据有效性检查程序流程的提前终止断言与不变量,数据有效性检查,void GetUserInput()获取用户输入数据 while(用户输入数据无效)通知用户输入数据有误，提醒用户重新输入数据 重新获取用户输入数据 void Input()c=GetFloat(Input a temperature value(C):);while(c=absolute_zero)printf(The temperature value is below%.2f.n,absolute_zero);c=GetFloat(Input a temperature greater than the absol

27、ute zero:);,程序流程的提前终止,const int failed_in_testing_primality=1;BOOL IsPrime(unsigned int n)unsigned int i,t;if(n=1)printf(IsPrime:Failed in testing the primality of%d.,n);exit(failed_in_testing_primality);if(n=2)return TRUE;if(n%2=0)return FALSE;i=3;t=(unsigned int)sqrt(n)+1;while(i=t)if(n%i=0)return

28、 FALSE;i+=2;return TRUE;,素性判定函数终极版,BOOL IsPrime(unsigned int n)unsigned int i,t;if(n=1)PrintErrorMessage(FALSE,IsPrime:Failed in testing the primality of%d.,n);if(n=2)return TRUE;if(n%2=0)return FALSE;i=3;t=(unsigned int)sqrt(n)+1;while(i=t)if(n%i=0)return FALSE;i+=2;return TRUE;,断言与不变量,断 言任何程序都存在一些

29、特定点，只要程序运行到该处，关于某个计算状态的判断就总是成立的断言的定义：关于某个计算状态的判别式断言的格式使用 assert 宏在判别式为假时说明程序出现错误，终止程序执行断言主要用于调试程序，在实际程序中一般不出现如果不需要需要使用断言，可以在文件开头定义 NDEBUG 宏，而不需要逐条删除断言语句,素性判定函数欧洲版,#include BOOL IsPrime(unsigned int n)unsigned int i,t;assert(n 1);if(n=2)return TRUE;if(n%2=0)return FALSE;i=3;t=(unsigned int)sqrt(n)+1;

30、while(i=t)if(n%i=0)return FALSE;i+=2;return TRUE;,素性判定函数欧洲版,#include#define NDEBUGBOOL IsPrime(unsigned int n)unsigned int i,t;assert(n 1);if(n=2)return TRUE;if(n%2=0)return FALSE;i=3;t=(unsigned int)sqrt(n)+1;while(i=t)if(n%i=0)return FALSE;i+=2;return TRUE;,算法复杂度,引入算法复杂度的目的度量算法的效率与性能大 O 表达式算法效率与性能

31、的近似表示（定性描述）算法执行时间与问题规模的关系表示原则忽略所有对变化趋势影响较小的项，例如多项式忽略高阶项之外的所有项忽略所有与问题规模无关的常数，例如多项式的系数,标准算法复杂度类型,O(1)：常数级，表示算法执行时间与问题规模无关O(log(n)：对数级，表示算法执行时间与问题规模的对数成正比O(sqrt(n)：平方根级，表示算法执行时间与问题规模的平方根成正比O(n)：线性级，表示算法执行时间与问题规模成正比O(n*log(n)：n*log(n)级，表示算法执行时间与问题规模的 n*log(n)成正比O(n2)：平方级，表示算法执行时间与问题规模的平方成正比,算法复杂度估计,for(

32、i=0;i n;i+)printf(No.%d:Hello,World!n,i);for(i=0;i n;i+)for(j=0;j n;j+)printf(Hello,World!n);for(i=0;i n;i+)for(j=i;j n;j+)printf(Hello,World!n);,O(n),O(n2),O(n2),本章小结,算法：解决问题的方法与步骤算法基本特征：有穷性、确定性、输入、输出、有效性描述工具：伪代码与流程图算法设计与实现某个问题可能具有多种不同的算法实现策略，都可以解决问题，但美感有上下，效率有高低算法复杂度：用于衡量算法效率递归算法类比：数学归纳法与递推公式递归信任容错：允许程序中出现错误处理错误方式的方式有多种：数据有效性检查、程序流程的提前终止、断言与不变量,作 业,第 153 页：习题二第 5 小题第 154 页：习题二第 8、10 小题,