{ 書上一些概念型語句 }

遞歸的概念
直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。

分治法的基本思想
分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。

動(dòng)態(tài)規(guī)劃算法
動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想是將待求解問題分解成若干子問題，先求解子問題，再結(jié)合這些子問題的解得到原問題的解。與分治法不同的是，適合用動(dòng)態(tài)規(guī)劃法求解的問題經(jīng)分解得到的子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，以致最后解決原問題需要耗費(fèi)指數(shù)級(jí)時(shí)間。

動(dòng)態(tài)規(guī)劃算法適用于解最優(yōu)化問題，通?？砂匆韵?4 個(gè)步驟設(shè)計(jì)：
① 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；
② 遞歸地定義最優(yōu)值；
③ 以自底向上的方式計(jì)算最優(yōu)值；
④根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。

貪心算法
顧名思義，貪心算法總是做出在當(dāng)前看來是最好的選擇。也就是說，貪心算法并不從整體最優(yōu)上加以考慮，所做的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，我們希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。

回溯法（深度優(yōu)先搜索DFS）
回溯法有 “通用的解題法”之稱，可以系統(tǒng)地搜索一個(gè)問題的所有解或任一解，它是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。

分支限界法（廣度優(yōu)先搜索BFS）
{ 第六章不考編程，故選擇可能會(huì)涉及 }
分支限界法類似回溯法，也是在問題的解空問上搜索問題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同。回溯法的求解目標(biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。

【編程題】

[ 二分搜索 ]

這個(gè)必須會(huì)?。。?/span>

這里直接上代碼，沒什么好說的。
題目：在遞增數(shù)組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退出循環(huán) 
	{
		bool flag = 0;		//x是否在a數(shù)組標(biāo)志，0不存在，1存在 
		int left = 0;		//查找區(qū)間左端 
		int right = n-1;	//查找區(qū)間右端 
		while(left<=right)
		{
			int mid = (left+right)/2;	//取中值 
			if(a[mid] == x) 
			{
				flag = 1;
				break;		//若找到則退出循環(huán) 
			}
			if(a[mid] > x)
				right = mid-1;	//中值大于目標(biāo)值，目標(biāo)值在左半段 
			else
				left = mid+1;	//中值小于目標(biāo)值，目標(biāo)值在右半段 
		}
		if(flag == 0)
			cout<<"no"<<'\n';
		else
			cout<<"yes"<<'\n';
		cin >> x;
	}
}

進(jìn)階：浮點(diǎn)數(shù)的二分查找，涉及精度問題，可去CSDN搜索 “PIE問題” 。

[ 合并排序 ]

思想：將兩個(gè)有序的數(shù)組合成一個(gè)有序的數(shù)組解決問題。

題目：給定兩遞增數(shù)組a1和a2，求兩數(shù)組元素集合的中位數(shù)。

#include<iostream>
using namespace std;
const int N = 1e5; 

int main(){
    int n, a1[N], a2[N], a3[2*N];	//合并數(shù)組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數(shù)組都沒走完
	{
        if(a1[a]<a2[b])	//逐個(gè)比較a1和a2中元素大小，依次取小的存入a3 
		{
            a3[c]=a1[a];
            c++;
			a++; 
        }
        else
		{
            a3[c]=a2[b];
            c++;
            b++;
        }        
    }
    //必定有一個(gè)數(shù)組會(huì)走完，剩下數(shù)組里的數(shù)一定比a3數(shù)組里的數(shù)大
	//將剩下數(shù)組的數(shù)放入a3數(shù)組 
    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的數(shù)組長度
    return 0; 
}

[ 快速排序 ]

書上的代碼如下，記憶。

//調(diào)用快排只需QuickSort(a,p,r)
//a為目的數(shù)組，p為數(shù)組起點(diǎn)下標(biāo)0，r為數(shù)組終點(diǎn)下標(biāo)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看北京航空航天大學(xué)的《算法設(shè)計(jì)與分析》

https://www.icourse163.org/course/BUAA-1449777166?tid=1463474515

