Tính giai thừa lớn trong C++

Question

Tôi hiểu đây là một vấn đề lập trình cổ điển và do đó tôi muốn rõ ràng tôi không tìm kiếm mã như một giải pháp, nhưng sẽ đánh giá cao sự thúc đẩy đúng hướng. Tôi đang học C++ và là một phần của quá trình học tập Tôi đang thử một số vấn đề về lập trình. Tôi đang cố gắng viết một chương trình có số lượng lên đến 1 tỷ. Rõ ràng đây sẽ là những con số khổng lồ và quá lớn để đối phó với việc sử dụng các phép toán số học bình thường. Bất kỳ dấu hiệu nào cho biết tôi nên đi theo hướng nào để cố gắng giải quyết loại vấn đề này sẽ được đánh giá cao.

Tôi muốn cố gắng để giải quyết việc này mà không sử dụng các thư viện bổ sung nếu có thể

Cảm ơn

PS - vấn đề là ở đây http://www.codechef.com/problems/FCTRL

---

Dưới đây là phương pháp tôi sử dụng để giải quyết vấn đề , điều này đạt được bằng cách đọc các nhận xét bên dưới:

Giải pháp - Số 5 là yếu tố chính của bất kỳ số nào kết thúc bằng số không. Do đó, chia số thừa cho 5, đệ quy và thêm số lượng, bạn sẽ nhận được số lượng dấu 0 trong kết quả giai thừa

E.G. - Số lượng dấu 0 trong số 126! = 31

126/5 = 25 còn lại 1

25/5 = 5 còn lại 0

5/5 = 1 dư 0

25 + 5 + 1 = 31

Điều này phù hợp với bất kỳ giá trị nào, chỉ cần tiếp tục chia cho đến khi thương số ít hơn hơn 5

Answer 1

skimmed câu hỏi này, không chắc chắn nếu tôi thực sự đã nhận nó đúng, nhưng đây là một đoán suy:

Câu hỏi đầu tiên - làm thế nào để bạn có được một số không trên kết thúc của số? Bằng cách nhân với 10.

Bạn nhân với 10 bằng cách nào? bằng cách nhân với 10 hoặc 2 x 5 ...

Vì vậy, đối với X! bạn có bao nhiêu 10s và 2x5s ...?

(may mắn là 2 & 5 là số nguyên tố)

chỉnh sửa: Dưới đây là gợi ý khác - Tôi không nghĩ rằng bạn cần phải làm bất kỳ nhân. Hãy cho tôi biết nếu bạn cần một gợi ý khác.

Answer 2

Để bắt đầu, bạn nên lưu trữ số trong một số loại mảng như d :: vectơ (một chữ số cho mỗi vị trí trong mảng) và bạn cần tìm một thuật toán nào đó để tính giai thừa (có thể trong một số loại lớp chuyên biệt). ;)

Answer 3

Bạn cần gói "big number" - dù bạn sử dụng hoặc bạn viết chính mình.

Tôi khuyên bạn nên thực hiện một số nghiên cứu thành "large number algorithms". Bạn sẽ muốn thực hiện tương đương C++ của Java BigDecimal.

Một cách khác để xem nó là sử dụng gamma function. Bạn không cần phải nhân tất cả các giá trị đó để có được câu trả lời đúng.

Answer 4

Gợi ý: bạn có thể không cần tính N! để tìm số 0 ở cuối N!

Answer 5

Đây không phải là câu trả lời hay cho câu hỏi của bạn vì bạn đã sửa đổi nó một chút so với những gì tôi đã đọc ban đầu. Nhưng tôi sẽ để nó ở đây để chứng minh tính không thực tế của việc thực sự cố gắng thực hiện các phép tính bằng vũ lực chính.

Một tỷ giai thừa sẽ không nằm ngoài tầm với của thư viện bignum. Những con số như vậy sẽ đòi hỏi nhiều không gian hơn để đại diện cho hầu hết mọi người có trong RAM. Bạn sẽ phải bắt đầu phân trang các số từ bộ nhớ khi bạn làm việc với chúng. Có nhiều cách để làm điều này.guy who recently calculated π out to 2700 billion places đã sử dụng thư viện này

Answer 6

Để giải quyết câu hỏi này, vì Chris Johnson cho biết bạn phải xem số lượng 0.

Các yếu tố của 10 sẽ là 1,2,5,10. Vì vậy, bạn có thể đi qua từng số N! và viết chúng theo 2^x * 5^y * 10^z. Loại bỏ các yếu tố khác của các con số.

Bây giờ câu trả lời sẽ lớn hơn (x, y) + z.

Một điều thú vị tôi học được từ câu hỏi này là, tốt hơn hết là lưu trữ giai thừa của một số về các yếu tố chính để so sánh dễ dàng.

Để thực sự x^y, có một phương pháp dễ sử dụng trong thuật toán RSA, mà không nhớ. Tôi sẽ cố gắng cập nhật bài đăng nếu tôi tìm thấy.

Answer 7

Không sử dụng phương pháp ngây thơ. Nếu bạn cần phải tính toán giai thừa, sử dụng một thuật toán nhanh: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 8

Tôi nghĩ rằng bạn nên tìm ra cách giải quyết vấn đề trong mã giả trước khi bạn bắt đầu nghĩ về C++ hoặc bất kỳ ngôn ngữ nào khác cho vấn đề đó. Bản chất của câu hỏi như một số đã chỉ ra là nhiều hơn một vấn đề thuật toán hơn là một vấn đề C + +. Những người đề nghị tìm kiếm một số thư viện tối nghĩa đang chỉ cho bạn theo hướng của một con dốc trơn trượt, bởi vì việc học lập trình là học cách suy nghĩ, đúng không? Tìm một văn bản phân tích thuật toán tốt và nó sẽ phục vụ bạn tốt. Trong bộ phận của chúng tôi, chúng tôi dạy từ văn bản CLRS.

Answer 9

Để tính toán thừa lớn, bạn có thể sử dụng mã này trong C++:

#include<iostream> 
using namespace std; 

long double factorial(int n); 

int main() 
{ 
    int n; 

    cout << "Enter a positive integer: "; 
    cin >> n; 

    cout << "Factorial of " << n << " = " << factorial(n); 

    return 0; 
} 

long double factorial(int n) 
{ 
    if(n > 1) 
     return n * factorial(n - 1); 
    else 
     return 1; 
} 

Khi đôi dài nắm giữ dữ liệu lớn 1.7E +/- 308, mã này thực sự có thể thực hiện tốt !!