期末算法分析程序填空題

目錄

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]; pivotkey=L.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(low<high){                                        pivotloc=;;;}
}void QuickSort(SqList &L)
{QSort(L,1,L.length);
}void Create_Sq(SqList &L)
{int i,n;cin>>n;    //輸入的值不大于 MAXSIZEfor(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)if(i==1) cout<<L.r[i].key;elsecout<<" "<<L.r[i].key;
}int main()
{SqList L;L.r=new ElemType[MAXSIZE+1];L.length=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[high].key >= pivotkey

第三空：low < high && L.r[low].key <= pivotkey

第四空：Partition(L,low,high)

第五空：QSort(L,low,pivotloc-1)

第六空：QSort(L,pivotloc+1,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;cin>>n;    //輸入的值不大于 MAXSIZEfor(i=1;i<=n;i++){cin>>L.r[i].key;L.length++;}
}
void show(SqList L)
{int i;for(i=1;i<=L.length;i++)if(i==1) cout<<L.r[i].key;elsecout<<" "<<L.r[i].key;
}void Merge(ElemType R[],ElemType T[],int low,int mid,int high)
{ int i,j,k;i=low; j=mid+1;k=low; while(i<=mid&&j<=high){                     if(R[i].key<=R[j].key) T[k++]=R[i++]; else T[k++]=R[j++]; } while(i<=mid)T[k++]=R[i++];                 while(j<=high)T[k++]=R[j++];                       
} void MSort(ElemType R[],ElemType T[],int low,int high)
{ int mid;ElemType *S=new ElemType[MAXSIZE];if(low==high) ; else{ mid=(low+high)/2;;; ;} 
} void MergeSort(SqList &L)
{ MSort(L.r,L.r,1,L.length); 
} int main()
{SqList R;R.r=new ElemType[MAXSIZE+1];R.length=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[low]=R[low]

第二空：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[MAX][MAX];
void solve()                    //求dp
{int i,j;for (i=1;i<=a.length();i++) dp[i][0]=i;            //把a的i個字符全部刪除轉換為bfor (j=1; j<=b.length(); j++)dp[0][j]=j;            //在a中插入b的全部字符轉換為bfor (i=1; i<=a.length(); i++)for (j=1; j<=b.length(); j++){if (a[i-1]==b[j-1]);elsedp[i][j]=;}
}
int main()
{    cin>>a>>b;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.e<b.e;                //按結束時間遞增排序
}int n;                            //訂單個數
NodeType A[MAX];    //存放訂單
//求解結果表示
int dp[MAX];                    //動態規劃數組
int pre[MAX];                    //pre[i]存放前驅訂單編號
void solve();int main()
{cin>>n;for(int i=0;i<n;i++)cin>>A[i].b>>A[i].e;for (int i=0; i<n; i++)A[i].length=A[i].e-A[i].b;solve();cout<<dp[n-1]; return 0;
}void solve()                    //求dp和pre
{memset(dp,0,sizeof(dp));    //dp數組初始化stable_sort(A,A+n,cmp);        //采用穩定的排序算法dp[0]=A[0].length;pre[0]=-1;for (int i=1;i<n;i++){int low=0, high=i-1;while(low<=high)        //在A[0..i-1]中查找結束時間早于A[i]開始時間的最晚訂單A[low-1]{int mid=(low+high)/2;if(A[mid].e<=A[i].b)low=mid+1;elsehigh=mid-1;}if (low==0)                //特殊情況{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 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)            //k=1～i-1是已放置了皇后的行{    if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)));k++;};
}void queen(int i,int n)            //放置1～i的皇后
{    if (i>n) dispasolution(n);        //所有皇后放置結束else{for (int j=1;j<=n;j++)        //在第i行上試探每一個列jif ()            //在第i行上找到一個合適位置(i,j){    q[i]=j;;}}
}int main()
{    int n;                    //n為存放實際皇后個數scanf("%d",&n);if (n<=20)queen(1,n);                //放置1～i的皇后return 0;
}

輸入格式:

輸入n。

輸出格式:

按行輸出每組解。

輸入樣例1:

輸出樣例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[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 (i>n)                    //找到一個葉子結點{    if ()     //找到一個滿足條件的更優解,保存它{    maxv=tv;for ()    //復制最優解x[j]=op[j];}}else                        //尚未找完所有物品{    if ()          //左孩子結點剪枝：滿足條件時才放入第i個物品{op[i]=1;            //選取第i個物品dfs();}op[i]=0;                //不選取第i個物品,回溯if ()            //右孩子結點剪枝dfs();}
}
void dispasolution()            //輸出最優解
{    int i;for (i=1;i<=n;i++)if (x[i]==1)printf("%d ",i);printf("\n%d %d",W,maxv);
}
int main()
{int i;cin>>n>>W; //輸入物體個數及背包載重量 for(int i=1;i<=n;i++)//輸入各物體重量及價值 cin>>w[i]>>v[i];int op[MAXN];                //存放臨時解memset(op,0,sizeof(op));int rw=0;for (int i=1;i<=n;i++)rw+=w[i];dfs(1,0,0,rw,op);dispasolution();return 0;
}

輸入格式:

第一行輸入背包載重量W及背包個數n，再依次輸入n行，每行為背包重量wi和價值vi。

輸出格式:

第一行輸出輸出裝入背包內的物體編號(末尾有空格)，第二行輸出背包內的物體總重量和總價值。

輸入樣例1:

輸出樣例1:

1 2 3 
10 14

第一空：tw==W && tv>maxv

第二空：j=1;j<=n;j++

第三空：tw+w[i]<=W

第四空：i+1,tw+w[i],tv+v[i],rw-w[i],op

第五空：tw+rw>W

第六空：i+1,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:

輸出樣例1:

11001
15

輸入樣例2:

輸出樣例2:

00
0

#include <stdio.h>
#include <queue>
#include <iostream>
using namespace std;
#define MAXN 20                        //最多可能物品數
//問題表示
int n,W;
int w[MAXN+1];                //重量，下標0不用
int v[MAXN+1];                  //價值，下標0不用
//求解結果表示
int maxv=-9999;                        //存放最大價值,初始為最小值
int bestx[MAXN+1];                    //存放最優解,全局變量
int total=1;                        //解空間中結點數累計,全局變量
struct NodeType                        //隊列中的結點類型
{    int no;                            //結點編號int i;                            //當前結點在搜索空間中的層次int w;                            //當前結點的總重量int v;                            //當前結點的總價值int x[MAXN+1];                    //當前結點包含的解向量double ub;                        //上界
};void bound(NodeType &e)            //計算分枝結點e的上界
{int i=e.i+1;int sumw=e.w;double sumv=e.v;while (){    sumw+=w[i];                //計算背包已裝入載重sumv+=v[i];                //計算背包已裝入價值i++;}if (i<=n)    e.ub=;elsee.ub=sumv;
}void EnQueue(NodeType e,queue<NodeType> &qu)    //結點e進隊qu
{if (e.i==n)                    //到達葉子結點{if (e.v>maxv)            //找到更大價值的解{;for (int j=1;j<=n;j++);}}else qu.push(e);            //非葉子結點進隊
}
void bfs()                            //求0/1背包的最優解
{int j;NodeType e,e1,e2;                //定義3個結點queue<NodeType> qu;                //定義一個隊列e.i=0;                            //根結點置初值，其層次計為0e.w=0; e.v=0;e.no=total++; for (j=1;j<=n;j++)e.x[j]=0;bound(e);                        //求根結點的上界qu.push(e);                        //根結點進隊while (!qu.empty())                //隊不空循環{e=qu.front(); qu.pop();        //出隊結點ee1.no=total++; e1.i=e.i+1;                //建立左孩子結點e1.w=e.w+w[e1.i];e1.v=e.v+v[e1.i];for (j=1;j<=n;j++)        //復制解向量e1.x[j]=e.x[j];e1.x[e1.i]=1;bound(e1);                //求左孩子結點的上界        if  ()        //剪枝：檢查左孩子結點{EnQueue(e1,qu);            //左孩子結點進隊操作}e2.no=total++;                //建立右孩子結點e2.i=e.i+1;e2.w=; e2.v=;for (j=1;j<=n;j++)            //復制解向量e2.x[j]=e.x[j];e2.x[e2.i]=;bound(e2);                    //求右孩子結點的上界if ()                //若右孩子結點可行,則進隊,否則被剪枝EnQueue(e2,qu);}
}
int main()
{cin>>n>>W; //輸入物體個數及背包載重量 for(int i=1;i<=n;i++)//輸入各物體重量及價值 cin>>w[i]>>v[i];    bfs();                    //調用隊列式分枝限界法求0/1背包問題for(int i=1;i<=n;i++)printf("%d",bestx[i]);printf("\n%d",maxv);return 0;
}

第一空：(sumw+w[i]<=W) && i<=n

第二空：sumv+(W-sumw)*v[i]/w[i]

第三空：maxv=e.v

第四空：bestx[j]=e.x[j]

第五空：e.w+w[e.i+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=v/wfloat x;bool operator<(const NodeType &s) const{return p>s.p;            //按p遞減排序}
};
NodeType A[MAXN]={{0}};    //下標0不用
//求解結果表示
double V;                        //最大價值
bool cmp(const NodeType &a,const NodeType &b)
{return a.no<b.no;
}void Knap()                        //求解背包問題并返回總價值
{V=0;                        //V初始化為0double weight=W;            //背包中能裝入的余下重量int i=1;while ()    {    A[i].x=1;                    //裝入物品i;            V+=A[i].v;                //累計總價值;    }if (weight>0)                //當余下重量大于0{    A[i].x=;V+=A[i].x*A[i].v;            //累計總價值}
}int main()
{   cin>>n>>W;for(int i=1;i<=n;i++){cin>>A[i].no>>A[i].w>>A[i].v;A[i].x=0;}for (int i=1;i<=n;i++)            //求v/wA[i].p=A[i].v/A[i].w;sort(A+1,A+n+1);                //排序Knap();sort(A+1,A+n+1,cmp);for(int j=1;j<=n;j++)cout<<A[j].no<<" "<<A[j].x*A[j].v<<endl;cout<<V;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].w<=weight

第二空：weight-=A[i].w

第三空：i++

第四空：weight/A[i].w

5-10?兩個字符串的最長公共子序列長度

下面程序完成最長公共子序列的長度計算。

#include<stdio.h>
#include<string.h>
#define N 80
int C[N][N];   // 記錄最長公共子序列 
int rec[N][N]; // 記錄軌跡 int LCSLength(char *X, char *Y) 
{   int i,j,m=strlen(X),n=strlen(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];
}