pascal算法-比2.doc

第3章 算法与程序设计模块 3.1 算 法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 常用的算法：列举了穷举有哪些信誉好的足球投注网站、递归、回溯、递推、模拟、分治、贪心、深度优先有哪些信誉好的足球投注网站、广度优先有哪些信誉好的足球投注网站等几种较为常用的算法。对于这些必需的方法和思想，关键不在于学生能不能，而在于教师是否想到，是否有过关注，引发学生对系统方法和思想的思考，重视建立编程思想，强化编程习惯的培养。 3.1.1 算法的5个重要特性 1．有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。 2．确定性：算法中每一条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径。 3．可行性：一个算法是能行的。即算法中描述的操作是执行有限次运算来实现的。 4．输入：一个算法有零个或多个输入。 5．输出：一个算法有一个或多个输出。 3.1.2 算法设计的要求 通常设计一个“好”的算法，应考虑达到以下目标。 1．正确性：算法应当满足具体问题的需求。 2．可读性：算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解。 3．健壮性：当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果。 4．效率与低存储量需求。 效率指的是算法执行时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。低存储量需求指算法执行过程中所需要的最大存储空间。 3.1.3 算法分析 算法分析的任务是对设计出的每一个具体的算法，利用数学工具，讨论各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问题宜采用哪种算法。 算法的复杂度分时间复杂度和空间复杂度。时间复杂度是在运行算法时所耗费的时间为f(n)（即?n的函数）。空间复杂度是实现算法所占用的空间为g(n)（也为n的函数）。称O(f(n))和O(g(n))为该算法的复杂度。 3.1.4 程序设计 1．程序 程序是对所要解决的问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。 2．程序设计 程序设计就是设计、编制和调试程序的过程。程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计两个阶段。 除了好的程序设计方法和技术之外，程序设计风格也很重要。因为程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序结构清晰合理，使程序代码便于维护。因此，程序设计风格对保证程序的质量很重要。 一般来讲，程序设计风格是指编写程序时所表现出的特点、习惯和逻辑思路。程序是由人来编写的，为了测试和维护程序，往往还要阅读和跟踪程序，因此程序设计的风格总体而言应该强调简单和清晰，必须可以理解。可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。要形成良好的程序设计风格，主要应注重源程序文档化。 （1）符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序的功能进行理解。 （2）程序注释：正确的注释能够帮助读者理解程序。 3．结构化程序设计 结构化程序设计方法是程序设计的先进方法和工具。采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序语言仅使用顺序、选择和循环3种基本控制结构就足以表达出各种其他形式结构的程序设计方法。 总之，遵循结构化程序的设计原则，按结构化程序设计方法设计出的程序具有明显的优点。其一，程序结构良好、易读、易理解和易维护；其二，可以提高编程工作的效率，降低软件开发成本。  3.2 穷举有哪些信誉好的足球投注网站法 有一些问题一时难以找到规律或者公式，或者根本没有规律、公式。这时可以利用计算机高速运算的特点，使用穷举来解决。穷举有哪些信誉好的足球投注网站法是穷举所有可能情形，并从中找出符合要求的解决。穷举有哪些信誉好的足球投注网站法所有可能情形，最直观的是联系循环的算法。 例1 找出n个自然数（1,2,3,…,n）中r个数的组合。例如，当n=5，r=3时，所有组 合为： ? ?5 5 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2