[数据结构与算法]算法设计与分析（多边游戏、图像压缩、电路布线）

算法设计与分析（多边游戏、图像压缩、电路布线）

多边游戏代码部分：
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int N,m[105][105][2],v[105]; 
char op[105];
void MinMax(int n,int i,int s,int j,int &minf,int &maxf);
int PloyMax(int n,int& p);
int main() 
{  
	int p;
	cout<<"请输入多边形顶点数："<<endl;
	cin>>N;
	for(int i=1; i<=N; i++)
	{
		cout<<"请输入多边形顶点"<<i<<"数值:"<<endl;
		cin>>v[i];  
		m[i][1][0]=v[i];  
		m[i][1][1]=v[i]; 
		cout<<"请输入多边形边"<<i<<"运算符:"<<endl;
		cin>>op[i];   
	} 
	cout<<"多边形游戏首次删除第"<<p<<"条边，结果为："<<PloyMax(N,p)<<endl; 
	return 0;
}
void minMax(int n,int i, int s, int j, int*minf, int*maxf){
	int a,b,c,d,r; 
	a = m[i][s][0];
	b = m[i][s][1]; 
	r = (i+s)%n; 
	c = m[r][j-s][0]; 
	d = m[r][j-s][1]; 
	if(op[r] == '+'){
		*minf = a+c; 
		*maxf = b+d; 
	}
	else{ 
		int e[5];
        e[1]=a*c;
        e[2]=a*d;
        e[3]=b*c;
        e[4]=b*d;
        *minf=e[1];
        *maxf=e[1];
        for(r=2;r<5;r++){
            if(*minf>e[r]) *minf=e[r];
            if(*maxf<e[r]) *maxf=e[r];
        }
	} 
}
int PloyMax(int n,int& p){ 
	int minf, maxf; 
	for(int j=2; j<=n; j++) {
		for(int i=1; i<=n; i++) {
			for(int s=1; s<j; s++) {
				minMax(n, i, s, j, &minf, &maxf); 
				if(m[i][j][0]>minf) m[i][j][0]=minf; 
				if(m[i][j][1]<maxf) m[i][j][1]=maxf; 
			} 
		} 
	}
	int temp=m[1][n][1];
	p=1; 
	for(int i=2 ;i<=n; i++) { 
		if(temp<m[i][n][1]) {
			temp=m[i][n][1]; p=i;
		} 
	}
	return temp; 
}

图像压缩代码部分：
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int N = 7;  
int length(int i);  
void Compress(int n,int p[],int s[],int l[],int b[]);  
void Tracebace(int n,int& i,int s[],int l[]);  
void Output(int s[],int l[],int b[],int n);
int main(){
    int p[] = {200,200,100,150,1,5,100};
    int s[N],l[N],b[N];  
    cout<<"图像的灰度序列为："<<endl;
    for(int i=1;i<N;i++){  
        cout<<p[i]<<" ";  
    }  
    cout<<endl;
    Compress(N-1,p,s,l,b);  
    Output(s,l,b,N-1);  
    return 0;  
}
void Compress(int n,int p[],int s[],int l[],int b[]) { 
	int Lmax = 256,header = 11; s[0] = 0; 
	for(int i=1; i<=n; i++) { 
		b[i] = length(p[i]);
		int bmax = b[i]; s[i] = s[i-1] + bmax; l[i] = 1; 
		for(int j=2; j<=i && j<=Lmax;j++) { 
			if(bmax<b[i-j+1]) {
				bmax = b[i-j+1];
			} 
			if(s[i]>s[i-j]+j*bmax) { 
				s[i] = s[i-j] + j*bmax; 
				l[i] = j; 
			} 
		}
		s[i] += header; 
	} 
}
void Traceback(int n,int& i,int s[],int l[]) { 
	if(n==0) return; 
	Traceback(n-l[n],i,s,l); 
	s[i++]=n-l[n];
}
int length(int i){  
    int k=1;  
    i = i/2;  
    while(i>0){  
        k++;  
        i=i/2;  
    }  
    return k;  
}
void Output(int s[],int l[],int b[],int n){  
    cout<<"图像压缩后的最小空间为："<<s[n]<<endl;  
    int m = 0;  
    Traceback(n,m,s,l);  
    s[m] = n;  
    cout<<"将原灰度序列分成"<<m<<"段序列段"<<endl;  
    for(int j=1; j<=m; j++){  
        l[j] = l[s[j]];  
        b[j] = b[s[j]];  
    }  
    for(int j=1; j<=m; j++){  
        cout<<"段长度："<<l[j]<<",所需存储位数:"<<b[j]<<endl;  
    }  
}

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int N = 10;
void MNS(int C[],int n,int **size);
void Traceback(int C[],int **size,int n,int Net[],int& m);
int main(){
	int c[] = {0,8,7,4,2,5,1,9,3,10,6};//0互相对应 
	int **size = new int *[N+1];
	for(int i=0; i<=N; i++){
		size[i] = new int[N+1];
	}
	MNS(c,N,size);
	cout<<"电路布线最大不相交连线数目为："<<size[N][N]<<endl;
	int Net[N],m;
	Traceback(c,size,N,Net,m);
	cout<<"最大不相交连线分别为："<<endl;
	for(int i=m-1; i>=0; i--){
		cout<<"("<<Net[i]<<","<<c[Net[i]]<<") ";
	}
	cout<<endl;
	return 0;
}
void MNS(int C[],int n,int **size) { 
	for(int j=0;j<C[1];j++) size[1][j]=0; 
	for(int j=C[1]; j<=n; j++) size[1][j]=1; 
	for(int i=2; i<n; i++) { 
		for(int j=0; j<C[i]; j++) { 
			size[i][j]=size[i-1][j];
		}
		for(int j=C[i]; j<=n; j++) { 
			size[i][j]=max(size[i-1][j],size[i-1][C[i]-1]+1); 
		} 
	}
	size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1); 
}
void Traceback(int C[],int **size,int n,int Net[],int& m) { 
	int j=n;
	m=0; 
	for(int i=n;i>1;i--) { 
		if(size[i][j]!=size[i-1][j]){ 
			Net[m++]=i; 
			j=C[i]-1;
		} 
	}
	if(j>=C[1]){ 
		Net[m++]=1; 
	} 
}