【精选】算法设计与分析（考试算法汇总篇）
前言
总结算法设计与分析课程期末必记知识点。
考试算法汇总篇
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--;
}
}
}
} 结语
考试算法汇总篇结束。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
