使用 C++ 查詢 N! 在 16 進製表示中的尾隨零個數

在本文中，我們將瞭解如何解決查詢給定數字 N 的階乘在 16 進製表示中尾隨零個數的問題，例如：

Input : N = 7
Output : 1
Explanation : fact(7) = 5040 in base10 and 13B0 in base16 having 1 trailing zero.

Input : N = 11
Output : 2
Explanation : fact(11) = 39916800 in base10 and 2611500 in base16 having 2 trailing zeroes.

讓我們首先回顧一下將任何十進位制數從一個進位制轉換為另一個進位制的過程；讓我們以將 (5040)10 轉換為 (?)16 為例

即，將數字除以 16 並保留餘數，直到數字無法再被除為止。結果將是餘數的反序。

因此，我們得到一個尾隨零，當 16 除以該數字時餘數為 0，我們就得到了這個尾隨零。

5040 的質因數分解 = 16¹ * 4⁵¹* 7¹, 這意味著 16 除以 5040 餘數為 0，等於尾隨零的個數。透過這種方式，我們可以計算尾隨零的個數。

解決方法

我們上面討論了查詢尾隨零個數的方法。我們也知道 16 = 2⁴，這意味著 N 除以四得到的最高次冪 2 將等於 16 的最高次冪。這也被稱為勒讓德公式。

上述方法的 C++ 程式碼

這是一個我們可以用作輸入來解決給定問題的 C++ 語法：

示例

#include <bits/stdc++.h>
using namespace std;

int main () {
   int n = 11;
   long long int count = 0;
   long long int value, power = 2;
   long long int result;

   do{
      value = n / power;
      count += value;
      power *= 2;
   }
   while (value != 0);

   // Count has the highest power of 2
   result = count / 4;
   cout << "Number of trailing zeroes in base 16 representation of N : " << result;
}

輸出

Number of trailing zeroes in base 16 representation of N: 2

上述程式碼的解釋

  • 我們用 2 初始化 power，因為我們需要計算 2 的最高次冪。
  • 在一個 while 迴圈中實現勒讓德公式，我們用初始值為 2 的 power 除以 n，並用該值遞增 count，用 2 遞增 power。
  • 用 4 除以儲存在 count 變數中的 2 的最高次冪之後。
  • 最後，我們列印結果。

結論

在本文中，我們解決了查詢 N 的階乘在 16 進製表示中尾隨零個數的問題，我們使用勒讓德公式解決了這個問題。我們還編寫了 C++ 程式碼來解決同一個問題。您可以使用其他語言（如 Java、C、Python 等）編寫此程式碼。我們希望您覺得這篇文章有所幫助。

更新於：2021-11-25

瀏覽量：144

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告