程序设计实习（田永鸿)清华大学

### 知识点总结：《程序设计实习》与动态规划 #### 清华大学课程《程序设计实习》概览 《程序设计实习》是清华大学开设的一门计算机科学基础课程，由田永鸿教授主讲。该课程聚焦于程序设计的核心技能，特别是针对ACM竞赛的准备，深入讲解C语言编程技巧以及算法分析。课程资源丰富，包括了大量实用的实例讲解，旨在提升学生的编程能力和解决复杂问题的能力。 #### 动态规划：问题解决利器 动态规划是一种强大的算法策略，用于解决具有重叠子问题和最优子结构特征的问题。它通过存储子问题的解来避免重复计算，从而大幅度提高效率。本课程中，动态规划被引入作为解决问题的关键技术之一，尤其在处理复杂算法问题时显得尤为重要。 #### 搜索策略：深度优先与广度优先 - **深度优先搜索（DFS）**：一种先探索尽可能深的搜索树路径，然后再回退的搜索策略。适用于节省存储空间，尤其是在空间受限的环境中。 - **广度优先搜索（BFS）**：从根节点开始，一层一层地遍历整个图的节点。这种方法对于寻找最短路径问题非常有效，但可能需要更多的内存空间。 #### 八数码问题与木棒问题 - **八数码问题**：一个经典的滑动谜题，通过移动空格到不同位置来将打乱的数字恢复到正确排序。课程中讨论了如何使用不同的搜索策略（如BFS vs DFS）来优化解决方案，同时提出了节省存储空间和加速搜索的方法，例如使用A*算法、双向BFS、HASH映射和并行算法等。 - **木棒问题**：涉及到分割给定长度的木棒，以满足特定条件下的需求。课程中介绍了基于DFS的算法，并探讨了如何构建基于BFS的算法来解决这一问题。具体策略包括枚举所有可能的分割方式，以及基于木棒总数的奇偶性进行递归处理，形成平衡的二叉树结构，以达到优化解决方案的目的。 #### 为什么选择动态规划？ 动态规划之所以成为解决复杂问题的首选策略，主要是因为传统搜索算法（如BFS和DFS）在处理具有重复子问题的场景时存在冗余计算的问题。动态规划通过记忆化存储机制，避免了不必要的重复计算，显著提高了算法的效率。以Fibonacci数列求解为例，传统的递归方法会导致大量的重复计算，而采用动态规划则可以有效地存储和复用中间结果，极大地提升了计算速度。 #### 结论 《程序设计实习》课程不仅提供了C语言编程的基础知识，还深入探讨了算法设计和优化策略，尤其是动态规划的理论与应用。通过对八数码问题和木棒问题的实例分析，学生能够深刻理解搜索策略和动态规划在实际问题解决中的重要作用，为将来从事软件开发、算法研究或参加ACM竞赛打下坚实的基础。