讯代理网站,介绍公司的话简短精辟,网站怎么发外链,深圳外贸网站建设哪家好目录 5-1 最小生成树#xff08;普里姆算法#xff09; 5-2 快速排序#xff08;分治法#xff09; 输入样例#xff1a; 输出样例#xff1a; 5-3 归并排序(递归法) 输入样例#xff1a; 输出样例#xff1a; 5-4 求解编辑距离问题#xff08;动态规划法#xff09;… 目录 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 32767
using namespace std;struct edge{char adjvex;int lowcost;
}closedge[MVNum];typedef struct{ char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum;
}AMGraph;int LocateVex(AMGraph G , char v);//实现细节隐藏
int CreateUDN(AMGraph G);//实现细节隐藏int Min(AMGraph G){int i;int index -1;int min MaxInt;for(i 0 ; i G.vexnum ; i){if(){min closedge[i].lowcost;index i;}}return index;
}void MiniSpanTree_Prim(AMGraph G, char u){ int k , j , i;char u0 , v0;k LocateVex(G, u);for(j 0; j G.vexnum; j){ if(j ! k){ closedge[j].adjvex ;closedge[j].lowcost ;}}closedge[k].lowcost ;for(i 1; i G.vexnum; i){k ; u0 closedge[k].adjvex;v0 G.vexs[k]; cout u0 - v0 endl;closedge[k].lowcost ; for(j 0; j G.vexnum; j) if(G.arcs[k][j] closedge[j].lowcost){closedge[j].adjvex ;closedge[j].lowcost ;}}
}int main(){AMGraph G;CreateUDN(G);char u;cin u;MiniSpanTree_Prim(G , u);return 0;
} 第一空min closedge[i].lowcost closedge[i].lowcost ! 0 第二空u 第三空G.arcs[k][j] 第四空0 第五空Min(G) 第六空0 第七空G.vexs[k] 第八空G.arcs[k][j] 5-2 快速排序分治法 快速排序。 #include iostream
#define MAXSIZE 1000
using namespace std;typedef struct
{int key;char *otherinfo;
}ElemType;typedef struct
{ElemType *r;int length;
}SqList;int Partition(SqList L,int low,int high)
{ int pivotkey;L.r[0]L.r[low]; pivotkeyL.r[low].key;while(){while() --high;L.r[low]L.r[high]; while() low;L.r[high]L.r[low];}L.r[low]L.r[0];return low;
}void QSort(SqList L,int low,int high)
{int pivotloc;if(lowhigh){ pivotloc;;;}
}void QuickSort(SqList L)
{QSort(L,1,L.length);
}void Create_Sq(SqList L)
{int i,n;cinn; //输入的值不大于 MAXSIZEfor(i1;in;i){cinL.r[i].key;L.length;}
}
void show(SqList L)
{int i;for(i1;iL.length;i)if(i1) coutL.r[i].key;elsecout L.r[i].key;
}int main()
{SqList L;L.rnew ElemType[MAXSIZE1];L.length0;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[high].key pivotkey 第三空low high L.r[low].key pivotkey 第四空Partition(L,low,high) 第五空QSort(L,low,pivotloc-1) 第六空QSort(L,pivotloc1,high) 5-3 归并排序(递归法) 归并排序(递归法)。 #include iostream
#define MAXSIZE 1000
using namespace std;typedef struct
{int key;char *otherinfo;
}ElemType;typedef struct
{ElemType *r;int length;
}SqList;void Create_Sq(SqList L)
{int i,n;cinn; //输入的值不大于 MAXSIZEfor(i1;in;i){cinL.r[i].key;L.length;}
}
void show(SqList L)
{int i;for(i1;iL.length;i)if(i1) coutL.r[i].key;elsecout L.r[i].key;
}void Merge(ElemType R[],ElemType T[],int low,int mid,int high)
{ int i,j,k;ilow; jmid1;klow; while(imidjhigh){ if(R[i].keyR[j].key) T[k]R[i]; else T[k]R[j]; } while(imid)T[k]R[i]; while(jhigh)T[k]R[j];
} void MSort(ElemType R[],ElemType T[],int low,int high)
{ int mid;ElemType *Snew ElemType[MAXSIZE];if(lowhigh) ; else{ mid(lowhigh)/2;;; ;}
} void MergeSort(SqList L)
{ MSort(L.r,L.r,1,L.length);
} int main()
{SqList R;R.rnew ElemType[MAXSIZE1];R.length0;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[low]R[low] 第二空MSort(R,S,low,mid) 第三空MSort(R,S,mid1,high) 第四空Merge(S,T,low,mid,high) 5-4 求解编辑距离问题动态规划法 设A和B是两个字符串。现在要用最少的字符操作次数将字符串A转换为字符串B。这里所说的字符操作共有3种 1删除一个字符。 2插入一个字符。 3将一个字符替换另一个字符。 #includestdio.h
#includestring
#includeiostream
#includealgorithm
using namespace std;
#define MAX 201
//问题表示
string a;
string b;
//求解结果表示
int dp[MAX][MAX];
void solve() //求dp
{int i,j;for (i1;ia.length();i) dp[i][0]i; //把a的i个字符全部删除转换为bfor (j1; jb.length(); j)dp[0][j]j; //在a中插入b的全部字符转换为bfor (i1; ia.length(); i)for (j1; jb.length(); j){if (a[i-1]b[j-1]);elsedp[i][j];}
}
int main()
{ cinab;solve();printf(%d,dp[a.length()][b.length()]);return 0;
} 输入格式: 第一行输入A字符串第二行输入B字符串。 输出格式: 输出最少的字符操作次数。 输入样例1: sfdqxbw
gfdgw输出样例1: 4 第一空dp[i][j]dp[i-1][j-1] 第二空 min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) 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.eb.e; //按结束时间递增排序
}int n; //订单个数
NodeType A[MAX]; //存放订单
//求解结果表示
int dp[MAX]; //动态规划数组
int pre[MAX]; //pre[i]存放前驱订单编号
void solve();int main()
{cinn;for(int i0;in;i)cinA[i].bA[i].e;for (int i0; in; i)A[i].lengthA[i].e-A[i].b;solve();coutdp[n-1]; return 0;
}void solve() //求dp和pre
{memset(dp,0,sizeof(dp)); //dp数组初始化stable_sort(A,An,cmp); //采用稳定的排序算法dp[0]A[0].length;pre[0]-1;for (int i1;in;i){int low0, highi-1;while(lowhigh) //在A[0..i-1]中查找结束时间早于A[i]开始时间的最晚订单A[low-1]{int mid(lowhigh)/2;if(A[mid].eA[i].b)lowmid1;elsehighmid-1;}if (low0) //特殊情况{if(dp[i-1]A[i].length){dp[i];pre[i]-2; //不选中订单i}else{dp[i];pre[i]-1; //没有前驱订单}}else //A[i]前面最晚有兼容订单A[low-1]{if (dp[i-1]dp[low-1]A[i].length){dp[i];pre[i]-2; //不选中订单i}else{dp[i];pre[i]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[i-1] 第二空A[i].length 第三空dp[i-1] 第四空dp[low-1]A[i].length 5-6 求解n皇后问题递归回溯法 在n×n的方格棋盘上放置n个皇后要求每个皇后不同行、不同列、不同左右对角线。如下图所示是6皇后问题的一个解。 #include stdio.h
#include stdlib.h
#define N 20 //最多皇后个数
int q[N]; //存放各皇后所在的列号,即(i,q[i])为一个皇后位置void dispasolution(int n) //输出n皇后问题的一个解
{for (int i1;in;i)printf((%d,%d),i,q[i]);printf(\n);
}bool place(int i,int j) //测试(i,j)位置能否摆放皇后
{if (i1) return true; //第一个皇后总是可以放置int k1;while (ki) //k1i-1是已放置了皇后的行{ if ((q[k]j) || (abs(q[k]-j)abs(i-k)));k;};
}void queen(int i,int n) //放置1i的皇后
{ if (in) dispasolution(n); //所有皇后放置结束else{for (int j1;jn;j) //在第i行上试探每一个列jif () //在第i行上找到一个合适位置(i,j){ q[i]j;;}}
}int main()
{ int n; //n为存放实际皇后个数scanf(%d,n);if (n20)queen(1,n); //放置1i的皇后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(i1,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[MAXN]{0}; //存放物品重量,不用下标0元素
int v[MAXN]{0}; //存放物品价值,不用下标0元素
int x[MAXN]; //存放最终解
int maxv; //存放最优解的总价值
void dfs(int i,int tw,int tv,int rw,int op[]) //求解0/1背包问题
{int j;if (in) //找到一个叶子结点{ if () //找到一个满足条件的更优解,保存它{ maxvtv;for () //复制最优解x[j]op[j];}}else //尚未找完所有物品{ if () //左孩子结点剪枝满足条件时才放入第i个物品{op[i]1; //选取第i个物品dfs();}op[i]0; //不选取第i个物品,回溯if () //右孩子结点剪枝dfs();}
}
void dispasolution() //输出最优解
{ int i;for (i1;in;i)if (x[i]1)printf(%d ,i);printf(\n%d %d,W,maxv);
}
int main()
{int i;cinnW; //输入物体个数及背包载重量 for(int i1;in;i)//输入各物体重量及价值 cinw[i]v[i];int op[MAXN]; //存放临时解memset(op,0,sizeof(op));int rw0;for (int i1;in;i)rww[i];dfs(1,0,0,rw,op);dispasolution();return 0;
}输入格式: 第一行输入背包载重量W及背包个数n再依次输入n行每行为背包重量wi和价值vi。 输出格式: 第一行输出输出装入背包内的物体编号(末尾有空格)第二行输出背包内的物体总重量和总价值。 输入样例1: 5 10
2 6
2 3
6 5
5 4
4 6输出样例1: 1 2 3
10 14 第一空twW tvmaxv 第二空j1;jn;j 第三空tww[i]W 第四空i1,tww[i],tvv[i],rw-w[i],op 第五空twrwW 第六空i1,tw,tv,rw-w[i],op 5-8 0/1背包问题分支限界法 0/1背包问题。给定一载重量为m的背包及n个重量为wi、价值为vi的物体1≤i≤n,要求把物体装入背包使背包的物体价值最大。 输入格式: 第一行输入背包载重量m及背包个数n再依次输入n行每行为背包重量wi和价值vi。 输出格式: 第一行输出输出所求X[n]数组第二行输出装入背包内的物体的最大价值。 输入样例1: 5 10
2 6
2 3
6 5
5 4
4 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[MAXN1]; //重量下标0不用
int v[MAXN1]; //价值下标0不用
//求解结果表示
int maxv-9999; //存放最大价值,初始为最小值
int bestx[MAXN1]; //存放最优解,全局变量
int total1; //解空间中结点数累计,全局变量
struct NodeType //队列中的结点类型
{ int no; //结点编号int i; //当前结点在搜索空间中的层次int w; //当前结点的总重量int v; //当前结点的总价值int x[MAXN1]; //当前结点包含的解向量double ub; //上界
};void bound(NodeType e) //计算分枝结点e的上界
{int ie.i1;int sumwe.w;double sumve.v;while (){ sumww[i]; //计算背包已装入载重sumvv[i]; //计算背包已装入价值i;}if (in) e.ub;elsee.ubsumv;
}void EnQueue(NodeType e,queueNodeType qu) //结点e进队qu
{if (e.in) //到达叶子结点{if (e.vmaxv) //找到更大价值的解{;for (int j1;jn;j);}}else qu.push(e); //非叶子结点进队
}
void bfs() //求0/1背包的最优解
{int j;NodeType e,e1,e2; //定义3个结点queueNodeType qu; //定义一个队列e.i0; //根结点置初值其层次计为0e.w0; e.v0;e.nototal; for (j1;jn;j)e.x[j]0;bound(e); //求根结点的上界qu.push(e); //根结点进队while (!qu.empty()) //队不空循环{equ.front(); qu.pop(); //出队结点ee1.nototal; e1.ie.i1; //建立左孩子结点e1.we.ww[e1.i];e1.ve.vv[e1.i];for (j1;jn;j) //复制解向量e1.x[j]e.x[j];e1.x[e1.i]1;bound(e1); //求左孩子结点的上界 if () //剪枝检查左孩子结点{EnQueue(e1,qu); //左孩子结点进队操作}e2.nototal; //建立右孩子结点e2.ie.i1;e2.w; e2.v;for (j1;jn;j) //复制解向量e2.x[j]e.x[j];e2.x[e2.i];bound(e2); //求右孩子结点的上界if () //若右孩子结点可行,则进队,否则被剪枝EnQueue(e2,qu);}
}
int main()
{cinnW; //输入物体个数及背包载重量 for(int i1;in;i)//输入各物体重量及价值 cinw[i]v[i]; bfs(); //调用队列式分枝限界法求0/1背包问题for(int i1;in;i)printf(%d,bestx[i]);printf(\n%d,maxv);return 0;
} 第一空(sumww[i]W) in 第二空sumv(W-sumw)*v[i]/w[i] 第三空maxve.v 第四空bestx[j]e.x[j] 第五空e.ww[e.i1]We1.ubmaxv 第六空e.w 第七空e.v 第八空0 第九空e2.ubmaxv 5-9 部分背包问题贪心法 设有编号为1、2、…、n的n个物品它们的重量分别为w1、w2、…、wn价值分别为v1、v2、…、vn其中wi、vi1≤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; //pv/wfloat x;bool operator(const NodeType s) const{return ps.p; //按p递减排序}
};
NodeType A[MAXN]{{0}}; //下标0不用
//求解结果表示
double V; //最大价值
bool cmp(const NodeType a,const NodeType b)
{return a.nob.no;
}void Knap() //求解背包问题并返回总价值
{V0; //V初始化为0double weightW; //背包中能装入的余下重量int i1;while () { A[i].x1; //装入物品i; VA[i].v; //累计总价值; }if (weight0) //当余下重量大于0{ A[i].x;VA[i].x*A[i].v; //累计总价值}
}int main()
{ cinnW;for(int i1;in;i){cinA[i].noA[i].wA[i].v;A[i].x0;}for (int i1;in;i) //求v/wA[i].pA[i].v/A[i].w;sort(A1,An1); //排序Knap();sort(A1,An1,cmp);for(int j1;jn;j)coutA[j].no A[j].x*A[j].vendl;coutV;return 0;
} 输入格式: 第一行物品数n和背包容量W接着的n行中输入每个物品的编号重量和价值。 输出格式: 输出装入背包的物品信息共n行按物品编号递增排序的物品编号及重量物品编号从1开始。最后一行输出总价值。 输入样例1: 5 100
1 10 20
2 20 30
3 30 66
4 40 40
5 50 60输出样例1: 1 20
2 30
3 66
4 0
5 48
164 第一空A[i].wweight 第二空weight-A[i].w 第三空i 第四空weight/A[i].w 5-10 两个字符串的最长公共子序列长度 下面程序完成最长公共子序列的长度计算。 #includestdio.h
#includestring.h
#define N 80
int C[N][N]; // 记录最长公共子序列
int rec[N][N]; // 记录轨迹 int LCSLength(char *X, char *Y)
{ int i,j,mstrlen(X),nstrlen(Y);for(i 1; i m ; i) {for(j 1; j n; j) {if() {C[i][j] C[i-1][j-1] 1;rec[i][j] 1; //LU}else if() {C[i][j] C[i-1][j]; rec[i][j] 2; //U}else {C[i][j] ;rec[i][j] 3; //L}}}return C[m][n];
} 第一空X[i]Y[j] 第二空C[i-1][j]C[i][j-1] 第三空C[i][j-1]
