解题思路:
1.假设二维数组为 N=3
0 1 2 H=0 代表行：第一行
3 4 5 H=1
6 7 8 H=2
H=3，没有这行，结束；
注意：以下程序使用了一维数组代替二维数组：(因为刚开始用全排列做的，一维数组直接把全排列搬过来就可，之后换方法就没改）
每一行的第一个元素，在一维数组中的下标为[H*N];
每行的最后一个元素，在一位数组中的下表为[H*N+N-1],即：[(H+1)*N-1]
以下是递归关系：（得到所有不同矩阵）
（1）.到第三行（最后一行）右移N(N=3)次，每次得到一个新的矩阵，每得到一个矩阵，求其最大值；
（2）.到第二行移动三次，每移动一次，做一遍（1）；
（3）.到第一行移动三次，每移动一次，做一遍（2）；
优化：
因为
1 0 2 和 0 1 2
4 3 5 3 4 5
7 6 8 6 7 8 .....是一样的
所以第一行可以不用右移动；若不能理解的话，把所有的写出来，看看；
递归关系简化为：
（1）.到第三行（最后一行）右移N(N=3)次，每次得到一个新的矩阵，每得到一个矩阵，求其最大值；
（2）.到第二行移动三次，每移动一次，做一遍（1）；
注意，简化后，因为第一行没有排序，当输入N=1的时候，不能得出结果（具体看函数），所以当N==1时，结果单独输出；
if(N==1)//N==1直接输出结果，原因向下看
printf("%d\n",A[0]);
else //否则进行排列递归，从第二行开始
{
pailie(A,N,1); //1表示从第二行开始移动（因为优化第一行不移动了），当N等于1时，看下面pailie
//实现，H==N，直接就返回了，所以N==1在上面单独输出
free(A);
printf("%d\n",comax_min);
}递归实现；
void pailie(int *A,int N,int H)
{
if(H==N) //当H==N，看上面例子，可以知道，前面已经到最后一行，所以返回上一个函数
return;
for(int j=0;j<N;j++) //每一行移动N次
{
pailie(A,N,H+1); //递归到下一行
int t=A[N*(H+1)-1]; //记录这一行的最后一个元素
for(int i=N*(H+1)-1;i>N*H;i--) //移动
A[i]=A[i-1];
A[N*H]=t;
Colmax(A,N); //求矩阵的最大值，同时里面会记录所有矩阵最大值的最小一个
}
return ;
}参考代码:
#include<stdio.h>
#include<malloc.h>
int comax_min;
void pailie(int *A,int N,int H);
void input(int *A,int N);
void Colmax(int *A,int N);
int main()
{
int *A;
int N;
while(scanf("%d",&N)&&N!=-1)
{
comax_min=100000;
A=(int *)malloc((N*N)*sizeof(int));
input(A,N*N);
if(N==1)
printf("%d\n",A[0]);
else
{
pailie(A,N,1);
free(A);
printf("%d\n",comax_min);
}
}
return 0;
}
/*===================================================*/
void input(int *A,int N)
{
for(int i=0;i<N;i++)
scanf("%d",&A[i]);
}
/*===================================================*/
void pailie(int *A,int N,int H)
{
if(H==N)
return;
for(int j=0;j<N;j++)
{
pailie(A,N,H+1);
int t=A[N*(H+1)-1];
for(int i=N*(H+1)-1;i>N*H;i--)
A[i]=A[i-1];
A[N*H]=t;
Colmax(A,N);
}
return ;
}
/*===================================================*/
void Colmax(int *A,int N) //求矩阵的最大值，并且求出所有矩阵中最大值最小的一个
{
int max,sum=0;
for(int j=0;j<N;j++) //先求第一例的和
sum+= A[j*N];
max=sum; //让最大值先等于第一列的和
for(int i=1;i<N;i++) //再求后面的列的和
{ sum=0;
for(int k=0;k<N;k++)
{
sum+=A[k*N+i];
}
if(max<sum) //后面列的和更大，则更行max
max=sum;
}
if(comax_min>max) //记录所有矩阵最大值中最小的一个
comax_min=max;
}下面介绍全排列法以上方法就是它来的：（此方法仅供观赏，测试电脑性能）
同样把除了第一行以外的行，做全排列；
0 1 2 H=0 代表行：第一行
3 4 5 H=1
6 7 8 H=2
把第二行做全排列，每得到一种排列，转向排列它的下一行，（同样每得到一种排列，排列它的下一行）；若是最后一行，排列这一行，每一种排列求出这个矩阵的最大值。
//整个实现过程就是全排列里面，加上递归全排列，和求矩阵最大值
void pailie(int *A,int index,int length,int H,int N)
{
int j=0;
if(index==length) //得到一种排列
{
if(H==N-1) //看是不是最后一行
Colmax(A,N); //是最后一行，求矩阵最大值
else
pailie(A,(H+1)*N,(H+2)*N,H+1,N); //不是最后一行，递归下一行
}
else
for(j = index;j < length; j++)
{
swap(&A[j],&A[index]);
pailie(A,index+1,length,H,N);
swap(&A[j],&A[index]);
}
return ;
}参考代码：
#include<stdio.h>
#include<malloc.h>
int comax_min=0;
void pailie(int *A,int index,int length,int H,int N);
void swap(int *x,int *y);
void input(int *A,int N);
void Colmax(int *A,int N);
int main()
{
int *A;
int N;
while(scanf("%d",&N)&&N!=-1)
{
comax_min=100000;
A=(int *)malloc((N*N)*sizeof(int));
if(N==1)
{
input(A,N*N);
printf("%d\n",A[0]);
}
else
{
input(A,N*N);
pailie(A,1*N,N+N,1,N);
printf("%d\n",comax_min);
}
}
return 0;
}
/*===================================================*/
void input(int *A,int N)
{
for(int i=0;i<N;i++)
scanf("%d",&A[i]);
}
/*===================================================*/
void pailie(int *A,int index,int length,int H,int N)
{
int j=0;
if(index==length)
{
if(H==N-1)
Colmax(A,N);
else
pailie(A,(H+1)*N,(H+2)*N,H+1,N);
}
else
for(j = index;j < length; j++)
{
swap(&A[j],&A[index]);
pailie(A,index+1,length,H,N);
swap(&A[j],&A[index]);
}
return ;
}
/*===================================================*/
void Colmax(int *A,int N)
{
int max,sum=0;
for(int j=0;j<N;j++)
sum+= A[j*N];
max=sum;
for(int i=1;i<N;i++)
{ sum=0;
for(int k=0;k<N;k++)
{
sum+=A[k*N+i];
}
if(max<sum)
max=sum;
}
if(comax_min>max)
comax_min=max;
}
/*===================================================*/
void swap(int *x,int *y)
{
int z=(*x);
(*x)=(*y);
(*y)=z;
return ;
}别忘点赞哦-.-
0.0分
7 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复