Nhiệm vụ được giao là tìm số lượng lớn nhất các số 0 ở cuối trong tích của các tập con có kích thước K, của một mảng cho trước có kích thước N.
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 - Arr [] ={5, 20, 2}, K =2
Đầu ra - 2
Giải thích - Có thể tạo tổng cộng 3 tập con có kích thước =2.
Tích của [5, 20] là 100.
Tích của [20, 2] là 40.
Tích của [5, 2] là 10.
100 có số lượng số không ở cuối tối đa =2. Do đó 2 là câu trả lời.
Đầu vào - Arr [] ={60, 40, 25}, K =2
Đầu ra - 3
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Trước khi bắt đầu các chức năng, hãy #define M5 100 ở trên cùng.
-
Trong hàm MaxZeros (), tạo mảng 2D Sub [K + 1] [M5 + 5] và khởi tạo từng giá trị của nó bằng -1 và đặt Sub [0] [0] =0;
-
Vòng lặp từ P =0 cho đến P
-
Bắt đầu vòng lặp while với điều kiện while (Arr [P]% 2 ==0) và bên trong vòng lặp thực hiện P2 ++ và Arr [P] / 2 để thu được số lượng 2s. Lặp lại bước tương tự cho P5.
-
Sau đó, bên trong vòng lặp For bắt đầu ở trên khởi tạo thêm hai vòng lặp for lồng nhau như sau -
for (int i =K - 1; i> =0; i--)
for (int j =0; j
-
Bên trong các vòng này, hãy kiểm tra xem (Sub [i] [j]! =-1) và nếu nó là true thì đặt Sub [i + 1] [j + P5] =max (Sub [i + 1]; [j + P5 ], Sub [i] [j] + P2);
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define M5 100
int MaxZeros(int* Arr, int N, int K){
//Initializing each value with -1;
int Sub[K+1][M5+5];
memset(Sub, -1, sizeof(Sub));
Sub[0][0] = 0;
for (int P = 0; P < N; P++){
int P2 = 0, P5 = 0;
// Maximal power of 2 in Arr[P]
while (Arr[P] % 2 == 0){
P2++;
Arr[P] /= 2;
}
// Maximal power of 2 in Arr[P]
while (Arr[P] % 5 == 0) {
P5++;
Arr[P] /= 5;
}
/* We can collect 2s by checking first i numbers and taking their j with total power of 5*/
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
// If subset[i][j] is not calculated.
if (Sub[i][j] != -1)
Sub[i + 1][j + P5] = max(Sub[i + 1][j + P5], Sub[i][j] + P2);
}
/* Taking minimum of 5 or 2 and maximizing the result*/
int ans = 0;
for (int i = 0; i < M5; i++)
ans = max(ans, min(i, Sub[K][i]));
return ans;
}
//Main function
int main(){
int Arr[] = { 60, 40, 25 };
int K = 2;
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << MaxZeros(Arr, N, K);
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 -
3