小弟我也来贴个有关问题，算是头脑风暴

我也来贴个问题，算是头脑风暴~
先上50分，如果有好的解答再加。

  Q1：一个由m*n个方格组成的矩形，将其切割为若干个矩形，共有多少种切割方法？记方案数为f(m,n)，一个例子：
  例如下面这个3*5的矩形切成右边这种形状就是一种方案，右边相同数字组成一个矩形
  ##### 11122
  ##### -> 34445
  ##### 34446

  另有：完全不切割也算一种方案；不考虑旋转、翻转后的重复情况；定义f(0,n) = f(m,0) = 1

  Q2：上承Q1，如果问题比较难的话，试求f(1,n)和f(2,n)

  Q3：上承Q1，可能是Q1的中间步骤，也可能是扩展问题，即将m*n的矩形切割成k个子矩形有多少种切割方法？
  记为f(m,n,k)

[解决办法]
f(1,n)= C(1, n-1)+C(2, n-1)+...+C(n-1,n-1) = 2^(n-1)-1;

[解决办法]
f(1,n)或f(m,1)可以当成是整数分拆的问题……
而且是有序的整数分拆：
http://courseware.ecnudec.com/zsb/zsx/zsx09/zsx096/zsx09601/zsx096011.htm
推广到f(m,n)可能会比较困难……
[解决办法]
f(n,n)=f(1,n-1)*f(1,n)*2 = (2^(n-2)-1)*(2^(n-1)-1)*2 

[解决办法]
f(1,n)理解起来比较容易，就是n个块排成一列，有n-1个分割，从1个分割一直取到n-1分割。
[解决办法]
先在矩形中任取一点，然后再取和第一点不同行，不同列的一点，就可以组成一个矩形，这样应该是
f{m,n} = m*n*(m-1)(n-1)/4
不知道是不是符合题意
[解决办法]
n的有序k-分拆数是
k可以取的值为1、2、...、n
所以：
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
[解决办法]
f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
f(m,n)=[2^(n-1)]^m
[解决办法]
又想了想，应该是:
f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。
解释一下我的想法：
原先是个n*(m-1)的矩阵，那么加一个1*n的矩阵，就变成了n*n。
所以至少有f(n,n-1)×f(1,n)。
在n*m的矩阵中，新增的1*n放在最右边（放在最左边是对称的）。即为第m列，其左边一列为m-1列。
m-1列内（不和其它列组成矩形）的每种分布，m列都会有一种情况和其对应，这时可以把m-1、m2列的行连接在一起，变成一个新的组合。
所以这又增加了f(n,m-2)*f(1,n)。
最后f(n,m)=（f(n,m-1)+f(n,m-2))*f(1,n) n>=3。

[解决办法]

探讨

f(1,n)=C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)=2^(n-1)
f(m,n)=[2^(n-1)]^m

[解决办法]
另(1+x)^n = C(0,n)+C(1,n)x+...+C(n,n)x^n. （10多年以前学的二项式展开定理）
上式可以简化为
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*(((1+2)^m)-1)/2
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2
有时间的话，写个程序验证一下。

上面的f(1,n)公式写错了，9楼的是对了。
[解决办法]
f(3,2) 应该和 f(2, 3)相等

所以 [2^(n-1)]^m 这种结论不可能相等 因为2^3 != 3^2
[解决办法]

探讨

f(3,2) 应该和 f(2, 3)相等

所以 [2^(n-1)]^m 这种结论不可能相等 因为2^3 != 3^2

[解决办法]
关于[2^(n-1)]^m有以下的图（m=n=2）：


whg01的递推方法思路很好……
用m=n=2来验证是对的：
f(n,m)=f(n,m-1)*f(1,m)+f(n,m-2)*((3^m)-1)/2 

f(2,2)=f(2,1)*f(1,2)+f(2,0)*((3^2)-1)/2【f(2,1)=2，f(1,2)=2，f(2,0)=1】
=2*2+(9-1)/2
=4+4=8
[解决办法]
这题按楼上诸位的思路是无法解出来的，我找到了别人的研究成果，有一个公式可以计算，具体自己去看论文吧
http://www.math.lsu.edu/~verrill/research/rectangles.pdf
[解决办法]
摘自论文中的部分结果，首行和首列分别对应n和m,如f(1,2) = 2 ,f(3,4)= 3164

