关于在寻找n*m格子内正方形和长方形的数量的问题 |
您所在的位置：网站首页 › 一共有八个帽子 › 关于在寻找n*m格子内正方形和长方形的数量的问题 |
|
关于在寻找n*m格子内正方形和长方形的数量的问题 本人有两种方法，一种是暴力枚举法，另外一种则是主要依靠公式法，以下只提供主要的部分代码： 第一种，暴力枚举法： ∵正方形长等于宽 ∴子正方形构成的矩阵的长宽由原矩形长宽减去相同数而得 即(n-b)*(m-a) (a=b) #include using namespace std; long long n,m,rec,sqr; int main() { cin>>n>>m; for(int i=0; i long long temp; if(*a>*b){ temp=*a; *a=*b; *b=temp; } return 0; } int find(long long a,long long b){ for(long long i=1;i sum2+=b-i+1; } changemax(&a,&b); //调用方法，使N，M两边更小的一边为N，而大的一边为M。 for(long long i=a;i>=0;i--){ zhen+=i*b; //又一条公式，表示出来就是正方形的数量总是等于“递减的小边”与“递减的大边”的乘积的总和，一直加加加直到小边N边为0。具体原理网上一搜就有。 b--; } chang=sum1*sum2-zhen; //易知N和M各自的有效边之乘积就是图形总数量。 return 0; } //该方法的思路就是先得出所有图形的数量，再用公式得到正方形的数量，然后相减得到长方形的数量。缺点就是用到公式，难啊难；优点就是时间复杂性大幅降低，一般不会运行超时。代码如上，欢迎讨论。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |