bacmive


私信TA

用户名:bacmive

访问量:19730

签 名:

努力、奋斗

等  级
排  名 299
经  验 5601
参赛次数 0
文章发表 36
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:参考题号1110题 “2^k进制数”
参考代码:

#include <stdio.h>

int a[7][7];
int b[7];//记录矩阵的每一行最多移动的次数
int n;

int max()//求出每次移动一行之后的矩阵的“列元素和”最大值
{
    int i,j,tmp,res=-1;
    for(j=0;j<n;j++)
    {
        tmp=0;
        for(i=0;i<n;i++)
            tmp +=a[i][j];
        if(tmp>res) res=tmp;
    }
    return res;
}


void move(int i)//移动矩阵第i行
{
    int k,j,tmp;
    tmp=a[i][n-1];
    for(j=n-1;j>0;j--)
        a[i][j]=a[i][j-1];
    a[i][0]=tmp;
}


int main()
{
    int i,j,k,min,m;
    while(scanf("%d",&n)&&n>0)
    {
        //初始化
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                scanf("%d",a[i]+j);
        for(i=0;i<n;i++)
            b[i]=1;
        min=100000;

        int flag=1;
        while(flag){
            flag=0;
            for(i=n-1;i>=0;i--){
                if(b[i]<=n)
                {
                    b[i]++;
                    move(i);
                    m=max();
                    if(m<min) min=m;
                    for(k=i+1;k<n;k++)
                        b[k]=1;
                    flag=1;
                    break;
                }
            }
        }
        printf("%d\n",min);
    }
    return 0;
}


 

0.0分

2 人评分

  评论区

我有些看不懂地方就是这个循环能同时让多行移动吗,毕竟有可能答案是多行移动后的结果。而原代码似乎只是从下往上只移动一行?如果有大佬懂请私信告诉我。用户名:Monkey
2022-08-25 17:23:23
刚开始看到if里面的for循环不懂,然后按照程序顺序走一遍才明白过来,但是作者思路和大部分人不一样,我们一直以为是最下面一行开始,移动一次,则上面的每一行就要移动n次,但是作者的思路却是上面的每移动一次,下面的每一行就要移动n次。如果是这样的话,那就多移动了n^n次,因为从最后一行开始移动,只有移动到第二行的时候才能算是完结。那么从最后一行移到第二行就已经完结了,但是作者的是第二行又重新做了一次全排列,相当于做了两次全排列。所以如果可以的话,尽量用递归调用,而不用这样的方法先排列到递归的结束条件再重新排一遍。
2021-06-06 14:09:51
  • «
  • 1
  • »