資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中子集大小為 k 的乘積中尾隨零的最大數量
給定任務是找到給定大小為 N 的陣列的 K 個大小的子集乘積中尾隨零的最大數量。
現在讓我們用一個例子來理解我們必須做什麼 -
輸入 - 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() 中建立一個二維陣列 Sub[K + 1][M5 + 5] 並將其每個值初始化為 -1 並設定 Sub[0][0] = 0;
從 P=0 迴圈到 P<N，並在迴圈內初始化型別為 int 的 P2 = 0 和 P5 = 0，分別用於儲存給定數字中 2 和 5 的數量。
啟動一個 while 迴圈，條件為 while(Arr[P]%2 == 0)，並在迴圈內執行 P2++ 和 Arr[P]/2 以獲得 2 的數量。對 P5 重複相同的步驟。
然後在上面開始的 For 迴圈內初始化另外兩個巢狀的 for 迴圈，如下所示 -
for (int i = K - 1; i >= 0; i--)
for (int j = 0; j < M5; j++)
在這些迴圈內檢查 if(Sub[i][j] != -1)，如果為真，則將 Sub[i + 1][j + P5] = max(Sub[i + 1];[j + P5], Sub[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
更新於: 2020-08-17
183 次瀏覽
廣告