23

大きな階乗（100までの数）を計算するための次のプログラムに出くわしました。このアルゴリズムで使用される基本的な考え方を誰かに説明してもらえますか？階乗の計算で実装された数学だけを知る必要があります。

#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{

      unsigned int d;

      unsigned char *a;

      unsigned int j, n, q, z, t;

      int i,arr[101],f;

      double p;


    cin>>n;
    p = 0.0;
    for(j = 2; j <= n; j++)
        p += log10(j);
    d = (int)p + 1;
    a = new unsigned char[d];
    for (i = 1; i < d; i++)
        a[i] = 0; //initialize
    a[0] = 1;
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
        q = 0;
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
            t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }

    }
    for( i = d -1; i >= 0; i--)
        cout << (int)a[i];
    cout<<"\n";
    delete []a;

return 0;
}
4

1 に答える 1

86

ご了承ください

n! = 2 * 3 * ... * n

となることによって

log(n!) = log(2 * 3 * ... * n) = log(2) + log(3) + ... + log(n)

kが正の整数の場合、の上限は。log(k)の基数10表現の桁数であるため、これは重要ですk。したがって、これらのコード行は、の桁数をカウントしていn!ます。

p = 0.0;
for(j = 2; j <= n; j++)
    p += log10(j);
d = (int)p + 1;

次に、これらのコード行は、次の数字を保持するためのスペースを割り当てますn!。

a = new unsigned char[d];
for (i = 1; i < d; i++)
    a[i] = 0; //initialize

次に、小学校の乗算アルゴリズムを実行します

p = 0.0;
for (j = 2; j <= n; j++) {
    q = 0;
    p += log10(j);
    z = (int)p + 1;
    for (i = 0; i <= z/*NUMDIGITS*/; i++) {
        t = (a[i] * j) + q;
        q = (t / 10);
        a[i] = (char)(t % 10);
    }
}

外側のループはfromjから2toまで実行されます。nこれは、各ステップで、の数字で表される現在の結果に。を掛けるためです。内側のループは小学校の乗算アルゴリズムであり、各桁に乗算を行い、必要に応じてその結果を代入します。ajjq

p = 0.0ネストされたループの前とループのp += log10(j)内側は、これまでの回答の桁数を追跡するだけです。

ちなみに、プログラムのこの部分にはバグがあると思います。ループ条件はそうでi < zないはずです。そうでなければ、いつi <= zの終わりを過ぎて書き込みを行うことになります。したがって、置き換えますaz == dj == n

for (i = 0; i <= z/*NUMDIGITS*/; i++)

に

for (i = 0; i < z/*NUMDIGITS*/; i++)

次に、数字を印刷します

for( i = d -1; i >= 0; i--)
    cout << (int)a[i];
cout<<"\n";

割り当てられたメモリを解放します

delete []a;
于 2010-01-24T15:37:19.937 に答える