Nの基数16表現で後続ゼロの数を見つけます！ C++を使用する

この記事では、たとえば階乗の基数16の表現で特定の数Nの後続ゼロを見つける問題を理解します

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.

まず、10進数を1つの基数から別の基数に変換するプロセスを要約します。 （5040）10を（？）16に変換する例を見てみましょう

つまり、数値を16で除算し、数値をそれ以上除算できなくなるまで余りを保持します。結果は逆の順序で残りになります。

その結果、末尾のゼロが1つあり、16で数値を余り0で割ったときに得られるこの末尾のゼロ。

5040の素因数分解=161* 451 * 71は、16が5040を1回除算し、余りが0で、末尾のゼロに等しいことを意味します。このようにして、後続ゼロの数を計算できます。

解決策を見つけるためのアプローチ

末尾のゼロの数を見つける方法については、上記で説明しました。また、16 =24であることがわかっています。これは、Nの最大累乗2を4で割ると、最大累乗の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を計算する必要があるため、電力を2で初期化しています。
• ルジャンドルの公式をwhileループに実装します。ここでは、nを最初は2の累乗で除算し、カウントを値で除算し、累乗を2で除算します。
• 2の最大の累乗を4で割った後、カウント変数に格納されます。
• 最終的に結果を印刷します。

結論

この記事では、階乗Nのbase16表現で後続ゼロの数を見つける問題を解決します。これは、ルジャンドルの公式を使用して解決します。同じ問題を解決するためにC++コードも記述します。このコードは、Java、C、Pythonなどの他の言語で記述できます。この記事がお役に立てば幸いです。