【精选】算法设计与分析(考试算法汇总篇)

2023-12-13 05:07:28

目录

前言

考试算法汇总篇

1、求解梵塔问题的递归算法

2、二路归并的递归算法??

3、求 n! 的递归算法

4、斐波那契数列对应的递归算法

5、简单选择排序

6、冒泡排序

7、n皇后问题所有解的完整程序

8、快速排序

9、折半查找算法

10、BF算法——字符串匹配

11、求a的最大连续子序列和?

12、求解0/1背包问题

13、求解子集和(1)?

14、求解子集和(2)

15、求解子集和(3)?

16、求解最大兼容活动子集

17、求解最大兼容活动子集个数

18、求解背包问题并返回总价值

19、田忌赛马

结语


前言

总结算法设计与分析课程期末必记知识点。

考试算法汇总篇

1、求解梵塔问题的递归算法
void Hanoi(int n,char x,char y,char z){
	if(n==1)
		printf("将盘片%d从%c搬到%c\n",n,x,z);
	else
	{
		Hanoi(n-1,x,z,y);
		printf("将盘片%d从%c搬到%c\n",n,x,z);
		Hanoi(n-1,y,x,z);
	 } 
}
2、二路归并的递归算法??
void mergesort(int a[],int i,int j){
	int mid;
	if(i!=j){
		mid=(i+j)/2;
		mergesort(a,i,mid);
		mergesort(a,mid+1,j);
		merge(a,i,j,mid);
	}
}
3、求 n! 的递归算法
int fun(int n){
	if(n==1)
		return(1);
	else
		return(fun(n-1)*n);
}
4、斐波那契数列对应的递归算法
int Fib(int n){
	if(n==1||n==2)
		return 1;
	else
		return Fib(n-1)+Fib(n-2);
}
5、简单选择排序
#include<stdio.h>
void swap(int &x,int &y){	//交换x和y的值 
	int tmp=x;
	x=y;
	y=tmp;
}

void disp(int a[],int n){	//输出 a 中的所有元素 
	int i;
	for(i=0;i<n;i++)
		printf("%d",a[i]);
	printf("\n");
}

void SelectSort(int a[], int n,int i){
	int j,k;
	if(i==n-1)return;
	else
	{
		k=i;
		for(j=i+1;j<n;j++){
			if(a[j]<a[k]){
				k=j;
			}
		}
		if(k!=i)
			swap(a[i],a[k]);
		SelectSort(a,n,i+1);
	}
} 
int main(){
	int n=7;
	int a[]={2,5,1,7,10,16,11};
	printf("排序前:");
	disp(a,n);
	SelectSort(a,n,0);
	printf("排序后:");
	disp(a,n);
	return 0;
}
6、冒泡排序
void BubbleSort(int a[],int n,int i){
	int j;
	bool exchange;
	if(i==n-1) return;	//满足递归出口条件
	else
	{
		exchange = false;	//置exchange为flase
		for(j=n-1;j>i;j--){	//将 a[i..n-1] 中的最小元素放到 a[i] 处 
			if(a[j]<a[j-1])	//当相邻元素反序时
			{
				swap(a[j],a[j-1]);
				exchange=true; 
			} 
		}
		if(exchange == false)//为发生交换时候直接返回 
			return;
		else
			BubbeSort(a,n,i+1); 
	 } 
} 
7、n皇后问题所有解的完整程序
#include<stdio.h>
#include<stdlib.h>
#define N 20							//最多皇后个数 
int q[N];								//存放各个皇后所在的列号,即(i,q[i])为一个皇后位置 
int count = 0;							//累计解个数 
void dispasolution(int n)				//输出 n 皇后问题的一个解 
{
	printf("   第%d个解:", ++count);
	for (int i = 1; i <= n; i++)
		printf("(%d,%d)", i, q[i]);
	printf("\n");
}
bool place(int i, int j)					//测试(i,j)位置能否摆放皇后 
{
	if (i == 1)return true;
	int k = 1;
	while (k < i)
	{
		if ((q[k] == j) || (abs(q[k] - j) == abs(i - k)))
			return false;
		k++;
	}
	return true;
}
void queen(int i, int n)				//放置 1~i 的皇后
{
	if (i > n) {						//所有皇后放置结束
		dispasolution(n);				
	}
	else
	{
		for (int j = 1; j <= n; j++) {	//在第i行上试探每一个列j
			if (place(i, j))			//在第i行上找到一个合适位置(i,j)
			{
				q[i] = j;
				queen(i + 1, n);
			}
		}
	}
}
int main() {
	int n;								//n为存放实际皇后的个数
	printf(" 皇后问题(n<20)n=");
	scanf("%d", &n);
	if (n > 20) {
		printf("n值太大,不能求解\n");
	}
	else
	{
		printf("%d皇后问题求解如下:\n", n);
		queen(1, n);					//放置 1 ~ n 的皇后
	}
	return 0;
}
8、快速排序
#include<stdio.h>

