資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 查詢 N! 在 B 進製表示下的尾隨零個數
在這篇文章中，我們將瞭解如何找到給定數字 N 的階乘在 B 進製表示下的尾隨零個數的問題。例如
Input : N = 7 Base = 2 Output : 4 Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero. Input : N = 11 Base = 5 Output : 2 Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.
讓我們首先回顧一下將任何十進位制數從一個進位制轉換為另一個進位制的過程。讓我們以將 (5040)10 轉換為 (?)2 為例
即，將數字除以 2 並保留餘數，直到數字無法再被除為止。結果將是餘數的逆序。
因此，我們有 4 個尾隨零，當 2 除以該數字時餘數為 0，我們得到了這個尾隨零。
5040 的素因子分解 = 24 * 56711 * 3381 * 181，這意味著 2 除以 5040，餘數為 0，共 4 次，等於尾隨零的個數。透過這種方式，我們可以計算尾隨零的個數。
尋找解決方案的方法
我們上面討論了查詢尾隨零個數的方法。我們需要找到 N! 中 B 的最高冪，假設基數 B = 14，那麼 14 在 14 進位制下表示為 10，即 (14)10 = (10)14。這也被稱為勒讓德公式。
上述方法的 C++ 程式碼
這是我們可以用作輸入來解決給定問題的 C++ 語法：
示例
#include <bits/stdc++.h>
using namespace std;
vector < pair < int, int >> primeFactorsofBase(int Base) {
// declaring factors to store prime factors
// along with occurence in factorisation of Base .
vector < pair < int, int >>factors;
for (int i = 2; Base != 1; i++) {
if (Base % i == 0) {
int count = 0;
while (Base % i == 0){
Base = Base / i;
count++;
}
factors.push_back (make_pair (i, count));
}
}
return factors;
}
int main () {
int N = 11, Base = 5;
// finding the largest power of Base that divides factorial N.
vector < pair < int, int >>prime_factors;
// finding prime factors by primeFactorsofBase() function.
prime_factors = primeFactorsofBase(Base);
int result = INT_MAX;
for (int i = 0; i < prime_factors.size (); i++) {
// calculating minimum power.
int count = 0;
int r = prime_factors[i].first;
while (r <= N){
count += (N / r);
r = r * prime_factors[i].first;
}
result = min (result, count / prime_factors[i].second);
}
//printing trailing zeroes stored in result.
cout << "Number of trailing zeroes: " <<result;
return 0;
}輸出
Number of trailing zeroes: 2
上述程式碼的解釋
- 使用向量查詢基數的最大冪。
- 要計算最大冪，請使用向量計算素因子以儲存所有素因子。
- 然後計算基數的所有素因子的最小冪。
- 最後，列印結果。
結論
在這篇文章中，我們解決了查詢 N! 在 B 進製表示下的尾隨零個數的問題，我們使用勒讓德公式來解決這個問題。我們還編寫了 C++ 程式碼來解決同樣的問題。您可以使用其他語言（如 Java、C、Python 等）編寫此程式碼。希望您覺得這篇文章有所幫助。
更新於：2021年11月25日
224 次瀏覽
廣告