資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中陣列乘積中尾隨零的個數
給定一個大小為 N 的正整數陣列 Arr[]。目標是計算陣列所有元素的乘積中存在的尾隨零的個數。
我們將透過計算每個數字的因子來做到這一點。我們將 2 和 5 作為每個數字的因子進行計數，因為 2 和 5 的乘積是 10，它產生 1 個尾隨 0。最後，較小的計數決定了乘積中尾隨零的個數。如果我們有 4 個 2 和 6 個 5，那麼乘積中將有 4 個尾隨零 - 2*2*2*2*5*5*5*5*5*5= 250000
讓我們透過示例來理解。
輸入
Arr[] = { 2, 5, 10, 15, 20, 25, 100 }輸出
Number of trailing zeroes : 6
解釋
Factors 2 and 5 of each element of Arr[]: Arr[0] = 2 : 2 twos=1, fives=0 Arr[1] = 5 : 5 twos=1, fives=1 Arr[2] = 10 : 2*5 twos=2, fives=2 Arr[3] = 15 : 3*5 twos=2, fives=3 Arr[4] = 20 : 2*2*5 twos=4, fives=4 Arr[5] = 25 : 5*5 twos=4, fives=6 Arr[6] = 100 : 2*2*5*5 twos=6, fives=8 Count of 2 is less so trailing zeroes will be 6.
輸入
Arr[] = { 10,10,10,10,10 }輸出
Number of trailing zeroes : 5
解釋
Factors 2 and 5 of each element of Arr[]: Arr[0] = 10 : 2*5 twos=1, fives=1 Arr[1] = 10 : 2*5 twos=2, fives=2 Arr[2] = 10 : 2*5 twos=3, fives=3 Arr[3] = 10 : 3*5 twos=4, fives=4 Arr[4] = 10 : 2*5 twos=5, fives=5 Count of 2 and 5 is equal so trailing zeroes will be 5.
下面程式中使用的方案如下
我們獲取一個長度為 N 的正整數陣列。
函式 trailZeros(int arr[],int n) 以陣列和 n 作為輸入，並返回所有元素乘積中尾隨零的個數。
將初始變數 count 設為 0，表示零的個數。
將兩個變數 twos 和 fives 作為因子中 2 和 5 的個數。
使用 for 迴圈遍歷陣列。
對於每個元素，如果它可以被 2 或 5 整除，則遞增 twos 和 fives，並將其分別減少 2 或 5。
在 for 迴圈結束時，檢查 twos 和 fives 的值，取較小的那個。
將 count 初始化為兩者中較小的那個。
返回 count 作為結果。
示例
#include <bits/stdc++.h<
using namespace std;
int trailZeros(int arr[],int n){
int count = 0;
int twos = 0;
int fives = 0;
for (int i = 0; i < n; i++){
while(arr[i]%2==0 || arr[i]%5==0){
if(arr[i]%2==0){
arr[i]=arr[i]/2;
twos++;
}
if(arr[i]%5==0){
arr[i]=arr[i]/5;
fives++;
}
}
}
count=twos<fives?twos:fives;
return count;
}
int main(){
int Arr[]={ 12, 5 , 15, 8, 100, 40 };
int Length= sizeof(Arr)/sizeof(Arr[0]);
cout <<endl<< "Number of trailing zeroes : "<<trailZeros(Arr,Length);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Number of trailing zeroes : 5
更新於: 2020-10-31
293 次瀏覽
廣告