【无标题】

1. 两个序列的中位数

#include
#include 
#include 
int SearchMid(int A[], int B[],int n);
int main(void){
	int i ,j,g,g1,n;
	printf("请输入数组长度：\n");
	int len;
	scanf("%d",&len);
	printf("请输入数组范围: \n");
	int a,b; int c[len],c1[len];
	 scanf("%d%d",&a,&b);
	 srand(time(0));
	  for( i=0;i<len;i++)
    {
        c[i]=a+rand()%(b-a+1);
    for( g=0;g<i;g++){
	if(c[g]==c[i])
    i--;
    }
    }
     for( n=0;n<len;n++)
    {
        c1[n]=a+rand()%(b-a+1);
    for( g1=0;g<n;g1++){
	if(c1[g1]==c1[n])
    n--;
    }
    }
    	 printf("随机生成不重复数字的第一个数组为\n");
    for(i=0;i<len;i++){
        printf("%d ",c[i]);
    }
    	 printf("\n随机生成不重复数字的第二个数组为\n");
    for(i=0;i<len;i++){
        printf("%d ",c1[i]);
    }
	 printf("\n");
   int ans;
   ans=SearchMid(c,c1,len);
   printf("第一个数组和第二个数组的中位数为%d",ans);
   
}

int SearchMid(int A[], int B[],int n){
	int s1=0,e1=n-1,s2=0,e2=n-1;
	int mid1,mid2;
	while(s1<e1&&s2<e2){
		mid1=(s1+e1)/2;
		mid2=(s2+e2)/2;
		if(A[mid1]==B[mid2]) return A[mid1];
		if(A[mid1]<B[mid2]) {
			if((s1+e1)%2==0) s1=mid1;
			else s1= mid1+1;
			e2=mid2; 
		}
		else{
			if((s2+e2)%2==0) s2=mid2;
			else s2=mid2+1;
			e1=mid1;
		}
	}
	if(A[s1]<B[s2]) return A[s1];
	else return B[s2];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

2. TSP问题

#include
#include
#include 
#include 
#define INF 0
using namespace std;
int TSP(int arc[100][100] ,int n ,int w){
	int edgeCount=0,TSPLength=0;
	int min,u,v,j;
	int flag[n]={0};
	u=w;flag[w]=1;
	while(edgeCount<n-1){
		min=100;
		for(j=0;j<n;j++)

		
		 if( (flag[j]==0) && (arc[u][j]!=0) && (arc[u][j]<min) ){
			v=j;min=arc[u][j];
		}
		TSPLength+=min;
		flag[v]=1;edgeCount++;
		cout<<u+1<<"-->"<<v+1<<endl;
		u=v;
		
		}
		cout<<u+1<<"-->"<<w+1<<endl;
		return TSPLength+arc[u][w];
	}
	
	int main(void){
 	int n;
	printf("请输入点的个数: \n");
	scanf("%d",&n); 
		    //int max=0;
		    //int arc[100][100]={{max,3,3,2,6},{3,max,7,3,2},{3,7,max,2,5},{2,3,2,max,3},{6,2,5,3,max}};
			//int arc[n][n];
			//    arc[0][0]=INF; arc[0][1]=3;   arc[0][2]=3;   arc[0][3]=2;   arc[0][4]=6;
			//    arc[1][0]=3;   arc[1][1]=INF; arc[1][2]=7;   arc[1][3]=3;   arc[1][4]=2;
			//    arc[2][0]=3;   arc[2][1]=7;   arc[2][2]=INF; arc[2][3]=2;   arc[2][4]=5;
			//    arc[3][0]=2;   arc[3][1]=3;   arc[3][2]=2;   arc[3][3]=INF; arc[3][4]=3;
			//    arc[4][0]=6;   arc[4][1]=2;   arc[4][2]=5;   arc[4][3]=3;   arc[4][4]=INF;
  int a1,b1;
  int arc[100][100];
  printf("请输入随机邻接矩阵数值产生的范围：\n");
  scanf("%d%d",&a1,&b1);
 srand(time(0));
 printf("随机产生的邻接矩阵为：\n");
for(int ff=0;ff<n;ff++){
	for(int gg=0;gg<n;gg++){
		if(ff!=gg&&ff<gg) {
		arc[ff][gg]=a1+rand()%(b1-a1+1); arc[gg][ff]=arc[ff][gg];}
        printf("arc[%-d,%d]=%-5d ",ff,gg,arc[ff][gg]);
        if(gg==(n-1)) printf("\n");
}
	}
		printf("你输入了%d个顶点,顶点分别为: ",n);
	for(int i =0;i<n;i++){
	printf("%d ",i+1) ;
	}
	printf("\n---------------------------------\n请输入出发的顶点: \n") ;
	int t;
	scanf("%d",&t);
	printf("路径为： \n");
    int ans;
	ans = TSP(arc,n,t-1);
	printf("用贪心算法求得tsp问题的最短路径是：%d",ans);
	}
	
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

3 . 最小生成树问题

#include
#include
#include 
#include 
using namespace std;
int Prim(int arc[100][100],int n,int w){
	int i,j,k,min,minDist=0;
	int lowcost[n],adjvex[n];
	for(i=0;i<n;i++){
		lowcost[i]=arc[w][i];adjvex[i]=w;
		}
		lowcost[w]=0;
		for(i=0;i<n-1;i++){
			min=100;
			for(j=0;j<n;j++){
				if((lowcost[j]!=0) && (lowcost[j]<min))
				{
					min=lowcost[j];k=j;
				}
			}
			cout<<adjvex[k]<<"--"<<k<<endl;
			minDist=minDist+lowcost[k];
			lowcost[k]=0;
			for(j=0;j<n;j++){
				if(arc[k][j]<lowcost[j]){
	
			lowcost[j]=arc[k][j];adjvex[j]=k;
		} 
	}
}
	return minDist;
}
int main(void){
//	int max =0;
//	int arc[100][100]={{max,3,3,2,6},{3,max,7,3,2},{3,7,max,2,5},{2,3,2,max,3},{6,2,5,3,max}};
    	int n;
	printf("请输入点的个数: \n");
	scanf("%d",&n); 
	
	int a1,b1;
  int arc[100][100];
  printf("请输入随机邻接矩阵数值产生的范围：\n");
  scanf("%d%d",&a1,&b1);
 srand(time(0));
 printf("随机产生的邻接矩阵为：\n");
for(int ff=0;ff<n;ff++){
	for(int gg=0;gg<n;gg++){
		if(ff!=gg&&ff<gg) {
		arc[ff][gg]=a1+rand()%(b1-a1+1); arc[gg][ff]=arc[ff][gg];}
        printf("arc[%-d,%d]=%-5d ",ff,gg,arc[ff][gg]);
        if(gg==(n-1)) printf("\n");
}
	}
		printf("你输入了%d个顶点,顶点分别为: ",n);
	for(int i =0;i<n;i++){
	printf("%d ",i) ;
	}
	printf("\n---------------------------------\n请输入出发的顶点: \n") ;
	int t;
	scanf("%d",&t);
	printf("最小生成树的路径为：\n") ;
    int m =Prim(arc,5,t); 
    printf("最小生成树的代价为%d \n",m);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65