Số mảnh tối đa trong N vết cắt trong C ++

Nhiệm vụ được giao là tính toán số lượng tối đa các mảnh hình vuông hoặc hình chữ nhật có kích thước bằng nhau có thể có được bằng cách cắt một mảnh hình vuông nhất định trong tổng số N vết cắt theo chiều ngang hoặc chiều dọc.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -

Đầu vào - N =8

Đầu ra - 25

Giải thích - Khi N =8 thì số vết cắt dọc =4 và số vết cắt ngang =4.

Tổng số mảnh =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

Đầu vào - 7

Đầu ra - 20

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nếu N là số lần cắt và chúng ta phải tối đa hóa các miếng kết quả thì số lần cắt ngang và dọc bằng nhau phải được thực hiện.

Nếu N chẵn thì sẽ có các vết cắt ngang và dọc bằng nhau, còn nếu N lẻ thì các vết cắt ngang sẽ nhiều hơn 1 vết cắt dọc hoặc ngược lại.

Do đó, số lần cắt ngang =N / 2 và số lần cắt dọc =N-H.
Trong hàm MaxPieces (), hãy khởi tạo một biến H =N / 2 kiểu int để lưu trữ số lần cắt ngang.
Khởi tạo một biến khác V =N-H kiểu int để lưu trữ số lần cắt dọc.
Số mảnh cuối cùng =(Hàng ngang) * (Hàng dọc) =(H + 1) * (V + 1)

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -