正方形分成16份，将1到16填入其中。让行和列都是从大到小。问一共有多少种方法？...

看了到面试题：

将正方形分成16份，将1到16填入其中。让行和列都是从大到小。问一共有多少种方法？

此题 解法有：

1。 穷举，基本不用考虑 复杂度O(16！）。

2。 枚举+剪枝 。代码如下：得到答案是 24024

3。个人觉得 有简单方法 再想想

方法2 代码如下

#define MAX 4
int max_v(int i,int j)
{
    return (MAX +1 -i)*(MAX+1 - j)  -1;
}
bool is_select(int i,unsigned int stat)
{
    return stat&(1<<(i-1));
}
void select(int i ,unsigned int * stat)
{
    *stat = *stat|(1<<(i-1));
}
int count(int i ,int j,int s[MAX+1][MAX+1] ,unsigned int stat)
{
    int max1;
    if (s[i-1][j] > s[i][j-1]) 
        max1 = s[i][j-1];
    else 
        max1 = s[i-1][j];
    int min1 = max_v(i,j);
    //(max1 min1)
    if(min1>=max1-1) return 0;
    int count_n = 0;
    for (int k = min1+1;k<max1;k++)
    {
        if(!is_select(k,stat))
        {
            unsigned int ss = stat;
            select(k,&ss);
            s[i][j] = k;
            int a,b;
            a=i;b=j;
            if (b==MAX)
            {
                if (a == MAX)
                {
                    return 1;
                }
                b= 1;
                a++; 
            }
            else
            {
                b++;
            }
            count_n = count_n + count(a,b,s,ss);
        }
    }
    return count_n;
}
void main()
{
    int f[MAX+1][MAX+1];
    for (int i = 0;i<MAX+1;i++)
    {
        f[0][i] = f[i][0] = MAX*MAX +1;
    }

    unsigned int t = 0;
    cout<<count(1,1,f,t);
}

 

 

转载于:https://www.cnblogs.com/davidluo/articles/1799365.html

总结

以上是生活随笔为你收集整理的正方形分成16份，将1到16填入其中。让行和列都是从大到小。问一共有多少种方法？...的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。