第1周绪论第4讲-算法及其描述.pdf

《第1周绪论第4讲-算法及其描述.pdf》由会员分享，可在线阅读，更多相关《第1周绪论第4讲-算法及其描述.pdf（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据元素之间的关系有逻辑关系和物理关系，数据元素之间的关系有逻辑关系和物理关系，对应对应的运算有的运算有基基 于逻辑结构的运算描述于逻辑结构的运算描述和和基于存储结构的运算实现基于存储结构的运算实现。 通常通常把把基于存储结构基于存储结构的运算实现的步骤的运算实现的步骤或过程称为或过程称为算法算法。 基于存储基于存储结构结构算法算法 算法的五个重要的特性算法的五个重要的特性 （1） 有穷性有穷性：在有穷步：在有穷步之后之后结束，算法能够停机。结束，算法能够停机。 （2） 确定性确定性：无二义性。：无二义性。 （4） 有输入有输入 （5） 有输出有输出 表示存在数据处理表示存在数据处理 （3）

2、可行性可行性：可通过基本运算有限次执行：可通过基本运算有限次执行来来实现，实现， 也就是算法中每一个动作能够被机械地执行。也就是算法中每一个动作能够被机械地执行。 【例例1- -2】考虑下列两段考虑下列两段描述描述，这两段描述均不能满足算法这两段描述均不能满足算法 的特性的特性，试问它们违反了哪些特性试问它们违反了哪些特性？ 其中有一其中有一个死循环，违反了个死循环，违反了 算法的算法的有有穷性穷性特性。特性。 （1）描述一）描述一 其中包含其中包含除零错误，违反了除零错误，违反了 算法算法的的可行性可行性特性特性 （2） 描述二描述二 返回值返回值算法对应的函数名算法对应的函数名( (形参列

3、表形参列表) ) /临时变量的定义临时变量的定义 /实现由输入参数到输出参数的操作实现由输入参数到输出参数的操作 函 数 体 函 数 体 返回值返回值：通常为通常为bool类型，表示算法是否成功执行。类型，表示算法是否成功执行。 形参列表形参列表：由由输入型参数输入型参数和和输出型参数输出型参数构成。构成。 算法输入算法输入算法输出算法输出 算法算法输入输入输出输出 算法描述的一般格式算法描述的一般格式 C+语言中提供了一种语言中提供了一种引用引用运算符运算符“ int 引用引用 引用示例引用示例 a 10 b 两个变量共享内存空间两个变量共享内存空间 如何描述输出型参数？如何描述输出型参数？

4、 a、b同步发生改变同步发生改变 示例：示例：设计一个设计一个交换两个整数的算法。交换两个整数的算法。 void swap1(int x，int y) int tmp; tmp=x; x=y; y=tmp; 交换形参交换形参x和和y的值的值 当执行语句当执行语句swap1(a,b)时，时，a和和b实参值不会发生了交换。实参值不会发生了交换。 分析：分析：x、y既是输入型参数，也是输出型参数既是输入型参数，也是输出型参数 编写一个函数编写一个函数swap1(x，y)： 改正方法改正方法1：采用采用指针的方式来回传形参的值，需将上述函数改为指针的方式来回传形参的值，需将上述函数改为： 上述函数的调

5、用改为上述函数的调用改为swap2( tmp=*x;/将将x的值放在的值放在tmp中中 *x=*y; /将将x所指的值改为所指的值改为*y *y=tmp；/将将y所指的值改为所指的值改为tmp 交换形参交换形参x和和y 所指向的值所指向的值 void swap(int x=y; y=tmp; 改正方法改正方法2：采用采用引用引用型型形参形参 将输出型将输出型形参改为引用类型。形参改为引用类型。 当执行语句当执行语句swap(a,b)时，时，形形、实参的匹配、实参的匹配相当于：相当于： int /a为为x的引用的引用 int /b为为y的引用的引用 这样，这样，a与与x共享存储空间、共享存储空间

6、、b与与y共享存储空间，共享存储空间，因此因此执行函数后执行函数后a 和和b的值发生的值发生了了交换交换 简单简单。 交换形参交换形参x和和y的值的值 void fun1(int n) int m=2; fun2(m); printf(“%dn”,m); void fun2(int x) x+; printf(“%dn”,x); 实参实参 普通形参普通形参 fun1(m)fun2(x) 实参到形参单向值传递实参到形参单向值传递 普通的参数传递普通的参数传递 void fun1(int n) int m=2; fun2(m); printf(“%dn”,m); void fun2(int pri

7、ntf(“%dn”,x); 实参实参 引用型形参引用型形参 引用类型的参数传递引用类型的参数传递 fun1(m)fun2(x) 实参实参到形参单向值传递到形参单向值传递 形参形参回传给实参回传给实参，实参实参和和 形参同步形参同步发生改变发生改变 【例例1- -3】设计一个算法：求一元二次方程设计一个算法：求一元二次方程ax2+bx+c=0的的根。根。 描述算法示例描述算法示例 算法可以采用自然语言、流程图或者表格算法可以采用自然语言、流程图或者表格方式等方式等来来描述。描述。 但是但是，一个学习计算机的学生一个学习计算机的学生应该使用某种计算机应该使用某种计算机语言来描语言来描 述述算法。本

8、课程采用算法。本课程采用C/C+语言描述算法。语言描述算法。 C+的作用是在描述算法时使用其提供的引用类型！的作用是在描述算法时使用其提供的引用类型！ int solution(float a，float b，float c， float d=b*b-4*a*c; if (d0) x1=(-b+sqrt(d)/(2*a); x2=(-b-sqrt(d)/(2*a); return 2; /2个实根个实根 else if (d=0) x1=(-b)/(2*a); return 1;/1个实根个实根 else/d0的情况的情况 return 0;/不存在实根不存在实根 用用C/C+描述如下：描述如下： solution 输入：输入：a b c 输出：输出： 根个数根个数 x1x2 算法框架：算法框架： 本讲完本讲完