期末算法分析程序填空题
目录5-1 最小天生树（普里姆算法）
5-2 快速排序（分治法）
输入样例：
输出样例：
5-3 归并排序(递归法)
输入样例：
输出样例：
5-4 求解编辑距离问题（动态规划法）
输入格式:
输出格式:
输入样例1:
输出样例1:
5-5 求解会议安排问题（动态规划）
输入格式:
输出格式:
输入样例1:
输出样例1:
5-6
求解n皇后问题（递归回溯法）
输入格式:
输出格式:
输入样例1:
输出样例1:
5-7 0/1背包问题（回溯法）
输入格式:
输出格式:
输入样例1:
输出样例1:
5-8 0/1背包问题（分支限界法）
输入格式:
输出格式:
输入样例1:
输出样例1:
输入样例2:
输出样例2:
5-9 部分背包问题（贪心法）
输入格式:
输出格式:
输入样例1:
输出样例1:
5-10 两个字符串的最长公共子序列长度
5-1 最小天生树（普里姆算法）
最小天生树（普里姆算法）。
#include <iostream>
#define MVNum 100
#define MaxInt 3276
7
using namespace std;
struct edge{
char adjvex;
int lowcost;
}closedge;
typedef struct{
char vexs;
int arcs;
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G , char v);//实现细节隐藏
int CreateUDN(AMGraph &G);//实现细节隐藏
int Min(AMGraph G){
int i;
int index 
1; -1;
int min 
1; MaxInt;
for(i 
1; 0 ; i < G.vexnum ; ++i){
if(){
min 
1; closedge.lowcost;
index 
1; i;
}
}
return index;
}
void MiniSpanTree_Prim(AMGraph G, char u){
int k , j , i;
char u0 , v0;
k 
1;LocateVex(G, u);
for(j 
1; 0; j < G.vexnum; ++j){
if(j !
1; k){
closedge.adjvex 
1; ;
closedge.lowcost 
1; ;
}
}
closedge.lowcost 
1; ;
for(i 
1; 1; i < G.vexnum; ++i){
k 
1; ;
u0 
1; closedge.adjvex;
v0 
1; G.vexs;
cout << u0 << "->" << v0 << endl;
closedge.lowcost 
1; ;
for(j 
1; 0; j < G.vexnum; ++j)
if(G.arcs < closedge.lowcost){
closedge.adjvex 
1; ;
closedge.lowcost 
1; ;
}
}
}
int main(){
AMGraph G;
CreateUDN(G);
char u;
cin >> u;
MiniSpanTree_Prim(G , u);
return 0;
} 第一空：min > closedge.lowcost && closedge.lowcost !
1; 0
第二空：u
第三空：G.arcs
第四空：0
第五空：Min(G)
第六空：0
第七空：G.vexs
第八空：G.arcs
5-2 快速排序（分治法）
快速排序。
#include <iostream>
#define MAXSIZE 100
0
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}ElemType;
typedef struct
{
ElemType *r;
intlength;
}SqList;
int Partition(SqList &L,int low,int high)
{
int pivotkey;
L.r
1;L.r;
pivotkey
1;L.r.key;
while()
{
while() --high;
L.r
1;L.r;
while() ++low;
L.r
1;L.r;
}
L.r
1;L.r;
returnlow;
}
void QSort(SqList &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc
1;;
;
;
}
}
void QuickSort(SqList &L)
{
QSort(L,1,L.length);
}
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i
1;1;i<
1;n;i++)
{
cin>>L.r.key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i
1;1;i<
1;L.length;i++)
if(i
1;
1;1)
cout<<L.r.key;
else
cout<<" "<<L.r.key;
}
int main()
{
SqList L;
L.r
1;new ElemType;
L.length
1;0;
Create_Sq(L);
QuickSort(L);
show(L);
return 0;
}输入样例：
第一行输入一个数n(输入的值不大于 MAXSIZE)，接下来输入n个数。
7
24 53 45 45 12 24 90
输出样例：
输出按升序排序的结果。
12 24 24 45 45 53 90 第一空：low < high
第二空：low < high && L.r.key >
1; pivotkey
第三空：low < high && L.r.key <
1; pivotkey
第四空：Partition(L,low,high)
第五空：QSort(L,low,pivotloc-1)
第六空：QSort(L,pivotloc+1,high)
5-3 归并排序(递归法)
归并排序(递归法)。
#include <iostream>
#define MAXSIZE 100
0
using namespace std;
typedef struct
{
int key;
char *otherinfo;
}ElemType;
typedef struct
{
ElemType *r;
intlength;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cin>>n; //输入的值不大于 MAXSIZE
for(i
1;1;i<
1;n;i++)
{
cin>>L.r.key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i
1;1;i<
1;L.length;i++)
if(i
1;
1;1)
cout<<L.r.key;
else
cout<<" "<<L.r.key;
}
void Merge(ElemType R[],ElemType T[],int low,int mid,int high)
{
int i,j,k;
i
1;low; j
1;mid+1;k
1;low;
while(i<
1;mid&&j<
1;high)
{
if(R.key<
1;R.key) T
1;R;
else T
1;R;
}
while(i<
1;mid)
T
1;R;
while(j<
1;high)
T
1;R;
}
void MSort(ElemType R[],ElemType T[],int low,int high)
{
int mid;
ElemType *S
1;new ElemType;
if(low
1;
1;high)
;
else
{
mid
1;(low+high)/2;
;
;
;
}
}
void MergeSort(SqList &L)
{
MSort(L.r,L.r,1,L.length);
}
int main()
{
SqList R;
R.r
1;new ElemType;
R.length
1;0;
Create_Sq(R);
MergeSort(R);
show(R);
return 0;
}输入样例：
第一行输入一个数n，接下来输入n个数。
7
24 53 45 45 12 24 90
输出样例：
输出排序结果。
12 24 24 45 45 53 90 第一空：T
1;R
第二空：MSort(R,S,low,mid)
第三空：MSort(R,S,mid+1,high)
第四空：Merge(S,T,low,mid,high)
5-4 求解编辑距离问题（动态规划法）
设A和B是两个字符串。现在要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有3种：
（1）删除一个字符。
（2）插入一个字符。
（3）将一个字符替换另一个字符。
#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 201
//问题表示
string a;
string b;
//求解结果表示
int dp;
void solve() //求dp
{
int i,j;
for (i
1;1;i<
1;a.length();i++)
dp
1;i; //把a的i个字符全部删除转换为b
for (j
1;1; j<
1;b.length(); j++)
dp
1;j; //在a中插入b的全部字符转换为b
for (i
1;1; i<
1;a.length(); i++)
for (j
1;1; j<
1;b.length(); j++)
{
if (a
1;
1;b)
;
else
dp
1;;
}
}
int main()
{ cin>>a>>b;
solve();
printf("%d",dp);
return 0;
}输入格式:
第一行输入A字符串，第二行输入B字符串。
输出格式:
输出最少的字符操作次数。
输入样例1:
sfdqxbw
gfdgw
输出样例1:
4 第一空：dp
1;dp
第二空： min(dp, min(dp, dp)) + 1
5-5 求解会议安排问题（动态规划）
陈老师是一个比赛队的主教练。有一天，他想与团队成员开会，应该为这次会议安排课堂。课堂非常缺乏，所以课堂管理员必须接受订单和拒绝订单以优化课堂的使用率。如果接受一个订单，该订单的开始时间和竣事时间成为一个活动。每个时间段只能安排一个订单（即假设只有一个课堂）。请你找出一个最大化的总活动时间的方法。你的任务是这样的：读入订单，盘算全部活动（接受的订单）占用时间的最大值。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX 101
//问题表示
struct NodeType
{
int b; //开始时间
int e; //结束时间
int length; //订单的执行时间
};
bool cmp(const NodeType &a,const NodeType &b)
{ //用于排序的运算符重载函数
return a.e<b.e; //按结束时间递增排序
}
int n; //订单个数
NodeType A; //存放订单
//求解结果表示
int dp; //动态规划数组
int pre; //pre存放前驱订单编号
void solve();
int main()
{
cin>>n;
for(int i
1;0;i<n;i++)
cin>>A.b>>A.e;
for (int i
1;0; i<n; i++)
A.length
1;A.e-A.b;
solve();
cout<<dp;
return 0;
}
void solve() //求dp和pre
{
memset(dp,0,sizeof(dp)); //dp数组初始化
stable_sort(A,A+n,cmp); //采用稳定的排序算法
dp
1;A.length;
pre
1;-1;
for (int i
1;1;i<n;i++)
{
int low
1;0, high
1;i-1;
while(low<
1;high) //在A中查找结束时间早于A开始时间的最晚订单A
{
int mid
1;(low+high)/2;
if(A.e<
1;A.b)
low
1;mid+1;
else
high
1;mid-1;
}
if (low
1;
1;0) //特殊情况
{
if(dp>
1;A.length)
{
dp
1;;
pre
1;-2; //不选中订单i
}
else
{
dp
1;;
pre
1;-1; //没有前驱订单
}
}
else //A前面最晚有兼容订单A
{
if (dp>
1;dp+A.length)
{
dp
1;;
pre
1;-2; //不选中订单i
}
else
{
dp
1;;
pre
1;low-1; //选中订单i
}
}
}
}输入格式:
第一行是一个整数n，接着的n行中每一行包罗两个整数b和e，其中b是一个订单开始时间，e是的竣事时间。。
输出格式:
输出一行包罗全部活动占用时间的最大值。
输入样例1:
11
1 4
3 5
0 6
5 7
3 8
5 9
6
10
8 11
8 12
2 13
12 15
输出样例1:
13 第一空：dp
第二空：A.length
第三空：dp
第四空：dp+A.length
5-6
求解n皇后问题（递归回溯法）
在n×n的方格棋盘上，放置n个皇后，要求每个皇后不偕行、差别列、差别左右对角线。如下图所示是6
皇后问题的一个解。
#include <stdio.h>
#include <stdlib.h>
#define N 20 //最多皇后个数
int q; //存放各皇后所在的列号,即(i,q)为一个皇后位置
void dispasolution(int n) //输出n皇后问题的一个解
{
for (int i
1;1;i<
1;n;i++)
printf("(%d,%d)",i,q);
printf("\n");
}
bool place(int i,int j) //测试(i,j)位置能否摆放皇后
{
if (i
1;
1;1) return true; //第一个皇后总是可以放置
int k
1;1;
while (k<i) //k
1;1～i-1是已放置了皇后的行
{ if ((q
1;
1;j) || (abs(q-j)
1;
1;abs(i-k)))
;
k++;
}
;
}
void queen(int i,int n) //放置1～i的皇后
{ if (i>n)
dispasolution(n); //所有皇后放置结束
else
{
for (int j
1;1;j<
1;n;j++) //在第i行上试探每一个列j
if () //在第i行上找到一个合适位置(i,j)
{ q
1;j;
;
}
}
}
int main()
{ int n; //n为存放实际皇后个数
scanf("%d",&n);
if (n<
1;20)
queen(1,n); //放置1～i的皇后
return 0;
}
输入格式:
输入n。
输出格式:
按行输出每组解。
输入样例1:
6
输出样例1:
(1,2)(2,4)(3,6
)(4,1)(5,3)(6
,5)(1,3)(2,6
)(3,2)(4,5)(5,1)(6
,4)(1,4)(2,1)(3,5)(4,2)(5,6
)(6
,3)(1,5)(2,3)(3,1)(4,6
)(5,4)(6
,2) 第一空：return false
第二空：return true
第三空：place(i,j)
第四空：queen(i+1,n)
5-7 0/1背包问题（回溯法）
0/1背包问题。给定一载重量为W的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求而且重量和恰恰为W具有最大的价值。
#include <stdio.h>#include <string.h>#include <iostream>#define MAXN 20 //最多物品数using namespace std;int n; //物品数int W; //限定重量int w
1;{0}; //存放物品重量,不用下标0元素int v
1;{0}; //存放物品价值,不用下标0元素int x; //存放终极解int maxv; //存放最优解的总价值void dfs(int i,int tw,int tv,int rw,int op[]) //求解0/1背包问题{ int j; if (i>n) //找到一个叶子结点 { if () //找到一个满意条件的更优解,保存它 { maxv
1;tv; for () //复制最优解 x
1;op; } } else //尚未找完全部物品 { if () //左孩子结点剪枝：满意条件时才放入第i个物品 { op
1;1; //选取第i个物品 dfs(); } op
1;0; //不选取第i个物品,回溯 if () //右孩子结点剪枝 dfs(); }}void dispasolution() //输出最优解{ int i; for (i
1;1;i<
1;n;i++) if (x
1;
1;1) printf("%d ",i); printf("\n%d %d",W,maxv);}int main(){ int i; cin>>n>>W; //输入物体个数及背包载重量 for(int i
1;1;i<
1;n;i++)//输入各物体重量及价值 cin>>w>>v; int op; //存放暂时解 memset(op,0,sizeof(op)); int rw
1;0; for (int i
1;1;i<
1;n;i++) rw+
1;w; dfs(1,0,0,rw,op); dispasolution(); return 0;}输入格式:
第一行输入背包载重量W及背包个数n，再依次输入n行，每活动背包重量wi和价值vi。
输出格式:
第一行输出输出装入背包内的物体编号(末端有空格)，第二行输出背包内的物体总重量和总价值。
输入样例1:
5 102 6
2 36
55 44 6
输出样例1:
1 2 3
10 14 第一空：tw
1;
1;W && tv>maxv
第二空：j
1;1;j<
1;n;j++
第三空：tw+w<
1;W
第四空：i+1,tw+w,tv+v,rw-w,op
第五空：tw+rw>W
第六空：i+1,tw,tv,rw-w,op
5-8 0/1背包问题（分支限界法）
0/1背包问题。给定一载重量为m的背包及n个重量为wi、价值为vi的物体，1≤i≤n,要求把物体装入背包，使背包的物体价值最大。
输入格式:
第一行输入背包载重量m及背包个数n，再依次输入n行，每活动背包重量wi和价值vi。
输出格式:
第一行输出输出所求X数组，第二行输出装入背包内的物体的最大价值。
输入样例1:
5 102 6
2 36
55 44 6
输出样例1:
11001
15
输入样例2:
5 10
11 2
13 10
12 5
13 3
11 6
输出样例2:
00
0#include <stdio.h>#include <queue>#include <iostream>using namespace std;#define MAXN 20 //最多大概物品数//问题表示int n,W;int w; //重量，下标0不用int v; //价值，下标0不用//求解结果表示int maxv
1;-9999; //存放最大价值,初始为最小值int bestx; //存放最优解,全局变量int total
1;1; //解空间中结点数累计,全局变量struct NodeType //队列中的结点类型{ int no; //结点编号 int i; //当前结点在搜刮空间中的层次 int w; //当前结点的总重量 int v; //当前结点的总价值 int x; //当前结点包罗的解向量 double ub; //上界};void bound(NodeType &e) //盘算分枝结点e的上界{ int i
1;e.i+1; int sumw
1;e.w; double sumv
1;e.v; while () { sumw+
1;w; //盘算背包已装入载重 sumv+
1;v; //盘算背包已装入价值 i++; } if (i<
1;n) e.ub
1;; else e.ub
1;sumv;}void EnQueue(NodeType e,queue<NodeType> &qu) //结点e进队qu{ if (e.i
1;
1;n) //到达叶子结点 { if (e.v>maxv) //找到更大价值的解 { ; for (int j
1;1;j<
1;n;j++) ; } } else qu.push(e); //非叶子结点进队}void bfs() //求0/1背包的最优解{ int j; NodeType e,e1,e2; //界说3个结点 queue<NodeType> qu; //界说一个队列 e.i
1;0; //根结点置初值，其层次计为0 e.w
1;0; e.v
1;0; e.no
1;total++; for (j
1;1;j<
1;n;j++) e.x
1;0; bound(e); //求根结点的上界 qu.push(e); //根结点进队 while (!qu.empty()) //队不空循环 { e
1;qu.front(); qu.pop(); //出队结点e e1.no
1;total++; e1.i
1;e.i+1; //创建左孩子结点 e1.w
1;e.w+w; e1.v
1;e.v+v; for (j
1;1;j<
1;n;j++) //复制解向量 e1.x
1;e.x; e1.x
1;1; bound(e1); //求左孩子结点的上界 if() //剪枝：检查左孩子结点 { EnQueue(e1,qu); //左孩子结点进队操作 } e2.no
1;total++; //创建右孩子结点 e2.i
1;e.i+1; e2.w
1;; e2.v
1;; for (j
1;1;j<
1;n;j++) //复制解向量 e2.x
1;e.x; e2.x
1;; bound(e2); //求右孩子结点的上界 if () //若右孩子结点可行,则进队,否则被剪枝 EnQueue(e2,qu); }}int main(){ cin>>n>>W; //输入物体个数及背包载重量 for(int i
1;1;i<
1;n;i++)//输入各物体重量及价值 cin>>w>>v; bfs(); //调用队列式分枝限界法求0/1背包问题 for(int i
1;1;i<
1;n;i++) printf("%d",bestx); printf("\n%d",maxv); return 0;} 第一空：(sumw+w<
1;W) && i<
1;n
第二空：sumv+(W-sumw)*v/w
第三空：maxv
1;e.v
第四空：bestx
1;e.x
第五空：e.w+w<
1;W&&e1.ub>maxv
第六空：e.w
第七空：e.v
第八空：0
第九空：e2.ub>maxv
5-9 部分背包问题（贪心法）
设有编号为1、2、…、n的n个物品，它们的重量分别为w1、w2、…、wn，价值分别为v1、v2、…、vn，其中wi、vi（1≤i≤n）均为正数。
有一个背包可以携带的最大重量不超过W。求解目标：在不超过背包负重的前提下，使背包装入的总价值最大。
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;#define MAXN 51//问题表示int n;double W; //限重struct NodeType{ int no; double w; double v; double p; //p
1;v/w float x; bool operator<(const NodeType &s) const { return p>s.p; //按p递减排序 }};NodeType A
1;{{0}}; //下标0不用//求解结果表示double V; //最大价值bool cmp(const NodeType &a,const NodeType &b){ return a.no<b.no;}void Knap() //求解背包问题并返回总价值{ V
1;0; //V初始化为0 double weight
1;W; //背包中能装入的余下重量 int i
1;1; while () { A.x
1;1; //装入物品i ; V+
1;A.v; //累计总价值 ; } if (weight>0) //当余下重量大于0 { A.x
1;; V+
1;A.x*A.v; //累计总价值 }}int main(){ cin>>n>>W; for(int i
1;1;i<
1;n;i++) { cin>>A.no>>A.w>>A.v;A.x
1;0; } for (int i
1;1;i<
1;n;i++) //求v/w A.p
1;A.v/A.w; sort(A+1,A+n+1); //排序 Knap(); sort(A+1,A+n+1,cmp); for(int j
1;1;j<
1;n;j++) cout<<A.no<<" "<<A.x*A.v<<endl; cout<<V; return 0;}输入格式:
第一行物品数n和背包容量W，接着的n行中输入每个物品的编号，重量和价值。
输出格式:
输出装入背包的物品信息，共n行，按物品编号递增排序的物品编号及重量（物品编号从1开始）。末了一行输出总价值。
输入样例1:
5 1001 10 202 20 303 30 6
6
4 40 405 50 6
0输出样例1:
1 202 303 6
6
4 05 4816
4 第一空：A.w<
1;weight
第二空：weight-
1;A.w
第三空：i++
第四空：weight/A.w
5-10 两个字符串的最长公共子序列长度
下面程序完成最长公共子序列的长度盘算。
#include<stdio.h>#include<string.h>#define N 80int C; // 纪录最长公共子序列 int rec; // 纪录轨迹 int LCSLength(char *X, char *Y) { int i,j,m
1;strlen(X),n
1;strlen(Y); for(i 
1; 1; i <
1;m ; i++) { for(j 
1; 1; j <
1; n; j++) { if() { C 
1; C + 1; rec 
1; 1; //LU }else if() { C 
1; C; rec 
1; 2; //U }else { C 
1; ; rec 
1; 3; //L } } } return C;} 第一空：X
1;
1;Y
第二空：C>
1;C
第三空：C
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]