ภารกิจคือการค้นหาจำนวนสูงสุดของศูนย์ต่อท้ายในผลคูณของชุดย่อยของขนาด K ของอาร์เรย์ขนาด N ที่กำหนด
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -
ป้อนข้อมูล − Arr[] ={5, 20, 2} , K=2
ผลลัพธ์ − 2
คำอธิบาย − สามารถสร้างเซตย่อยได้ทั้งหมด 3 เซ็ต โดยมีขนาด =2
ผลคูณของ [5, 20] คือ 100
ผลคูณของ [20, 2] คือ 40
ผลคูณของ [5, 2] คือ 10
100 มีจำนวนศูนย์ต่อท้ายสูงสุด =2 ดังนั้น 2 คือคำตอบ
ป้อนข้อมูล − Arr[] ={60, 40, 25} , K=2
ผลผลิต − 3
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ก่อนเริ่มฟังก์ชั่น #define M5 100 ที่ด้านบน
-
ในฟังก์ชัน MaxZeros() ให้สร้างอาร์เรย์ 2 มิติ Sub[K + 1][M5 + 5] และกำหนดค่าเริ่มต้นแต่ละค่าด้วย -1 และตั้งค่า Sub[0][0] =0;
-
วนจาก P=0 จนถึง P
-
เริ่มต้นการวนซ้ำแบบมีเงื่อนไข while(Arr[P]%2 ==0) และภายในลูป ให้ทำ P2++ และ Arr[P]/2 เพื่อให้ได้จำนวน 2 วินาที ทำขั้นตอนเดิมซ้ำสำหรับ P5
-
จากนั้นในข้างต้นเริ่มต้นสำหรับลูปเริ่มต้นอีกสองซ้อนกันสำหรับลูปดังนี้ −
สำหรับ (int i =K - 1; i>=0; i--)
สำหรับ (int j =0; j
-
ภายในลูปเหล่านี้ตรวจสอบว่าถ้า(Sub[i][j] !=-1) และถ้าเป็นจริงให้ใส่ Sub[i + 1][j + P5] =max(Sub[i + 1);[j + P5 ], ซับ[i][j] + P2);
ตัวอย่าง
#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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
3