課件 - 03分而治之篇II - 3.2快速排序 上

{ 期中考 } 查找第K小的數(shù)就是用的快排思想。

[ 動(dòng)態(tài)規(guī)劃 ]

必考題，思想比較靈活，建議是去刷網(wǎng)課然后自己做一遍。

課件 - 040506動(dòng)態(tài)規(guī)劃

[ 貪心算法 ]

有手就行，考到就是賺到??！

[ 回溯法DFS ]

期末重難點(diǎn)，但其實(shí)會(huì)了0-1背包就沒問題了。

建議是抓個(gè)會(huì)的活人給你現(xiàn)場講解帶著寫一下。

這里上一道去年的期末題：

帶書計(jì)劃

【Description】

小明買到了他心儀的算法書。他打算帶著這些書回家，趁著假期好好學(xué)習(xí)一下算法。但是由于飛機(jī)上有行李重量的限制，大塊頭的計(jì)算機(jī)書籍都很重。小明想盡可能用滿行李重量的限額，在不超過限額的前提下，帶的書越重越好。辛辛苦苦學(xué)了一學(xué)期算法的你，能幫助小明找到最佳的解決方案嗎，告訴他可以帶哪些書嗎？

【Input】

第一行2個(gè)整數(shù)，分別代表飛機(jī)重量的限制b(0< b < 1000)、書的數(shù)量n(0 < n < 100)。 下面n行，每行一個(gè)字符串和整數(shù)，空格分隔，代表每本書的名稱和重量

【Output】

按書名的字典排序輸出多行，每行代表一本書。如果有多個(gè)答案，輸出字典序最小的答案。如果一本書都不能帶，輸出-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》兩種組合都可以獲得最大值，取字典序最小的按字典序輸出。

?題目難度還好，關(guān)鍵在于字典序的輸出，需要會(huì)對(duì)結(jié)構(gòu)體的排序。

代碼如下：

#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];			//下標(biāo)表示書號(hào)

bool cmp(node A, node B)
{
	return A.name < B.name;
}

void Dfs(int t)		//當(dāng)前訪問書的書號(hào)t
{
	if(t>n)	//當(dāng)所有書籍都找完 
	{
		if(cv > Max)	//當(dāng)前存放量cv大于所記錄最大方案 
		{
			Max = cv;
			cn = way.size();	//總共拿了幾本書cn 
			int i=0;
			for(auto x:way)
			{
				ans[i] = x;		//將拿到的書的序號(hào)存到ans數(shù)組 
				i++;
			}
		}
		return;
	}
	if(cv+book[t].weight <= b)	//cv+book[t].weight如果加入下本書不會(huì)超容量 
	{
		cv += book[t].weight;	//拿書 
		way.push_back(t);		//記錄拿的幾號(hào)書 
		Dfs(t+1);				//回溯 
		cv -= book[t].weight;	//放回書 
		way.pop_back(); 		//刪去放回的書的記錄 
	}
	Dfs(t+1);	//當(dāng)前t號(hào)書不拿，考慮下一本 
	return;
}

int main()
{
	cin>>b>>n;	//輸入最大容量b ，書籍?dāng)?shù)目n 
	for(int i=1; i<=n; i++)
	{
		cin>>book[i].name>>book[i].weight;
	}
	sort(book+1,book+1+n,cmp);	//將書籍按字典序排序 
	
	Dfs(1);	//回溯法，深度優(yōu)先搜索
	
	if(Max == 0)	//最大方案為0，即沒有書籍 
	{
		cout<<"-1"<<'\n';
	}
	else
	{
		for(int i=0; i<cn; i++)	//輸出各書號(hào)對(duì)應(yīng)的書名 
			cout<<book[ans[i]].name<<'\n';
	}
	return 0;
}

【結(jié)語】

相信自己，算法期末，有手就行?。?！文章來源地址http://www.zghlxwxcb.cn/news/detail-435087.html

到了這里，關(guān)于【期末復(fù)習(xí)】計(jì)算機(jī)算法設(shè)計(jì)與分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！