1 2 3
1 1 2 4

2 2 8 34
3 4 34322
4 8 148 3164
5 16650 31484
6 322864 314662
7 6412634 3149674
[解决办法]
在google中输入 dividing rectangles into rectangles ,第一个结果On dividing rectangles into rectangles 就是这篇paper

探讨

引用:
这题按楼上诸位的思路是无法解出来的，我找到了别人的研究成果，有一个公式可以计算，具体自己去看论文吧
http://www.math.lsu.edu/~verrill/research/rectangles.pdf

打不开啊……顺便请教下是怎么搜到的这篇paper呢？

[解决办法]
把论文的结果搬运过来……

【公式】


【例子】

[解决办法]
在矩形中任意不同的两点就可以分割成一个矩形，总共有M*N个点，可以有M*N*(M*N-1),去掉重复对称情况为
M*N*(M*N-1)/2
在去掉在一行或一列上的两个点的情况，总共有M*C(N,2)+N*C(M,2)
所以可以分割的矩形数量为M*N*(M*N-1)/2-M*C(N,2)-N*C(M,2)

[解决办法]

探讨

在矩形中任意不同的两点就可以分割成一个矩形，总共有M*N个点，可以有M*N*(M*N-1),去掉重复对称情况为
M*N*(M*N-1)/2
在去掉在一行或一列上的两个点的情况，总共有M*C(N,2)+N*C(M,2)
所以可以分割的矩形数量为M*N*(M*N-1)/2-M*C(N,2)-N*C(M,2)

[解决办法]
【程序】

C/C++ code

#include <stdio.h>void fun(int n){//f(1,n)    int i,j,n_f;    for(i=1,n_f=1;i<n;i++) n_f*=2;    for(i=0;i<n_f;i++){        printf("┌");        for(j=0;j<n-1;j++){            if(i&(1<<j)) printf("┬");            else printf("─");        }        printf("┐\n└");        for(j=0;j<n-1;j++){            if(i&(1<<j)) printf("┴");            else printf("─");        }        printf("┘\n");    }}int main(){    fun(5);    return 0;}
[解决办法]
Q2:
f(2,n)=f(1,n)*2+C(1,n)+C(3,n)+C(4,n)+C(5,n)+...++C(n,n)

     =3*2^n-3-2n-((n-1)n)/2


Q3:

可以用计算机么     设成数组  
a[1,1].....a[1,n]
.       .      .
.       .      .
.       .      .
a[m,1]......a[n,n]

