PTA算法测试题（程序填空）
1 棋盘覆盖问题
#include
#include
#include
#define MAX 1025
using namespace std;
int board[MAX][MAX];
int tile=1;
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{ if(size==1
) return; //递归出口
int t=tile++; //取一个L型骨，其牌号为tile
int s=size/2; //分割棋盘
//考虑左上角象限
if(dr
ChessBoard(tr,tc,dr,dc,s)
;
else //此象限中无特殊方格
{ board[tr+s-1][tc+s-1]=t
; //用t号L型骨牌覆盖右下角
ChessBoard(tr,tc,tr+s-1,tc+s-1,s)
; //将右下角作为特殊方格继续处理该象限
}
//考虑右上角象限
if(dr
)
ChessBoard(tr,tc+s,dr,dc,s)
; //特殊方格在此象限中
else //此象限中无特殊方格
{ board[tr+s-1][tc+s]=t
; //用t号L型骨牌覆盖左下角
ChessBoard(tr,tc+s,tr+s-1,tc+s,s)
; //将左下角作为特殊方格继续处理该象限
}
//处理左下角象限
if(dr>=tr+s&&dc
ChessBoard(tr+s,tc,dr,dc,s)
;
else //此象限中无特殊方格
{ board[tr+s][tc+s-1]=t
; //用t号L型骨牌覆盖右上角
ChessBoard(tr+s,tc,tr+s,tc+s-1,s)
; //将右上角作为特殊方格继续处理该象限
}
//处理右下角象限
if(dr>=tr+s&&dc>=tc+s
) //特殊方格在此象限中
ChessBoard(tr+s,tc+s,dr,dc,s)
;
else //此象限中无特殊方格
{ board[tr+s][tc+s]=t
; //用t号L型骨牌覆盖左上角
ChessBoard(tr+s,tc+s,tr+s,tc+s,s)
; //将左上角作为特殊方格继续处理该象限
}
}
int main()
{
int dr,dc,size;
int j,i;
cin>>size;
cin>>dr>>dc;
ChessBoard(0,0,dr,dc,size);
for(i=0;i
cout<
cout<
cout<
return 0;
}
2 快速排序
#include
#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(
low ) { while( low ) --high; L.r[low]=L.r[high]; while( low ) ++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 { pivotloc= Partition(L,low,high) ; QSort(L,low,pivotloc-1) ; QSort(L,pivotloc+1,high) ; } } void QuickSort(SqList &L) { QSort(L,1,L.length); } void Create_Sq(SqList &L) { int i,n; cin>>n; //输入的值不大于 MAXSIZE for(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< else cout<<" "< } int main() { SqList L; L.r=new ElemType[MAXSIZE+1]; L.length=0; Create_Sq(L); QuickSort(L); show(L); return 0; } 3 归并排序 #include #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; //输入的值不大于 MAXSIZE for(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< else cout<<" "< } 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) T[low]=R[low] ; else { mid=(low+high)/2; MSort(R,S,low,mid) ; MSort(R,S,mid+1,high) ; Merge(S,T,low,mid,high) ; } } 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; } 4 部分背包问题（贪心法） #include #include #include #include using namespace std; #define MAXN 51 //问题表示 int n; double W; //限重 struct NodeType { int no; double w; double v; double p; //p=v/w float 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 } void Knap() //求解背包问题并返回总价值 { V=0; //V初始化为0 double weight=W; //背包中能装入的余下重量 int i=1; while ( A[i].w<=weight ) { A[i].x=1; //装入物品i weight-=A[i].w ; V+=A[i].v; //累计总价值 i++ ; } if (weight>0) //当余下重量大于0 { A[i].x= weight/A[i].w ; 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/w A[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< cout< return 0; } 5 最小生成树（普里姆算法） #include #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 && closedge[i].lowcost != 0 ){ 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 = u ; closedge[j].lowcost = G.arcs[k][j] ; } } closedge[k].lowcost = 0 ; for(i = 1; i < G.vexnum; ++i){ k = Min(G) ; u0 = closedge[k].adjvex; v0 = G.vexs[k]; cout << u0 << "->" << v0 << endl; closedge[k].lowcost = 0 ; for(j = 0; j < G.vexnum; ++j) if(G.arcs[k][j] < closedge[j].lowcost){ closedge[j].adjvex = G.vexs[k] ; closedge[j].lowcost = G.arcs[k][j] ; } } } int main(){ AMGraph G; CreateUDN(G); char u; cin >> u; MiniSpanTree_Prim(G , u); return 0; } 6 求解活动安排问题（贪心法） #include #include #include #include using namespace std; #define MAX 51 //问题表示 struct Action { int b; //活动起始时间 int e; //活动结束时间 bool operator<(const Action &s) const //重载<关系函数 { return e<=s.e; //用于按活动结束时间递增排序 } }; int n; Action A[MAX]; bool flag[MAX]; //标记选择的活动 int Count=0; //选取的兼容活动个数 void solve() //求解最大兼容活动子集 { memset(flag,0,sizeof(flag));//初始化为false sort(A,A+n); //A[1..n]按活动结束时间递增排序 int preend=0; //前一个兼容活动的结束时间 for (int i=0;i { if ( A[i].b>=preend ) { flag[i]=true ; preend=A[i].e ; } } } int main() { cin>>n; for (int i=0;i cin>>A[i].b>>A[i].e; solve(); for (int i=0;i if (flag[i]) { printf("[%d,%d]\n",A[i].b,A[i].e); Count++; } cout< return 0; } 7 多段图问题（动态规划法） #include using namespace std; const int N = 20; const int MAX = 1000; int arc[N][N]; int Backpath(int n); int creatGraph(); int main() { int n = creatGraph( ); int pathLen = Backpath(n); cout< return 0; } int creatGraph() { int i, j, k; int weight; int vnum, arcnum; cin>>vnum>>arcnum; for (i = 0; i < vnum; i++) for (j = 0; j < vnum; j++) arc[i][j] = MAX; for (k = 0; k < arcnum; k++) { cin>>i>>j>>weight; arc[i][j] = weight; } return vnum; } int Backpath(int n) { int i, j, temp; int cost[N]; int path[N]; for(i = 0; i < n; i++) { cost[i] = MAX; path[i] = -1; } cost[0] = 0; for(j = 1; j < n; j++) { for(i = j - 1; i >= 0; i--) { if ( arc[i][j] + cost[i] < cost[j] ) { cost[j] = arc[i][j] + cost[i] ; path[j] = i; } } } return cost[n-1] ; } 8 最短路径（弗洛伊德算法） #include using namespace std; #define MaxInt 32767 #define MVNum 100 typedef char VerTexType; typedef int ArcType; int Path[MVNum][MVNum]; int D[MVNum][MVNum]; typedef struct{ VerTexType vexs[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; int LocateVex(AMGraph G , VerTexType v);//实现细节隐藏 void CreateUDN(AMGraph &G);//实现细节隐藏 void ShortestPath_Floyed(AMGraph G){ int i , j , k ; for (i = 0; i < G.vexnum; ++i) for(j = 0; j < G.vexnum; ++j){ D[i][j] = G.arcs[i][j] ; if(D[i][j] < MaxInt && i != j) Path[i][j]=i ; else Path [i][j] = -1; } for(k = 0; k < G.vexnum; ++k) for(i = 0; i < G.vexnum; ++i) for(j = 0; j < G.vexnum; ++j) if( D[i][k] + D[k][j] < D[i][j]){ D[i][j] = D[i][k]+D[k][j] ; Path[i][j] = Path[k][j] ; } } void DisplayPath(AMGraph G , int begin ,int temp ){ if(Path[begin][temp] != -1){ DisplayPath(G , begin ,Path[begin][temp]); cout << G.vexs[Path[begin][temp]] << "->"; } } int main(){ AMGraph G; char start , destination; int num_start , num_destination; CreateUDN(G); ShortestPath_Floyed(G); cin >> start >> destination; num_start = LocateVex(G , start); num_destination = LocateVex(G , destination); DisplayPath(G , num_start , num_destination); cout << G.vexs[num_destination]< cout << D[num_start][num_destination]; return 0; } 9 求解图的m着色问题（回溯法） #include #include #define MAXN 20 //图最多的顶点个数 int n,k,m; int a[MAXN][MAXN]; int count=0; //全局变量，累计解个数 int x[MAXN]; //全局变量，x[i]表示顶点i的着色 bool Same(int i) //判断顶点i是否与相邻顶点存在相同的着色 { for (int j=1;j<=n;j++) if ( a[i][j]==1 && x[i]==x[j] ) return false; return true; } void dfs(int i) //求解图的m着色问题 { if (i>n) { count++ ; } else { for (int j=1;j<=m;j++) { x[i]=j; if ( Same(i) ) dfs(i+1); x[i]=0 ; } } } int main() { memset(a,0,sizeof(a)); //a初始化 memset(x,0,sizeof(x)); //x初始化 int x,y; scanf("%d%d%d",&n,&k,&m); //输入n,k,m for (int j=1;j<=k;j++) { scanf("%d%d",&x,&y); //输入一条边的两个顶点 a[x][y]=1; //无向图的边对称 a[y][x]=1; } dfs(1); //从顶点1开始搜索 if (count>0) //输出结果 printf("%d",count); else printf("-1"); return 0; } 10 0/1背包问题（回溯法） #include #include #include #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 ( tw==W && tv>maxv ) //找到一个满足条件的更优解,保存它 { maxv=tv; for ( j=1;j<=n;j++ ) //复制最优解 x[j]=op[j]; } } else //尚未找完所有物品 { if ( tw+w[i]<=W ) //左孩子结点剪枝：满足条件时才放入第i个物品 { op[i]=1; //选取第i个物品 dfs( i+1,tw+w[i],tv+v[i],rw-w[i],op ); } op[i]=0; //不选取第i个物品,回溯 if ( tw+rw>W ) //右孩子结点剪枝 dfs( i+1,tw,tv,rw-w[i],op ); } } 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; } 11 求解n皇后问题（递归回溯法） #include #include #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 { 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为存放实际皇后个数 scanf("%d",&n); if (n<=20) queen(1,n); //放置1～i的皇后 return 0; }本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
