階乗関連のアルゴリズムとその C++ 実装

階乗とは、必要な数値が得られるまで 1 × 2 × 3 × 4 を掛け合わせることを意味します。 C++の階乗についても同様です。階乗アルゴリズムに関連する側面は 2 つあります。1 つは高精度の計算であり、もう 1 つは数論に関連しています。

1つ。 高精度で階乗を計算する

これは実際には最も技術的な問題ではありませんが、頻繁に使用されるため、記述して最適化する必要があります。

まず、12 以下の階乗計算を見てみましょう (計算結果は 32 ビットの範囲を超えません)。

 int 階乗(int n) {
 ( n == 1 || n == 0)の場合
1 を返します。
階乗(n-1)*nを返します。
 } 
 

この再帰プログラムはシンプルで明確であり、非常に直感的です。ただし、n > 12 になると、32 ビット int 型の範囲を超え、誤った結果が発生します。したがって、上記の再帰プログラムは、n <= 12 の階乗計算にのみ適しています。より大きな n の階乗を計算するには、階乗計算に高精度の乗算アルゴリズムを組み込む必要があります。高精度の乗算プロセスは、次のように簡単に説明できます。(ここで、A * B = C、A[0]、B[0]、C[0] はそれぞれ長さを格納します)

 ( i = 1 ; i < = A[0]; i++)の場合
( j = 1 ; j < = B[0]; j++) の場合 {
 C[i+j-1] += A[i]*B[j]; // 現在の i+j-1 に対応する項目 + A[i] * B[j]
 C[i+j] += C[i+j-1]/10; // 次の桁 + 商（繰り上がり）
 C[i+j-1] %= 10; // 余りとして計算できる
}
 C[0] = A[0] + B[0];
 while (C[0] > 1 && C[C[0]] == 0) C[0]--; // 先頭の0を削除してCの実際の長さを取得します

この高精度の乗算により、階乗の計算は単純に繰り返し実行できます。

(i = 2; i <= n; i++) の場合 {

i を文字配列に変換します。

高精度の乗算を実行します。前の結果にiを掛けます。

}

二。 数論に関連する

階乗がどんどん大きくなるにつれて、数論を巧みに利用して興味深い数値 (値) を見つけることが階乗アルゴリズムの設計ポイントになります。関連する質問と分析をいくつか示します。

（１）階乗の最後のゼロでない桁を計算する。

これは古典的な問題です。より複雑なアルゴリズムでは難しい数式が使用されますが、残念ながらその使い方がわかりません。オンラインの資料から学び、次のようなシンプルでわかりやすいアルゴリズムを思いつきました。

n! を観察すると、乗算処理中に、任意の n > 1 について、n! の最後のゼロ以外の桁が偶数であることがわかります。最後のゼロ以外の数字のみを保持する必要があります。掛け算する数に 5 の因数が含まれている場合、5 の因数はすべて 8 として掛け算できます。その理由は次のとおりです。

…x2*5=…10（切り捨て）または…60、最後のゼロ以外の数字は6です。そして、2*8=16となり、最後の桁は6になります。

…x4*5=…70（切り捨て）または…20、最後のゼロ以外の数字は2です。そして、4*8=32となり、最後の桁は2になります。

…x6*5=…30（切り捨て）または…80、最後のゼロ以外の数字は8です。そして、6*8=48となり、最後の桁は8になります。

…x8*5=…90（切り捨て）または…40、最後のゼロ以外の数字は4です。そして、8*8=64となり、最後の桁は4になります。

(n > 1 の場合、最後の数字は 1、7、3、9 ではなく、常に 2、4、6、8 の周期で表示されます)

したがって、反復乗算を実行する場合、主なことは 5 の因数の数を計算することです。同時に、5 の因数の数は 4 の循環であることがわかります (つまり、その数を 4 で割った値のみを取得する必要があります)。次に、さまざまな状況での 5 の因数の数は、res[5][4] = {{0,0,0,0}, {2,6,8,4}, {4,2,6,8}, {6,8,4,2}, {8,4,2,6}} で取得でき、nonzero[i] は i の階乗の最後の桁を表すために使用されます。

