计算机算法设计与分析：步骤、定义、要素、质量指标和常用算法

算法设计与分析期末试题 算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。算法具有以下五个属性：有穷性、确定性、可行性、输入和输出。算法设计的质量指标包括正确性、可读性、健壮性、效率与存储量需求。 算法设计的步骤包括：问题分析、数学模型建立、算法设计与选择、算法指标、算法分析、算法实现、程序调试、结果整理文档编制。 算法的三要素是操作、控制结构和数据结构。常见的算法有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法等。 迭代法是一种不断用变量的旧值递推出新值的解决问题的方法。迭代法需要确定迭代模型、建立迭代关系式、对迭代过程进行控制。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 在编写迭代程序时，需要考虑迭代过程的控制，不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。 例如，编写计算斐波那契（Fibonacci）数列的第n项函数fib（n），可以使用迭代法来实现。斐波那契数列是一个经典的算法问题，它的定义是：fib（1）=fib（2）=1，fib（n）=fib（n-1）+fib（n-2）（n>=3）。使用迭代法，可以编写出以下函数： ``` function fib(n) { if (n == 1 || n == 2) { return 1; } else { return fib(n-1) + fib(n-2); } } ``` 这个函数使用了递归的方法来计算斐波那契数列的第n项，但是这种方法存在效率问题，因为它会重复计算同一个值多次。可以使用迭代法来改进这个函数，例如： ``` function fib(n) { var a = 1, b = 1; for (var i = 3; i <= n; i++) { var temp = a + b; a = b; b = temp; } return b; } ``` 这个函数使用了迭代法来计算斐波那契数列的第n项，效率比之前的递归方法高很多。 算法设计与分析是计算机科学的核心内容，掌握了算法设计与分析的方法和技术，对于解决实际问题、提高计算效率和降低存储需求具有重要意义。