Theme NexT works best with JavaScript enabled

人生若只如初见

📢📢📢:博主开学了!封闭中!

算法期末试卷总结

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

基本概念

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

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

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

算法分析

开灯问题

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

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

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

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

1
2
3
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)一样,就离谱。哎呀,我裂开了呀。最后还是没写完!

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

-------------------- ⭐本文结束⭐ --------------------