t が偶数の場合は、直接乗算します: nonzero[i] = (nonzero[i-1]*t)%10。

それ以外の場合、nonzero[i] = res[((nonzero[i-1]*t)%10)/2][five];

ここで、t は 5 の因数をすべて除去した結果であり、five は 4 を法とする 5 の因数の数です。関連トピック:

http://acm.zju.edu.cn からの質問 1222。ただし、入力 n は 32 ビット int 値の範囲に限定されず、非常に長い長さを持つことに注意してください。したがって、この異常な問題を計算するときは、高精度の除算 (n/=5) と高精度の加算 (cnt+=n) を使用する必要があります。

（２） 階乗の最後にはゼロがいくつありますか?

分析により、因数 5 の数は実際には末尾の 0 の数であることが示され、因数 i を含む 1 から n までの数値の数を計算する簡単なアルゴリズムは次のようになります。

cnt = 0; while (n) { n /= i; cnt += n; }

したがって、i を 5 に置き換えるだけで、5 の因数の数、つまり n! の末尾のゼロの数を取得できます。

（３） 階乗の左側の2番目の数値を返します

シンプルなアルゴリズム: 実数を掛けて、100 を超える場合は 10 で割り、1 の位に切り上げます。整数部分の 1 桁目は階乗結果の左から 2 番目の桁であるためです。関連トピック:

（４） 値 m が n を割り切れるかどうかを判断します。

アルゴリズム: 素因数決定法を使用する

A. まず、2つの特殊なケースを直接出力します。

m == 0 の場合、0 は間違いなく n を割り切れません。

n >= m であれば、m は確実に n を割り切れます。

B. すると、m > n の 1 つのケースのみが残ります。m の最小の素因数から始めます。素因数を i とします。すると、m の素因数 i の数 nums1 がわかります。次に、閉区間 i と n の間の数値を調べて、それらに素因数 i がいくつ含まれているかを確認します。上記 (2) で紹介した数式を使用して、nums2 を計算することができます。 nums2 < nums1 の場合、1 ~ n の素因数の数 < 除数 m の素因数 i の数であることを意味し、m は n! を割り切れないはずなので、ok = false に設定します。

C. ***: !ok または m > n または m == 0 の場合、割り切れません。それ以外の場合は割り切れます。

（５）数 N はいくつかの異なる階乗の合計として表現できますか。

ここで選択できる階乗は、0! ~ 9! です。実際、この質問は数論とは何の関係もなく、検索に関するものです。関連する質問: http://acm.zju.edu.cn からの質問 2358。

分析: 選択できる階乗の数が少ないため、DFS 検索を直接使用できます。

A. まず、0から9までの階乗の表A[10]を作成し、次にその和を形成できる配列ans[N]を設定します。

B. 深さ優先探索法:

検索(n) {
 ( i = n ; i < = 9; i++) の場合 {
 sum += A[i]; //合計。ans配列にsumが存在しない場合は、ans[]配列にsumを挿入します。
検索(n+1);
 sum - = A [i]; // バックトラック
}
 }

C. ***入力 n について、ans 配列に n が存在するかどうかを確認します。存在する場合は、n を異なる階乗和として表現できることを意味し、存在しない場合は表現できません。

上記の紹介から、C++ の階乗はループ ステートメントを使用して実装されていることがわかります。実際、階乗アルゴリズムを習得すれば、どの言語でも簡単に実装できます。これが階乗についてのより深い理解に役立つことを願っています。

【編集者のおすすめ】

1. 2.2 階乗に怯まないで
2. Java でアルゴリズムを実装する場合は、再帰に注意してください。
3. 非反復乱数列生成アルゴリズム
4. C/C++アルゴリズム設計における任意のビット幅の使用