湘潭大学软件工程算法设计与分析考试复习笔记（四）

回顾

• 湘潭大学软件工程算法设计与分析考试复习笔记（一）
• 湘潭大学软件工程算法设计与分析考试复习笔记（二）
• 湘潭大学软件工程算法设计与分析考试复习笔记（三）

前言

现在是晚上十一点，我平时是十一点睡觉的，但是今天确实一天都没有复习这个，我还是想复习一下。所以还是复习一下吧。

现在复习的是程序填空，一空四分，四十分，也就是说十个空。这个这么难，好像老师是说看大家造化了哈哈哈。

第三道大题是算法设计与分析，前面三篇笔记是复习了一下第一道大题，也就是对算法的大概的理解。第三道大题主要是分治法，解决实际问题（上台阶，电梯），分析时间复杂度，求一个序列中特殊性质的元素，数塔求最大的，最小的和，最优路径，tsp 问题，（这个之前不知道是啥问题，现在大概知道了一些，就是图论题）

10+40+xx+15=100

好吧。那就是这样子了，考试重点就是这些了。现在开始复习程序填空。

计划

有个朋友和我说，她先看课件，然后最后再复习程序填空，先有一个框架，感觉确实是这样，那我也先复习后面的那个算法设计比较好。程序填空确实范围比较大。还有一点就是课件上面的代码我得下载下来才能复制里面的内容，之后方便的时候再操作一下。

分治

前面老师画的重点有提到分治解决各种问题，分治，我现在不看课件对这个概念的理解比较浅显：就是把一个比较复杂的问题分解成为很多子问题，一步一步划分，直到划分到我们能够处理，好像听起来很简单，在现实生活中其实非常非常难，因为我们是有感情的人类，我们在分解任务的时候会有情绪，然后会因为各种各样的原因做不到。

概述

有八个小节，容量上面还是比较多的。课件是第二章，我们前面大致复习了一下 4 5 7 这三个章节。复习完第二章，就算真正的复习完一半了，今天是周三，离考试不到一周的时间了。另外有个朋友联系我让我发一些资料给他，哈哈哈，其实我也没有什么资料，和他一样也是慌的一批地准备期末考试，但是就算害怕也要装作无所谓的样子。

递归

按照我的理解就是，最开始给定的 n 是不能直接解决的问题，比如说一开始让造一个火箭，递归就是问能不能造一个火箭头，不能，然后能不能造个啥，不能，…，最后问，能不能帮忙拧一下这个螺丝钉？可以，那就是所谓的递归出口。

递归形式

• 多变元递归
• 多步递归
• 嵌套递归
• 联立递归

上面这些一个都看不懂，好像也不会考。考应该是考怎么解决实际问题，时间复杂度是多少。看这种复杂的东西真的看不进去。

实例

这页课件有朋友在很早之前就问过我，可惜我看不懂。

常数和系数没搞懂，指数那块感觉是这样推导的。

递归小结

递归的时间复杂度可以看到是指数级别的，在很多情况下都是不可接受的。或者说比较难。

分治基本思想

我就一直感觉什么分治，递归，贪心，动态规划，都很像，它不像那些复杂的数据结构或者图论，完全是一些看不懂的代码，这几个更像是一种内功，就是表现出来非常朴素，但是里面蕴含的思想是非常深刻的。

只看的懂这个，就是画一棵二叉树，根节点是 n-m ，往下一层全是 n-m-1 ，再往下一层全是 n-m-2 ，一直画下去，最后减小到 1 ，分治结束，从 1 到 n-m 一共有 n-m 层，又因为是二叉树，所以时间复杂度是 O(2^(n-m))

棋盘覆盖问题

这个是很经典的递归的问题，很明显我是一直没有学会的那一批，被这种题折磨得痛苦不堪，其实也还好，因为下意识远离这个题了，没有直面它，之前问过老师这个题，给我发了很多条信息，我似懂非懂。oj 或者网上的刷题网站有很多变体，什么贴瓷砖之类的。

后记

复习到这儿，明天再继续复习。