《问题求解与算法分析概述》由会员分享，可在线阅读，更多相关《问题求解与算法分析概述（24页珍藏版）》请在金锄头文库上搜索。
1、算法设计与问题求解北京交通大学计算机与信息技术学院 李清勇E-mail: Tel: 51688603 主校区: 9号楼 北312问题与问题实例（1）o问题是需要我们回答的一般性提问，通常含有若干参数 ，由求解任务描述，输入条件以及输出要求等要素组成。o问题实例则可以定义为确定问题描述参数后的一个对象 。一个问题的求解任务描述和输入条件通常包含若干参数，当给定这 些参数一组赋值后，则可以得到一个问题实例。一个问题可以包含 若干个问题实例，问题和问题实例的关系类似于面向对象程序设计 语言中类和类对象的关系。问题与问题实例（2）问题实例1：a=1,b=1； 问题实例2：a=1000,b=10000
2、。问题与问题实例（3）算法与程序算法是任何定义好了的计算程式，它取某些值或值的集 合作为输入，并产生某些值或值的集合作为输出。概括起 来，算法有以下五个特性： 确定性： 算法的每一种运算（包括判断）必须要有确切的定义，即每一种运算应 该执行何种动作必须是相当清楚的、无二义性的。 可实现性： 此性质是指算法中有待实现的运算都是相当基本的，每种运算至少在 原理上能由人用纸和笔在有限的时间内完成。 具有数据输入： 一个算法有零个或多个数据输入，它们是在算法开始之前对算法 最初赋予的量，这些输入取自特定的对象集合。 具有数据输出： 一个算法产生一个或多个输出，它们是同输入有某种特定关系的 量。 有穷性
3、： 一个算法总是在执行了有穷步之后终止。 程序是算法用某种程序设计语言的具体实现。程序可以不满 足算法的性质(5)即有穷性。 问题求解周期o问题简化 大多数实际问题涉及到的因素很多，在求解 之前必须经过简化，得到问题的原型；o模型构建 数学建模过程，非常灵活；o算法设计 用最适合计算机体系结构的方式进行求解；o程序设计与调试 用特定的程序设计语言实现算法。 从一个问题的提出，到计算机可执行的、满足准确性和复 杂性要求的程序算法的完成，可以看作是“问题求解”的 一个周期。问题求解周期包括问题简化，模型构建，算法 设计，程序设计与测试等过程。问题求解周期问题求解周期问题求解周期程序设计的盲点o在问
4、题求解时，程序设计者除了犯一些语法和语义 错误外，比如指针错误，数组下标越界，运算符优先 级混乱等；o常常出现一些跟问题领域和算法相关的错误，比如 忽视变量的取值范围，不正确理解浮点数的精度限制 ，无原则地使用递归调用。 程序设计的盲点long不够长把char 改为 long?程序设计的盲点long不够长long add（long a, long b） 1. long c = a + b; 2. return c; 程序设计的盲点long不够长数据是计算机加工处理的对象，为了存储和处理的需要，将数据划分为不同的类型，编 译程序为不同的类型分配不同大小的存储空间（存储单元的字节数），并且对各种数
5、据 类型规定了该类型能进行的运算（运算符集合）; 任何类型数据的值均被限制在一定的范围内，称为数据类型的值域（取值范围）。当一 个变量的数据类型确定以后，该变量的取值范围就随之确定。在程序运行时，如果该变 量的实际值超出了其数据类型的取值范围时，则会导致“溢出”。数据“溢出”虽然不 会导致编译错误，但是其运算结果却不再正确。程序设计的盲点long不够长程序设计的盲点double不够准void testDouble1（） 1.double a, b; 2.cout.precision（17）; 3.a = 1.234; 4.coutaendl; 5.a = 1.2345; 6.coutaendl
6、; 7.a = 1.123456789123456; 8.b = 1.000000000000000; 9.couta+bendl; 程序设计的盲点double不够准void testDouble2（） 1. if （1.123f + 1.345f = = 2.468f） 2. cout“It is true: 1.123f + 1.345f = = 2.468f rn“; 3. else 4. cout“It is false: 1.123f + 1.345f = = 2.468f rn“; 5. if （1.123f + 1.344f = = 2.467f） 6. cout“It is t
7、rue: 1.123f + 1.344f = = 2.467f rn“; 7. else 8. cout“It is false: 1.123f + 1.344f = = 2.467f rn“; “精确是偶然的、误差是必然的” 程序设计的盲点double不够准IEEE（Institute of Electrical and Electronics Engineers，电子电气工程师 协会）在I985年制定的IEEE 754二进制浮点运算规范，是浮点运算部 件事实上的工业标 准。一个实数R在IEEE 754标准中表示为：程序设计的盲点double不够准程序设计的盲点double不够准对于floa
8、t型，用32位二进制编码表示，具体如下： 最高位31位，保存符号位s，“0”表示正数，“1”表示负数。 30位23位，共8位，移码方式（指数值加上偏移量127）保存指数部分，称为阶码 。 22位0位，共23位，保存系数部分，称为尾数，对于规范化二进制数，整数位的 前导“1”不保存（隐含），直接保存小数部分f22.f1f0。对于double型，用64位二进制编码表示，具体如下： 最高位63位，保存符号位s，“0”表示正数，“1”表示负数。 62位52位，共11位，移码方式（指数值加上偏移量1023）保存指数部分，称为阶 码。 51位0位，共52位，保存系数部分，称为尾数，对于规范化二进制数，整数位的 前导“1”不保存（隐含），直接保存小数部分f51.f1f0。程序设计的盲点double不够准float型尾数部分表示的数：double型尾数部分表示的数：程序设计的盲点double不够准一个十进制数能否用二进制浮点数精确表示，关键在于小数部分。我们来看一个最简单的小数 0.1能否精确表示： 程序设计的盲点递归不够快直接或间接地调用自身的算法称为递归算法。用函数自身 给出定义的函数称为递归函数。程序设计的盲点递归不够快1.递归调用需要额外的时间和空间开销 ； 2.重复计算的子问题。思考题
