这学期的考试我就没出现过写不完的情况，然而事情就的的确确发生在我头上了。算法考试题基本上都是策略分析题，总共加起来得有两千多字了。

基本概念

算法是由若干条指令组成的序列，且满足有输入、输出、可行性、有穷性和确定性五个特性。

评价算法的主要标准是算法实现的时间，算法实现的存储空间和代码要易于理解。

贪心法，分治法，和动态规划法的区别和联系：
分治法与动态规划都是将问题分解成若干个较小规模的子问题。而分治法是将原问题分解为多个子问题，通过计算出子问题的结果构造出最优解，分治法分解后的子问题被看成是相互独立的。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互有联系。贪心算法是依赖于当前已经做出的选择，采用自顶向下的解决方法。具体分析请看这里：贪心法，分治法，和动态规划法。

算法分析

开灯问题

有n盏灯，编号为1~n，每个灯有个开关，按一下打开，再按一下关闭，再按一下打开。第1个人把所有灯打开，第2个人按下编号为2的倍数的灯的开关，第3个人按下编号为3的倍数的灯的开关，依此类推，一共有k个人，问最后有哪些灯开着？输入n和k，输出开着的灯的编号。k<=n<=1000。

将灯的状态存入一维数组中，设灯亮的状态为1，第一层循环为从第1个人到第k个人(i代表第几个人)，第二层循环为在所有的n盏灯中（j代表第几盏灯），当第i个人按i的倍数的开关时，即灯的编号能整除i，此时灯的状态取反。代码如下：

for(int i=1;i<=k;i++)
	for(int j=1;j<=n;j++)
		if(j%i==0)
			a[j]=!a[j];

可以优化第二层循环，不用判断，直接修改数组值。

for(int i=2;i<=k;i++)
	for(int j=i;j<=n;j+=i)
		a[j]=!a[j];

最后遍历输出值为1的数组下标即可。更多讨论请看这里开灯问题。

博弈问题

给定N（N>20) 张牌，两个人轮流取牌，每人每次最少取 1 张牌，最多取 5 张牌。我们判定取完最后一张牌的人输。请你给出两人的最佳博弈方法。

考试之前以为不知道有多难呢，结果下来一看解析，哦豁，懂了。

思路：
首先N=1+4=5

（54-1）/5=10余3

故先拿牌者取3张即可稳保胜利。

操作如下：

先手拿三张后，执行如下原则：

玩家拿1张，先手拿4张；

玩家拿2张，先手拿3张；

玩家拿3张，先手拿2张；

玩家拿4张，先手拿1张；

就是保持每轮双方一共拿走5张牌，这样先手最后一次取牌后扑克牌就只剩一张，玩家必输。

要保证每轮拿牌总数在自己控制之内，所以每轮拿5张牌，对方拿N张，则自己拿5-N张，十轮可以拿50张牌，所以问题相当于，一共54-50=4张牌，自己先拿，要给对方省一张牌，所以第一次自己拿3张，以后每次都拿5-N张，其中N为对方拿牌数，1 <= n <= 4。
代码参考此博客。

4色图问题

4色地图问题的优化求解算法可由( )设计实现

N皇后问题

12银币问题

给余猜数问题

有一堆苹果，3 个 3 个地数，最后余 2 个；5 个 5 个地数，最后余 3 个；7 个 7 个地数，最后余 4 个。
问这堆苹果最少有多少个。

约瑟夫环问题

残缺棋盘问题

算法优劣问题

算法设计

分治法求最值

走格子问题

考试小结

我做算法题竟然做出了当年语文考试的样子，最后时刻快交卷了，我还有好多策略原理题没写（别问为什么不写代码，问就是不会），就开始狂草起来，那速度，没得说，那字，估计也没得看，想的啥就写啥，跟语文考试写作文写不完的时候一模（mu）一样，就离谱。哎呀，我裂开了呀。最后还是没写完！

其实还是知识点掌握的不够牢固。