数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告