【期末复习】计算机算法设计与分析
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
小编相信大家都很急切要如何短时间学会算法通过考试呢下面就让楼主带大家一起了解吧。
算法期末考试其实就是算法期末考试了。那么小编为什么会算法期末考试相信大家都很好奇是怎么回事。大家可能会感到很惊讶小编怎么会算法期末考试呢但事实就是这样楼主也感到非常惊讶。那么这就是关于算法期末考试的事情了大家有没有觉得很神奇呢
看了今天的内容大家有什么想法呢欢迎在评论区告诉楼主一起讨论哦。
【考试内容】
概念题1~6章
编程题2~5章
参考文献《计算机算法设计与分析第五版》王晓东 著
【概念题】
{ 期中考涉及内容期末再考可能不大 }
算法是指解决问题的一种方法或一个过程是由若干条指令组成的有穷序列满足四个性质
①输入有零个或多个输入
②输出产生至少一个结果
③确定性每条指令清晰无歧义
④有限性每条指令执行次数、执行时间有限。
通常只考虑三种情况下的时间复杂性即最好情况下、最坏情况下以及平均情况下的时间复杂性。实践表明可操作性最好且最有实用价值的是 最坏情况下 下的时间复杂性。
动态规划算法的基本要素是最优子结构和重叠子问题性质。
以及若干读代码判断时间复杂度的题这个期末再考可能性很大
{ 书上一些概念型语句 }
递归的概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
分治法的基本思想
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题这些子问题互相独立且与原问题相同。递归地解这些子问题然后将各子问题的解合并得到原问题的解。
动态规划算法
动态规划算法与分治法类似其基本思想是将待求解问题分解成若干子问题先求解子问题再结合这些子问题的解得到原问题的解。与分治法不同的是适合用动态规划法求解的问题经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题则分解得到的子问题数目太多以致最后解决原问题需要耗费指数级时间。
动态规划算法适用于解最优化问题通常可按以下 4 个步骤设计
① 找出最优解的性质并刻画其结构特征
② 递归地定义最优值
③ 以自底向上的方式计算最优值
④根据计算最优值时得到的信息构造最优解。
贪心算法
顾名思义贪心算法总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑所做的选择只是在某种意义上的局部最优选择。当然我们希望贪心算法得到的最终结果也是整体最优的。
回溯法深度优先搜索DFS
回溯法有 “通用的解题法”之称可以系统地搜索一个问题的所有解或任一解它是一个既带有系统性又带有跳跃性的搜索算法。
分支限界法广度优先搜索BFS
{ 第六章不考编程故选择可能会涉及 }
分支限界法类似回溯法也是在问题的解空问上搜索问题解的算法。一般情况下分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有解而分支限界法的求解目标是找出满足约束条件的一个解或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。
【编程题】
[ 二分搜索 ]
这个必须会
这里直接上代码没什么好说的。
题目在递增数组a中查找x元素。
#include <iostream>
using namespace std;
const int N = 110005;
int main() {
int n, a[N], x;
cin >> n;
for (int i=0; i<n; i++)
cin >> a[i];
cin >> x;
while (x != 0) //x为0退出循环
{
bool flag = 0; //x是否在a数组标志0不存在1存在
int left = 0; //查找区间左端
int right = n-1; //查找区间右端
while(left<=right)
{
int mid = (left+right)/2; //取中值
if(a[mid] == x)
{
flag = 1;
break; //若找到则退出循环
}
if(a[mid] > x)
right = mid-1; //中值大于目标值目标值在左半段
else
left = mid+1; //中值小于目标值目标值在右半段
}
if(flag == 0)
cout<<"no"<<'\n';
else
cout<<"yes"<<'\n';
cin >> x;
}
}进阶浮点数的二分查找涉及精度问题可去CSDN搜索 “PIE问题” 。
[ 合并排序 ]
思想将两个有序的数组合成一个有序的数组解决问题。
题目给定两递增数组a1和a2求两数组元素集合的中位数。
#include<iostream>
using namespace std;
const int N = 1e5;
int main(){
int n, a1[N], a2[N], a3[2*N]; //合并数组a3长度为a1和a2长度和
cin>>n;
for(int i=0;i<n;i++)
cin>>a1[i];
for(int i=0;i<n;i++)
cin>>a2[i];
int a,b,c;
a=0,b=0,c=0;
while(a<n && b<n) //a1和a2数组都没走完
{
if(a1[a]<a2[b]) //逐个比较a1和a2中元素大小依次取小的存入a3
{
a3[c]=a1[a];
c++;
a++;
}
else
{
a3[c]=a2[b];
c++;
b++;
}
}
//必定有一个数组会走完剩下数组里的数一定比a3数组里的数大
//将剩下数组的数放入a3数组
while(a<n){
a3[c]=a1[a];
c++;
a++;
}
while(b<n){
a3[c]=a2[b];
c++;
b++;
}
cout<<a3[(c-1)/2]<<'\n'; //最终c的值就为a3的数组长度
return 0;
}[ 快速排序 ]
书上的代码如下记忆。
//调用快排只需QuickSort(a,p,r)
//a为目的数组p为数组起点下标0r为数组终点下标n-1
void QuickSort(int a[], int p, int r)
{
if(p < r)
{
int q = Partition (a, p, r);
QuickSort(a, p, q-1);
QuickSort(a, q+1, r);
}
}
int Partition(int a[], int p, int r)
{
int i = p, j = r+1;
int x = a[p];
//x为主元
while(true)
{
while(a[++i]<x && i<r);
while(a[--j] > x);
if(i >= j)
break;
swap(a[i],a[j]);
}
a[p] = a[j];
a[j] = x;
return j;
}需要理解快排思想可去MOOC看北京航空航天大学的《算法设计与分析》
https://www.icourse163.org/course/BUAA-1449777166?tid=1463474515
课件 - 03分而治之篇II - 3.2快速排序 上
{ 期中考 } 查找第K小的数就是用的快排思想。
[ 动态规划 ]
必考题思想比较灵活建议是去刷网课然后自己做一遍。
课件 - 040506动态规划
[ 贪心算法 ]
有手就行考到就是赚到
[ 回溯法DFS ]
期末重难点但其实会了0-1背包就没问题了。
建议是抓个会的活人给你现场讲解带着写一下。
这里上一道去年的期末题
带书计划
【Description】
小明买到了他心仪的算法书。他打算带着这些书回家趁着假期好好学习一下算法。但是由于飞机上有行李重量的限制大块头的计算机书籍都很重。小明想尽可能用满行李重量的限额在不超过限额的前提下带的书越重越好。辛辛苦苦学了一学期算法的你能帮助小明找到最佳的解决方案吗告诉他可以带哪些书吗
【Input】
第一行2个整数分别代表飞机重量的限制b(0< b < 1000)、书的数量n(0 < n < 100)。 下面n行每行一个字符串和整数空格分隔代表每本书的名称和重量
【Output】
按书名的字典排序输出多行每行代表一本书。如果有多个答案输出字典序最小的答案。如果一本书都不能带输出-1
【Sample Input】
20 4
introduction_algorithm 13
algorithm_training 6
data_struct 15
beauty_of_math 4
【Sample Output 】
algorithm_training
introduction_algorithm
【Hint】
《introduction_algorithm》《algorithm_training》和《data_struct》《beauty_of_math》两种组合都可以获得最大值取字典序最小的按字典序输出。
题目难度还好关键在于字典序的输出需要会对结构体的排序。
代码如下
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1001;
int b,n,ans[N],cn,cv,Max;
vector<int> way;
struct node {
string name; //书名
int weight; //书重
}book[N]; //下标表示书号
bool cmp(node A, node B)
{
return A.name < B.name;
}
void Dfs(int t) //当前访问书的书号t
{
if(t>n) //当所有书籍都找完
{
if(cv > Max) //当前存放量cv大于所记录最大方案
{
Max = cv;
cn = way.size(); //总共拿了几本书cn
int i=0;
for(auto x:way)
{
ans[i] = x; //将拿到的书的序号存到ans数组
i++;
}
}
return;
}
if(cv+book[t].weight <= b) //cv+book[t].weight如果加入下本书不会超容量
{
cv += book[t].weight; //拿书
way.push_back(t); //记录拿的几号书
Dfs(t+1); //回溯
cv -= book[t].weight; //放回书
way.pop_back(); //删去放回的书的记录
}
Dfs(t+1); //当前t号书不拿考虑下一本
return;
}
int main()
{
cin>>b>>n; //输入最大容量b 书籍数目n
for(int i=1; i<=n; i++)
{
cin>>book[i].name>>book[i].weight;
}
sort(book+1,book+1+n,cmp); //将书籍按字典序排序
Dfs(1); //回溯法深度优先搜索
if(Max == 0) //最大方案为0即没有书籍
{
cout<<"-1"<<'\n';
}
else
{
for(int i=0; i<cn; i++) //输出各书号对应的书名
cout<<book[ans[i]].name<<'\n';
}
return 0;
}【结语】
相信自己算法期末有手就行