数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中 N 次切割的最大片段数
给定任务是计算通过总共 N 次水平或垂直切割给定正方形，可以获得的最大相同大小的正方形或矩形片段的数量。
现在让我们用一个例子来理解我们必须做什么 -
输入 - N=8
输出 - 25
解释 - 当 N=8 时，垂直切割数 = 4，水平切割数 = 4。
总片段数 = 25
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 |
输入 - 7
输出 - 20
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 |
下面程序中使用的方案如下
如果 N 是切割次数，并且我们必须最大化生成的片段，则必须进行相同数量的水平和垂直切割。
如果 N 是偶数，则将有相等的水平和垂直切割；否则，如果 N 是奇数，则水平切割将比垂直切割多 1 次，反之亦然。
因此，水平切割数 = N/2，垂直切割数 = N-H。
在 MaxPieces() 函数中，初始化一个 int 类型的变量 H =N/2 来存储水平切割数。
初始化另一个 int 类型的变量 V=N-H 来存储垂直切割数。
最终片段数 = (水平行数)*(垂直行数) = (H+1)*(V+1)
示例
#include <bits/stdc++.h>
using namespace std;
int MaxPieces(int N){
//H is the number of horizontal cuts
int H = N / 2;
//V is the number of vertical cuts
int V = N-H;
// maximum number of pieces = (H+1)*(V+1)
return ((H + 1) * (V + 1));
}
//Main function
int main(){
//Number of cuts
int N = 7;
cout << "Max pieces = "<<MaxPieces(N);
return 0;
}输出
如果我们运行以上代码，我们将得到以下输出 -
20
更新于: 2020-08-17
642 次浏览
广告