Bất cứ ai có thể giải thích thuật toán này để tính toán giai thừa lớn?

Question

tôi đi qua chương trình sau đây để tính toán giai thừa lớn (số lượng lớn như 100) .. bất cứ ai có thể giải thích cho tôi những ý tưởng cơ bản được sử dụng trong thuật toán này ?? Tôi chỉ cần biết toán học được thực hiện để tính giai thừa.

#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; 
} 

Answer 1

Lưu ý rằng

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

để

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

này rất quan trọng bởi vì nếu k là một số nguyên dương thì trần log(k) là số chữ số trong cơ số 10 đại diện của k. Do đó, các dòng mã này đang đếm số chữ số trong n!.

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

Sau đó, những dòng mã phân bổ không gian để chứa các chữ số của n!:

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

Sau đó, chúng tôi chỉ làm những thuật toán nhân lớp học

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); 
    } 
} 

Các vòng lặp bên ngoài là chạy từ j từ 2 đến n vì tại mỗi bước chúng tôi sẽ nhân kết quả hiện tại được biểu thị bằng d igits in a by j. Vòng lặp bên trong là thuật toán nhân học cấp lớp, trong đó chúng ta nhân mỗi số bằng j và mang kết quả vào q nếu cần.

p = 0.0 trước vòng lặp lồng nhau và p += log10(j) bên trong vòng lặp chỉ theo dõi số lượng chữ số trong câu trả lời cho đến thời điểm này.

Ngẫu nhiên, tôi nghĩ có lỗi trong phần này của chương trình. Điều kiện vòng lặp phải là i < z không phải i <= z nếu không chúng tôi sẽ viết qua cuối a khi z == d sẽ xảy ra chắc chắn khi j == n. Do đó thay thế

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

bởi

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

Sau đó, chúng tôi chỉ in ra các chữ số

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

và miễn phí bộ nhớ phân bổ

delete []a;