void disp(int a[],int n){	//输出 a 中的所有元素 
	int i;
	for(i=0;i<n;i++)
		printf("%d",a[i]);
	printf("\n");
}

int Partition(int a[], int s, int t)	//划分算法
{
	int i = s, j = t;
	int tmp = a[s];						//用序列的第 1 个记录作为基准
	while (i != j)						//从序列两端交替向中间扫描,直到 i=j为止
	{
		while (j > i && a[j] >= tmp)	
			j--;						//从右向左扫描,找第 1 个关键字大于 tmp 的a[i]
		a[i] = a[j];					//将a[i]后移到a[j]的位置
		while (i < j && a[i] <= tmp)
			i++;						//从左向右扫描,找第 1 个关键字大于 tmp 的a[i]
		a[j] = a[i];					//将 a[i]后移到a[j]的位置
	}
	a[i] = tmp;
	return i;
}

void QuickSort(int a[], int s, int t)		//对a[s..t]元素序列进行递增排序
{
	if (s < t)
	{
		int i = Partition(a, s, t);
		QuickSort(a, s, i - 1);				//对左子序列递归排序
		QuickSort(a, i + 1, t);				//对右子序列递归排序
	}
}

int main() {
	int n = 5;
	int a[] = { 5,2,3,1,4 };
	printf("排序前:");
	disp(a, n);
	QuickSort(a, 0, n - 1);
	printf("排序后:");
	disp(a, n);
	return 0;
}
9、折半查找算法
#include<stdio.h>
int BinSearch(int a[], int low, int high, int k)//折半查找算法
{
	int mid;
	if (low <= high)			//当前区间存在元素时
	{
		mid = (low + high) / 2; //求查找区间的中间位置
		if (a[mid] == k)			//找到后返回其物理下标mid
			return mid;
		if (a[mid] > k)				//当a[mid]>k时在a[low..mid-1]中递归查找
			return BinSearch(a, low, mid - 1, k);
		else                        //当a[mid]<k时在a[mid+1..high]中递归查找
			return BinSearch(a, mid + 1, high, k);
	}
	else return -1;					//当前查找区间没有元素返回-1
}
int main() {
	int n = 10, i;
	int k = 6;
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	i = BinSearch(a, 0, n - 1, k);
	if (i >= 0)
		printf("a[%d]=%d\n", i, k);
	else
		printf("未找到%d元素\n", k);
	return 0;
} 
10、BF算法——字符串匹配
int BF(string s, string t)	//字符串匹配
{
	int i = 0, j = 0;
	while (i < s.length() && j < t.length())
	{
		if (s[i] == t[j])		//比较的两个字符相同时
		{
			i++;
			j++;
		}
		else                    //比较的两个字符不相同时
		{
			i = i - j + 1;		//i回退到原来i的下一个位置
			j = 0;				//j从0开始
		}
	}
	if (j == t.length())			//t的字符比较完毕
		return i - j;				//t是s的子串,返回位置
	else
		return -1;					//返回-1
}
11、求a的最大连续子序列和?
#include<stdio.h>
int maxSubSum3(int a[], int n)	//求a的最大连续子序列和
{
	int i, maxSum = 0, thisSum = 0;
	for (i = 0; i < n; i++)
	{
		thisSum += a[i];
		if (thisSum < 0)			//若当前子序列和为负数,则重新开始下一个子序列
			thisSum = 0;
		if (maxSum < thisSum)		//比较求最大连续子序列和
			maxSum = thisSum;
	}
	return maxSum;
}
12、求解0/1背包问题
void dfs(int i, int tw, int tv, int rw, int op[])//求解0/1背包问题
{
	if (i > n)				//找到一个叶子结点
	{
		if (tw == W && tv > maxv)	//找到一个满足条件的更优解,保存它
		{
			maxv = tv;
			for (int j = 1; j <= n; j++)	//复制最优解
				x[j] = op[j];
		}
	}
	else                    //尚未找完所有物品
	{
		if (tw + w[i] < W)		//左孩子结点剪枝
		{
			op[i] = 1;			//选取第i个物品
			dfs(i + 1, tw + w[i], tv + v[i], rw - w[i], op);
		}
		if (tw + rw - w[i] >= W)		//右孩子结点剪枝
		{
			op[i] = 0;					//不选取第i个物品,回溯
			dfs(i + 1, tw, tv, rw - w[i], op);
		}
	}
} 
13、求解子集和(1)?
#include<stdio.h>
#define MAXN 20		//最多整数个数
//问题表示
int n = 4, W = 31;
int w[] = { 0,11,13,24,7 };//存放所有整数,不用下标0的元素
int count = 0;		//累计解个数
void dispasolution(int n)//输出一个解
{
	for (int j = 1; j <= n; j++)
		if (w[j] == 1)
			printf("\t将第%d个集装箱装上第一艘轮船\n", j);
		else
			printf("\t将第%d个集装箱装上第二艘轮船\n", j);
}
void dfs(int i, int tw, int rw, int x[])//求解子集和
{	//tw为考虑第i个整数时选取的整数和,rw为剩下的整数和
	if (i > n)//找到一个叶子结点
	{
		if (tw == W)//找到一个满足条件的解,输出它
			dispasolution(tw);
	}
	else            //尚未找完所有整数
	{
		if (tw + w[i] <= W)//左孩子结点剪枝:选取满足条件的整数w[i]
		{
			x[i] = 1;//选取第i个整数
			dfs(i + 1, tw + w[i], rw - w[i], x);
		}
		if (tw + rw - w[i] >= W)//右孩子结点剪枝
		{
			x[i] = 0;			//不选取第i个整数,回溯
			dfs(i + 1, tw, rw - w[i], x);
		}
	}
}
int main() {
	int x[MAXN];
	int rw = 0;//存放一个解向量
	for (int j = 1; j <= n; j++)
		rw += w[j];//求所有整数和rw
	dfs(1, 0, rw, x);//i从1开始
	return 0;
}
14、求解子集和(2)
#include<stdio.h>
#define MAXN 20		//最多整数个数
//问题表示
int n = 4, W;
int w[] = { 0,11,13,24,7 };	//存放所有整数,不用下标0的元素
bool dfs(int i, int tw, int rw)	//存放所有整数,不用下标0的元素
{
	if (i > n)						//找到一个叶子结点
	{
		if (tw == W)					//找到一个满足条件的解,返回true
		{
			return true;
		}
	}
	else                            //尚未找完所有物品
	{
		if (tw + w[i] <= W)				//左孩子结点剪枝
			return dfs(i + 1, tw + w[i], rw - w[i]);//选取第i个整数
		if (tw + rw - w[i] >= W)				//有孩子结点剪枝
			return dfs(i + 1, tw, rw - w[i]);	//不选取第i个整数,回溯
	}
	return false;
}
15、求解子集和(3)?
int count;						//全局变量,累计解个数
void dfs(int i, int tw, int rw)	//求解子集和
{
	if (i > n)						//找到一个叶子结点
	{
		if (tw == W)					//找到一个满足条件的解,count++
		{
			count++;
		}
	}
	else                            //尚未找完所有物品
	{
		if (tw + w[i] <= W)				//左孩子结点剪枝
			dfs(i + 1, tw + w[i], rw - w[i]);//选取第i个整数
		if (tw + rw - w[i] >= W)				//有孩子结点剪枝
			dfs(i + 1, tw, rw - w[i]);	//不选取第i个整数,回溯
	}
}
16、求解最大兼容活动子集
void solve()//求解最大兼容活动子集
{
	memset(flag, 0, sizeof(flag));//初始化为false
	sort(A + 1, A + n + 1);//A[1..n]按活动结束时间递增排序
	int preend = 0;//前一个兼容活动的结束时间
	for (int i = 1; i <= n; i++)//扫描所有活动
	{
		if (A[i].b >= preend)//找到一个兼容活动
		{
			flag[i] = true;//选择A[i]活动
			preend = A[i].e;//更新preend值
		}
	}
} 
17、求解最大兼容活动子集个数
void solve()//求解最大兼容活动子集个数
{
	sort(A + 1, A + n + 1);//A[1..n]按指定方式排序
	memset(ans, 0, sizeof(ans));//初始化为0
	int num = 1;//畜栏编号
	for (int i = 1; i <= n; i++)//i、j均为排序后的下标
	{
		if (ans[i] == 0)//第i头牛还没有安排畜栏
		{
			ans[i] = num;//第i头牛安排畜栏
			int preend = A[i].e;//前一个兼容活动的结束时间
			for (int j = i + 1; j <= n; j++)//查找一个最大兼容活动子集
			{
				if (A[i].b > preend && ans[j] == 0)
				{
					ans[j] = num;//将兼容活动子集中的活动安排在num畜栏中
					preend = A[j].e;//更新结束时间
				}
			}
			num++;//查找下一个最大兼容活动子集,num增1
		}
	}
} 
18、求解背包问题并返回总价值
void Knap()//求解背包问题并返回总价值
{
	V = 0;//V初始化为0
	double weight = W;//背包中能装入的余下重量
	memset(x, 0, sizeof(x));//初始化x向量
	int i = 1;
	while (A[i].w < weight)//物品i能够全部装入时循环
	{
		x[i] = 1;//装入物品i
		weight -= A[i].w;//减少背包中能装入的余下重量
		V += A[i].v;//累计总价值
		i++;//继续循环
	}
	if (weight > 0)//余下重量大于0
	{
		x[i] = weight / A[i].w;//将物品i的一部分装入
		V += x[i] * A[i].v;//累计总价值
	}
} 
19、田忌赛马
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX 1001
问题描述
int n;
int a[MAX];
int b[MAX];
//求解结果表示
int ans;	//田忌获得的最多硬币数
void solve()//求解算法
{
	sort(a, a + n);//对a递增排序
	sort(b, b + n);//对b递增排序
	ans = 0;
	int lefta = 0, leftb = 0;
	int righta = n - 1, rightb = n - 1;
	while (lefta<righta)
	{
		if (a[righta] > b[rightb]) {
			ans += 200;
			righta--;
			rightb--;
		}
		else if (a[righta] < b[rightb])//田忌最快的马比齐威王最快的马慢
		{
			ans -= 200;//选择田忌最慢的马与齐威王最快的马比赛
			lefta++;
			rightb--;
		}
		else           //田忌最快的马与齐威王最快的马的速度相同
		{
			if (a[lefta] > b[leftb])//田忌最慢的马比齐威王最慢的马快,两者比赛
			{
				ans += 200;
				lefta++;
				leftb++;
			}
			else
			{
				if (a[lefta] < b[rightb])//否则用田忌最慢的马与齐威王最快的马比赛
					ans -= 200;
				lefta++;
				rightb--;
			}
		}
	}
} 

结语

考试算法汇总篇结束。

🌌点击下方个人名片,交流会更方便哦~(欢迎到博主主页加入我们的 CodeCrafters联盟一起交流学习)↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓????

文章来源:https://blog.csdn.net/VLOKL/article/details/134954951
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。