【期末复习】计算机算法设计与分析-Toy模板网

这篇具有很好参考价值的文章主要介绍了【期末复习】计算机算法设计与分析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

小编相信大家都很急切，要如何短时间学会算法通过考试呢？下面就让楼主带大家一起了解吧。

算法期末考试，其实就是算法期末考试了。那么小编为什么会算法期末考试，相信大家都很好奇是怎么回事。大家可能会感到很惊讶，小编怎么会算法期末考试呢？但事实就是这样，楼主也感到非常惊讶。那么这就是关于算法期末考试的事情了，大家有没有觉得很神奇呢？

看了今天的内容，大家有什么想法呢？欢迎在评论区告诉楼主一起讨论哦。

【考试内容】

概念题：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为数组起点下标0，r为数组终点下标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;
}