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

前言

考试还剩十一天，现在准备开始复习这门课了。好像全是大题。

考试占比百分之五十，之前的课题占三十分，实验十五分，平时成绩五分。我感觉我课题给自己算二十五分，实验是 87*0.15=13 分，平时我都去上课了，没缺勤，算五分，这儿有四十三分了。所以这门课应该还是很容易过的。这次我的目标是想稍微考高点儿。

我记得之前在 csdn 上面看到过之前的回忆的期末题，但是不记得关键字是啥了，之后要是找到了会贴在评论区。有时候有些东西确实没记录或者收藏下来，真就找不到了，“记住什么，这辈子就有什么”，哈哈哈。

第一个题型是对算法的理解。随机类算法，回溯算法，动态规划算法，背后的原理和数学机理，数学机理我感觉是被生造的词哈哈哈。十分。今天就先复习这个题型。

感觉还是优先看课件吧，教材太学术，太新了，我喜欢旧一点的东西，那些时间给我带来确认和归属感。太新的东西给我一种不安全感。

回溯和动态规划好说，课件第四章和第五章是专门讲这两个算法的。随机类算法是啥呢？

查了一下，就是第七章的概率算法，包括随机算法，遗传算法，模拟退火算法，人工神经网络。模拟退火算法之前做过一次实验，虽然是直接理解这个源代码的。湘潭大学软件工程算法设计与分析实验-模拟退火算法

随机类（第七章）

在这里复习第一个题型，主要是复习基本的原理，那么应该能大概知道就行了。什么时间复杂度，空间复杂度，具体的代码实现，这个题型应该都不用管。当然在复习这个的时候把这些全弄清楚肯定好一些，就是太累了一点。

每个小节一二十页课件，其实还好。

想起来有个朋友说，他准备把学习通上面的网课全部看一遍，非常谨慎，我在考虑我要不要也看一遍，但是我看一遍可能也没啥用，可能看不懂，纠结。

随机

概述

随机算法可能以较小的概率出错，我感觉差不多了，感觉大概率正确在很多场景下都够用了，只有一些不容出错的场景不太适用，比如说什么导弹发射，医院电力控制（不能断电，断电了呼吸机啥的医疗仪器不能用了，出问题了就）

小概率事件在我的生活中发生的确实挺少的，比如买彩票七个数字我一般一个数字都不中。

概述只是一个大概的了解，应该不会考。

数值随机化

线性同余算法的公式是这样的

哈哈会不会就是考这个，之前数据结构就是考第一个函数二分函数，估计是想把难度降低一些。算法考试会不会刻意把难度降低一些呢？

具体的代码我暂时不看，主要是看不懂。

用这种面积或者求积分算面积，然后尝试足够多次，要是印象没出错的话，这应该就是几何概型求概率，算面积的比值就好了。比较简单。

再后面的好像是古典概型。好像不是，是抽取随机数字，但是这个随机数字之前不能被抽到过。

这里是说从 n 个元素里面抽取 m 个元素，我理解的没错的话，m 比较大，超过所有元素的一半的时候就把一些元素直接舍弃掉，也就是不一个一个抽取，舍弃掉之后直接全选。

彻底理解位运算——左移、右移：简单来说就是，左移就是乘，右移就是除，2 的某次方。这个我用的比较少，差点忘了。每次写代码的时候担心写错，我每次都是直接写除以 2 ，而不是写 >>1 ，我还是太谨慎了。这里的代码感觉就是用了一个生成随机数函数，其他的都比较直观。

舍伍德

课件里面这块应该是说 O(n^2) ，应该是格式问题没有正确显示。

好像不看代码完全理解不了算法的意思。前面的数值随机化可能也还要看代码重新理解一下。

消除最坏情形行为和特定实例之间的关联性，这句话不知道是啥意思。xtu oj 聚会：这里代码前面有一个快速排序模板，我没看明白这快速排序和舍伍德之间的关系是啥。

后面的也看不懂。

拉斯维加斯

拉斯维加斯算法有可能找不到解，所以使用倔强算法，我感觉就是用一种方法做不到一件事情的时候，再坚持坚持，倔强倔强。还不行可能就真不行了哈哈。

倔强算法就是只要没有找到需要的解，就一直用原来的算法继续寻找。

拉斯维加斯解决 n 后问题比较暴力，感觉比较难找到需要的解，太随机了。直接生成答案，我感觉难度就相当于在键盘上随便敲，没有逻辑地敲出世界名著的几百万字的这种难度。

回忆一下什么是 n 后问题，就是每一行，每一列，每条斜线都只能有一个皇后。

蒙特卡罗

建议读者主要还是看课件复习，看我的博客还是图一乐，该博客主要是一个陪伴作用，让读者知道有人也在努力地准备这个期末考试。因为博客里面会加入一些我的个人理解，然后会损失一些课件里面的重要信息。

所以就是所有的随机算法调用的次数越多，重复的次数越多，效果越好。

偏真算法：我感觉就是，假设我和朋友在核对一次测试的答案，我和朋友说这个题的答案我很确定是这个，那这个答案基本就是这个，假设我说不确定这个答案是这个，那么这个题答案可能是我写的答案，也可能不是这个，也就是课件里面的“有可能产生错误的解”。关键在于我能不能正确判断自己对答案的掌握程度。

主元素就是一个数组里面出现次数超过一半的元素。随机算法比顺序算法更好的一点就是有可能更快找到答案。顺序找可能要全部遍历一遍才能找到答案。随机算法可能一次就找到答案了。

后面的都看不懂，应该是废了。

下面的内容明天继续复习。

模拟退火

遗传

人工神经网络

回溯（第五章）

动态规划（第四章）

后记

这个我会每天更新，一直到 26 号晚上 22:00， 每天 22:00 更新一篇，记录自己这一天的复习过程哈哈哈。最后使尽全力还是 60 出头，70 出头就有点无奈了。哎。

今天复习的内容有点少了，感觉把课件完整看一遍都是问题了。还要做人机交互实验，争取下周五把人机交互实验做完。

原文地址：https://blog.csdn.net/L3102250566/article/details/143758733

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！