《(1.3.1)--1.3算法及其描述.ppt》由会员分享，可在线阅读，更多相关《(1.3.1)--1.3算法及其描述.ppt（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第 三 讲：算法及其描述数据结构与算法数据结构与算法2&算法算法（Algorithm)Algorithm)是描述计算机解决给定问题的操作过程（解题方是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令法），即为解决某一特定问题而由若干条指令组成的组成的有穷序列有穷序列。ontents1.3 算法及其描述算法及其描述程序设计的实质是对实际问题选择一个好的数据程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。大程度上取决于描述实际问题的数据结构。3（1
2、1）有穷性）有穷性-一个算法在执行了有穷步后一定要一个算法在执行了有穷步后一定要终止终止。（2 2）确定性（无二义）确定性（无二义）-算法的每一步操作都必须有确切定义，算法的每一步操作都必须有确切定义，不得有任何歧义性不得有任何歧义性。ontents算法的五个重要特性：算法的五个重要特性：算法的概念和描述算法的概念和描述（3 3）可行性）可行性-算法的每一步操作都必须是算法的每一步操作都必须是可行可行的，即每的，即每步操作均能在有限时间内完成。步操作均能在有限时间内完成。（4 4）输入数据）输入数据-一个算法有一个算法有n n（n=0)n=0)个初始数据的个初始数据的输入输入。（5 5）输出数
3、据）输出数据-一个算法有一个算法有一个或多个一个或多个与输入有某种关与输入有某种关系的有效信息的系的有效信息的输出输出。思考：算法与程序有何区别？思考：算法与程序有何区别？【例（补充）】考虑下列两段描述，这两段描述均不能满足算法的特性，试问它们违反了哪些特性？其中有一个死循环，违反了算法的有穷性特性。（1）描述一4/16其中包含除零错误，违其中包含除零错误，违反了算法的反了算法的可行性可行性特性特性（2）描述二5/166 （1 1）正确性）正确性（2 2）可读性）可读性 要求算法可读性好，要求算法可读性好，易于理解，易于编码，易于调试。（3 3）健壮性）健壮性（4 4）效率与低存储量要求）效率
4、与低存储量要求 执行算法所耗费的时间（高效率高效率）。执行算法所耗费的存储空间（主要考虑辅存空间；低存储低存储要求）。ontents算法设计的目标：算法设计的目标：算法的简单分析：算法的简单分析：7 描述描述-可采用自然语言、数学语言或约定的符号语言、伪代码、流程图等。计算机相关专业学生计算机相关专业学生应该熟练使用计算机语言来描述算法。本课的描述本课的描述-采用类C语言。ontents算法的描述和实现：算法的描述和实现：算法的概念和描述算法的概念和描述8算法设计的一般步骤：算法设计的一般步骤：1）分析算法的功能。）分析算法的功能。2）确定算法有哪些）确定算法有哪些输入输入，将这些输入设计成，
5、将这些输入设计成输入型参数输入型参数；确定算法有哪些确定算法有哪些输出输出，将这些输出设计成，将这些输出设计成输出型参数输出型参数。3）设计函数体完成从输入到输出的操作过程）设计函数体完成从输入到输出的操作过程。算法算法输入输入输出输出ontents返回值类型返回值类型 算法对应的函数名(形参列表形参列表)/实现由输入参数到输出参数的操作函数体返回值返回值：通常为int型或bool类型，表示算法是否成功执行。形参列表形参列表：由输入型参数和输出型参数构成。算法输入算法输出算法的算法的描述的一般格式：描述的一般格式：ontents10输出型参数的设计：输出型参数的设计：ontents示例：设计一
6、个交换两个整数的算法。void swap1(int x，int y)int tmp;tmp=x;x=y;y=tmp;当执行语句swap1(a，b)时，a和b实参值不会发生了交换。分析：x、y既是输入型参数，也是输出型参数 改正方法1：采用指针的方式来回传形参的值，需将上述函数改为：上述函数的调用改为swap2(&a，&b)void swap2(int*x，int*y)int tmp;tmp=*x;/将x的值放在tmp中 *x=*y;/将x所指的值改为*y *y=tmp；/将y所指的值改为tmp 交换形参x和y所指向的值11/16输出型参数的设计：输出型参数的设计：ontentsvoid swa
7、p(int&x，int&y)/形参前的“&”符号不是指针运算符 int tmp=x;x=y;y=tmp;改正方法2：采用引用型形参 将输出型形参改为引用类型。当执行语句swap(a，b)时，形、实参的匹配相当于：int&x=a;/a为x的引用int&y=b;/b为y的引用这样，a与x共享存储空间、b与y共享存储空间，因此执行函数后a和b的值发生了交换 简单明了。交换形参x和y的值12/16输出型参数的设计：输出型参数的设计：ontents13 例例 假设8枚金币中有一枚是伪造的一枚是伪造的，真假金币的区别仅仅是重量不同重量不同，现只有一个没有砝码的天平一个没有砝码的天平做工具，则至少用几至少用
8、几次次比较即可找出这枚伪造伪造的金币。要求用文字写出比较的算法。(提示：参考折半查找法即二分法)【解答：】先任选4枚金币,每边各2枚置于天平上,若天平平衡，则说明伪造的金币在另外4枚中；若不平衡，则说明伪造的金币在选择的4枚中，于是1 1次比较可以确定伪造的金币在哪次比较可以确定伪造的金币在哪4 4枚中枚中；自然语言描述算法举例自然语言描述算法举例ontents算法的概念和描述算法的概念和描述14 例例 假设8枚金币中有一枚是伪造的一枚是伪造的，真假金币的区别仅仅是重量不同重量不同，现只有一个没有砝码的天平一个没有砝码的天平做工具，则至少用几至少用几次次比较即可找出这枚伪造伪造的金币。要求用文
9、字写出比较的算法。(提示：参考折半查找法即二分法)【解答：】然后在含伪造的金币的4枚中，任选2枚金币，每边各1枚置于天平上，若天平平衡，则说明伪造的金币在另外2枚中，若不平衡，则说明伪造的金币在选择的2枚中，于是2 2次比较次比较可以确定伪造的金币在哪可以确定伪造的金币在哪2 2枚中枚中；最后在含伪造的金币的2枚中，任选1枚金币与其他1枚真币置于天平上，若不平衡，则选择的这枚是伪造的，否则余下的1枚是伪造的。因此3 3次比较即可找出伪造的金币次比较即可找出伪造的金币。自然语言描述算法举例自然语言描述算法举例ontents算法的概念和描述算法的概念和描述思考题15 在用在用C/C+语言语言描述算法时，输入型参数和输出型参数如描述算法时，输入型参数和输出型参数如何设计？何设计？设计一个算法：求一元二次方程设计一个算法：求一元二次方程ax2+bx+c=0的根。的根。