软件设计师-19，下午题-算法设计与C语言实现

Joker2Yue2023-10-182023-10-18

程序设计语言、算法分析、算法分类、解题技巧、真题讲解

NULL

数据成分：指的是一种程序设计语言的数据和数据类型。数据可分为常量（在程序运行时不可改变）、变量（在程序运行时可以改变）、全局变量（其存储空间在静态数据区分配）、局部变量（其存储空间在堆栈区分配）。数据类型包括整型、字符型、双精度、单精度浮点型、布尔型等。
运算成分：指明了允许使用的运算符号及运算规则。这包括算术运算、逻辑运算、关系运算、位运算等。
控制成分：指明了语言允许表达的控制结构。这包括顺序结构、选择结构和循环结构（包括初始化、循环体和循环条件）。
传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。

函数：C程序由一个或多个函数组成，每个函数都一个名字，其中有且仅有一个名字为main的函数作为程序运行时的起点。函数是程序模块的主要成分，是一段具有独立功能的程序。函数使用涉及三个概念：函数定义、函数声明（先声明后使用）、函数调用。
传值调用：将实参的值传递给形参，形参的改变不会导致调用点所传的实参的值改变。实参可以是合法的变量、常量和表达式。
传址调用：即引用调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值。实参不能为常量，只能是合法的变量和表达式。
因此，在编程时，要改变参数值，就传址，不改变，就传值。

上述的时间复杂度，经常考到，需要注意的是，时间复杂度是一个大概的规模表示，一般以循环次数表示，O(n)说明执行时间是n的正比，另外，log对数的时间复杂度一般在查找二叉树的算法中出现。渐进符号表示个渐进变化程度。实际变化必须小于等于O括号内的渐进变化程度。

递归：指的是子程序（函数）直接调用自身或通过一系列调用语句间接调用自身，是一种常用于描述问题和解决问题的方法。
- 递归的两个基本要素：边界条件（确定递归何时终止，即递归出口）和递归模式（将大问题如何分解成小问题，即递归体）。
- 示例：阶乘的定义
分治法：对于一个规模为n的问题，若该问题可以容易地解决，则直接解决；否则，将其分解为k个规模较小的子问题。这些子问题互相独立且与原问题形式相同，然后递归地解决这些子问题，最后将各子问题的解合并以得到原问题的解。
- 步骤：分解（将原问题分解成一系列子问题）→ 逐一求解（递归地求解各子问题，若子问题足够小，则直接求解）→ 合并（将子问题的解合并成原问题的解）。
- 凡是涉及到问题分解和解决的情况都可以考虑使用分治法，例如二分查找、归并排序等。

回溯法：被称为“通用的解题方法”，它可以系统地搜索一个问题的所有解或找到任何一个解。在问题的解空间树中，采用深度优先策略，从根节点开始搜索解空间树。当到达任一节点时，首先判断是否可以确定该节点不包含问题的解，如果不包含，就跳过对以该节点为根的子树的搜索，然后逐层向其祖先节点进行回溯；否则，进入该子树，继续采用深度优先策略进行搜索。
可以理解为首先进行深度优先搜索，一直向下探索，当遇到死路时，返回上一层继续探索其他分支。这就是回溯的含义，即一直向前尝试，当不成功时再返回上一层。
回溯法通常用于解决类似迷宫问题的情况，其中需要在一个复杂的空间中寻找路径或解决方案。

动态规划法：在问题求解中，对于每一步决策，列出各种可能的局部解，然后基于某种判定条件，剔除那些明显不可能得到最优解的局部解。通过每一步都经过筛选，以确保每一步都是最优解，从而保证全局是最优解。

这方法本质上是将复杂的问题划分成一个个子问题，不同于分治法的是，这些子问题之间不是相互独立的，也不一定都相同。它通常用于解决具有最优性质的问题，它会投入大量精力在前期构建一个表格上，其中存储了对每一步列出的各种可能答案。最终，在需要得出结果时，可以通过查询这个表格来获取。
动态规划法的特点是，它不仅保证每一步是最优的，而且全局也是最优的。

贪心法：贪心算法总是在当前情况下做出看似最优的选择，而不考虑整体的影响。每一步的选择只是局部最优，但并不一定是整体最优的选择。由于贪心算法不需要穷尽所有可能的解，所以它的计算时间相对较短，通常可以快速得到令人满意的解，但不能保证获得最优解。
局部贪心算法只关注当前步骤的最优选择，而不考虑整体的情况。要判断这类算法是否有效，需要看每一步是否都选择了最优解，并且整体问题没有透露出最终结果是最优的。

算法设计是软件设计中最具挑战的部分之一，主要困难在于填写C代码空白部分。因此，建议先不着急解决代码填空题（因为它们最难），而是先解决其他周边问题，如时间复杂度、算法技巧和计算特殊值的结果。最后再着手解决代码填空，这样有助于全面理解整个题目。以下是一些技巧：

代码填空：将第一个小题作为最后解决的部分，因为它不会影响其他题目的解决。要理解题目中算法的原理，才能得出答案。此外，近年来的算法设计真题中有许多技巧，即使不理解算法原理，也可以推导出答案。要结合算法描述中的公式以及代码中类似的分支条件，可以发现填空的答案已经在代码中的某个位置给出，因为算法原理的相似性可以通用，特别是分治法算法。

需要注意的是，当涉及到与最小值或最大值的比较时，如果比较结果更小，接下来肯定要更新最小值及其对应的下标元素的值。当遇到一些条件判断的填空时，要注意查看上下文，确定哪些变量是作为控制条件的。
算法和时间复杂度：将第二个小题先做，这样可以很好地区分不同的算法类型。涉及到分组的通常是分治法，局部最优解是贪心法，整体最优规划是动态规划法，而迷宫类问题则是回溯法。记住关键字有助于进行区分。时间复杂度可以通过观察C代码中的for循环层数和每层循环的次数来判断，涉及到二分法的通常是O(logn)。
计算特殊值：将第三个小题先做，不需要依赖C代码，直接根据题目给出的算法原理逐步推导即可得出答案，耐心推导并不难。但要注意，如果算法原理非常复杂，建议放弃，掌握问题1和2的技巧即可。