遇到下标为0的跳转
用for循环计算  单项下表相同的count++
[解决办法]
【程序】
C/C++ code
#include <stdio.h>#include <stdlib.h>#include <string.h>int M2[2][2]={2,1,1,4};void myprintf(int *s,int *p,int m,int n,int c){    int i,j;    int k,l,t,t2;    printf("┌");    for(i=0;i<n-1;i++){        if(*(s+p[i]*3+1)==1) printf("┬");        else printf("─");    }    printf("┐\n");    for(j=0;j<m-1;j++){        if(*(s+3*c*(j+1)+p[0]*3)==1) printf("├");        else printf("│");        for(i=0;i<n-1;i++){            k=*(s+3*c*j+p[i]*3+1);            l=*(s+3*c*(j+1)+p[i]*3+1);            t=*(s+3*c*(j+1)+p[i]*3);            t2=*(s+3*c*(j+1)+p[i]*3+2);            if(k==0&&l==0&&t==0&&t2==0) printf("　");            else if(k==0&&l==0&&t==1&&t2==1) printf("─");            else if(k==0&&l==1&&t==1&&t2==1) printf("┬");            else if(k==1&&l==0&&t==1&&t2==1) printf("┴");            else if(k==1&&l==1&&t==0&&t2==0) printf("│");            else if(k==1&&l==1&&t==0&&t2==1) printf("├");            else if(k==1&&l==1&&t==1&&t2==0) printf("┤");            else if(k==1&&l==1&&t==1&&t2==1) printf("┼");        }        if(*(s+3*c*(j+1)+p[n-2]*3+2)==1) printf("┤\n");        else printf("│\n");    }        printf("└");    for(i=0;i<n-1;i++){        if(*(s+3*c*(m-1)+p[i]*3+1)==1) printf("┴");        else printf("─");    }    printf("┘\n");}int fun(int m,int n){    int a[2][2]={2,1,1,4};    int b[2];    int c,cc;    int i,j,k,l,t,t2,m_f;    int *s,*p;    int x;    if(m<2||n<2){        printf("error: m<2||n<2!\n");return -1;    }    for(i=1,m_f=1;i<m;i++) m_f*=2;    for(i=0;i<m-2;i++){        b[0]=a[0][0]*M2[0][0]+a[0][1]*M2[1][0];        b[1]=a[0][0]*M2[0][1]+a[0][1]*M2[1][1];        a[0][0]=b[0];a[0][1]=b[1];        b[0]=a[1][0]*M2[0][0]+a[1][1]*M2[1][0];        b[1]=a[1][0]*M2[0][1]+a[1][1]*M2[1][1];        a[1][0]=b[0];a[1][1]=b[1];    }    c=a[0][0]+a[0][1]+a[1][0]+a[1][1];    s=(int*)malloc(sizeof(int)*m*3*c);    t=0;t2=0;    for(i=0;i<m_f;i++){        for(j=0;j<m_f;j++){            *(s+t*3)=i;            *(s+t*3+2)=j;            for(l=0;l<m-1;l++){                if(i&(1<<l)) *(s+3*c*(l+1)+t*3)=1;                else *(s+3*c*(l+1)+t*3)=0;            }            for(l=0;l<m-1;l++){                if(j&(1<<l)) *(s+3*c*(l+1)+t*3+2)=1;                else *(s+3*c*(l+1)+t*3+2)=0;            }            t2=t;            for(k=0;k<m_f*2;k++){                if(t2!=t){                    *(s+t*3)=i;                    *(s+t*3+2)=j;                    for(l=0;l<m-1;l++){                        if(i&(1<<l)) *(s+3*c*(l+1)+t*3)=1;                        else *(s+3*c*(l+1)+t*3)=0;                    }                    for(l=0;l<m-1;l++){                        if(j&(1<<l)) *(s+3*c*(l+1)+t*3+2)=1;                        else *(s+3*c*(l+1)+t*3+2)=0;                    }                    t2=t;                }                for(l=0;l<m;l++){                    if(k&(1<<l)) *(s+3*c*l+t*3+1)=1;                    else *(s+3*c*l+t*3+1)=0;                }                for(l=0;l<m-1;l++){                    if(*(s+3*c*(l+1)+t*3)!=*(s+3*c*(l+1)+t*3+2)){                        if(*(s+3*c*l+t*3+1)!=1) break;                        if(*(s+3*c*(l+1)+t*3+1)!=1) break;                    }else if(*(s+3*c*(l+1)+t*3)==0){                        if(*(s+3*c*l+t*3+1)!=*(s+3*c*(l+1)+t*3+1)) break;                    }                }                if(l==m-1) t++;                if(t==c) break;            }            if(t==c) break;        }        if(t==c) break;    }    x=n-1;    p=(int*)malloc(sizeof(int)*x);    memset(p,0,sizeof(int)*x);    k=0;t=1;cc=0;    while(1){        for(i=0;i<x-1;i++){            if(*(s+p[i]*3+2)!=*(s+p[i+1]*3)) break;        }        if(i==x-1){            myprintf(s,p,m,n,c);cc++;        }        if(p[0]==c-1){            for(i=1;i<x;i++) if(p[i]!=c-1) break;            if(i==x) break;            p[i]++;            for(i=i-1;i>=0;i--) p[i]=0;        }else p[0]++;    }    free(s);free(p);    return cc;}int main(){    printf("\nf(3,3)=%d\n",fun(3,3));    return 0;} 
  

 

查看更多 下一篇