Trang 1 / 2 12 LastLast
Hiển thị kết quả từ 1 đến 10 / 17
  1. #1
    Tham gia
    09-12-2005
    Bài viết
    125
    Like
    0
    Thanked 0 Times in 0 Posts

    Làm sao để tính giai thừa với số lớn!

    Có ai biết cách tính giai thừa của số lớn không?, khoảng 1 tỷ chẳng hạn, tui có thấy một công thức dùng để tính khai triển như sau:

    log(N!) = SUM log(k) FOR k = 1 to N
    log(N!) = floor(log(N!)) + (log(N!) - floor(log(N!)))

    cuối cùng là:
    n+½ -n
    n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) - ... )

    ở đây hiển thị không đúng nên chú thích chút(n mũ n+1/2, e mũ -n)

    n -n
    n! ~ n e SQRT(2pi*n + 1/3) (n mũ n, e mũ -n)
    không biết dùng thế này có ổn không?
    Quote Quote

  2. #2
    Tham gia
    28-09-2004
    Location
    Hà Nội
    Bài viết
    290
    Like
    0
    Thanked 1 Time in 1 Post
    1 tỉ giai thứa ặc ặc

  3. #3
    Tham gia
    10-12-2004
    Location
    HCMC
    Bài viết
    2,121
    Like
    283
    Thanked 720 Times in 362 Posts
    Quote Được gửi bởi Rikku
    1 tỉ giai thứa ặc ặc
    chuyện nhỏ, bác chuyển 1 tỉ giai thừa ra kí tự, lưu vô file, xong rồi chia nhỏ dãy số ra, xử lí trên file, không xử lí số mà chuyển số sang kí tự số rồi xử lí là ok.

  4. #4
    Tham gia
    09-12-2005
    Bài viết
    125
    Like
    0
    Thanked 0 Times in 0 Posts
    Bạn có thể nói rõ hơn không?, tui vẫn chưa hình dung được cách làm của bạn, tui có tìm thấy thuật toán này chạy 1000000! khá nhanh, nhưng không có code, nếu dùng số thông thường thì overflow là cái chắc rùi.

  5. #5
    Tham gia
    07-12-2004
    Bài viết
    120
    Like
    0
    Thanked 0 Times in 0 Posts
    He he, có ai lại đi tính 1 tỉ giai thừa bao giờ, kể cả ghi kết quả ra file thì cũng phải mất cả GB, chả có trình nào mở nổi, tính làm gì cho mệt.

    Còn nếu muốn viết chương trình, thì chỉ cần viết 1 hàm nhân thôi

  6. #6
    Tham gia
    17-09-2002
    Location
    SMA
    Bài viết
    749
    Like
    0
    Thanked 3 Times in 3 Posts
    Cái này gọi là ¨rubbish kỹ thuật cao¨ vì mất bài toán như thế này ít khi có ý nghĩa thực tế mà thường chỉ dùng để nghiên cứu. Giai thừa số lớn ko lạ lắm trong toán học, nhưng 1 tỉ giai thừa thì là... overkill.

    1 tỉ giai thừa là khoảng vài tỉ chữ số nên lưu nó cũng là vấn đề. Ở đây bàn đến 2 cách: tính chính xác và tính xấp xỉ. Tính chính xác có nhiều thuật toán, cách ¨ngu¨ là dùng đệ quy hay tính kiểu bình thường nhân là cách ai cũng biết. Đương nhiên là nó cần phải có cách biểu diễn số lớn tương ứng. Không kể đến chuyện này, độ phức tạp là khoảng O(n*log(n)^2*(loglog(n))^2). Tôi nghĩ tính xong chắc cũng mất vài ngày cho là dùng thuật toán nhanh nhất hiện nay (dựa vào phân tích thừa số nguyên tố - prime factorization và fast multiplication). Đương nhiên tốc độ còn phụ thuộc cách thức lưu và truy cập dữ liệu nữa.

    Bạn liệt kê vài công thức xấp xỉ nên chắc hỏi tính xấp xỉ. Tính xấp xỉ thì cũng phải dùng biểu diễn số lớn thôi (ở đậy là số thực lớn) vì bạn cũng biết số chữ số của n! là khoảng O(n*log(n)). Công thức tính xấp xỉ tốt nhất là dùng xấp xỉ Stirling cho hàm Gamma (công thức cuối bạn ghi ở trên). Công thức này hội tụ khi x->inf nên x càng lớn càng đúng Tiện đây nói luôn là hàm Gamma cho phép tính giai thừa của cả số thực.

  7. #7
    Tham gia
    10-12-2004
    Location
    HCMC
    Bài viết
    2,121
    Like
    283
    Thanked 720 Times in 362 Posts
    uh, mà tính 1 tỉ giai thừa làm chi vậy ta??

  8. #8
    Tham gia
    09-12-2005
    Bài viết
    125
    Like
    0
    Thanked 0 Times in 0 Posts
    Cái tui định đề cập ở đây không phải là tính 1 tỷ giai thừa để làm gì, mà chỉ muốn thử xem trên một máy tính bình thường, với một giải thuật tối ưu thì có thể thực hiện được điều này hay không thôi. Hiện nay có rất nhiều các giải thuật tối ưu mà thời gian chạy thì không thể tưởng tượng nổi, nếu có thời gian thì các bạn có thể xem trên trang này www.usaco.org, có những bài toán khá phức tạp nhưng thời gian chạy của họ là 0s, quá ngang bằng không chạy.

  9. #9
    Tham gia
    28-06-2005
    Location
    HCMC
    Bài viết
    117
    Like
    0
    Thanked 0 Times in 0 Posts
    nhớ hồi xưa nhặt được cái Source tính giai thừa lớn (1 tỷ thì không chắc chứ 1 triệu thì được đó) trên trang web của ông ĐH nào đó. Rất tiếc mất rùi. SOurce bằng pascal có 1 chương trình con xài ASM cũng ngắn thôi.

  10. #10
    Tham gia
    20-07-2003
    Bài viết
    83
    Like
    0
    Thanked 0 Times in 0 Posts
    Quote Được gửi bởi Dau_Dat
    Có ai biết cách tính giai thừa của số lớn không?, khoảng 1 tỷ chẳng hạn, tui có thấy một công thức dùng để tính khai triển như sau:

    log(N!) = SUM log(k) FOR k = 1 to N
    log(N!) = floor(log(N!)) + (log(N!) - floor(log(N!)))

    cuối cùng là:
    n+½ -n
    n! ~ n e SQRT(2pi)*( 1 + 1/(12n) + 1/(288n²) - ... )

    ở đây hiển thị không đúng nên chú thích chút(n mũ n+1/2, e mũ -n)

    n -n
    n! ~ n e SQRT(2pi*n + 1/3) (n mũ n, e mũ -n)
    không biết dùng thế này có ổn không?
    Cái công thức bạn đưa ở trên chỉ gần đúng thôi , chúng chỉ ứng dụng trong việc đánh giá giá trị thôi , còn nếu để tính chính xác n! thì không chuẩn , vì n! là số nguyên. Tôi có viết một program tính 2006! băng C++ chạy mất độ 10 phút, không biết nếu bạn tính 1 tỉ giai thừa không biết mất bao nhiêu thời gian , nếu bạn nào đã tính một tỉ giai thừa , xin cho biết thời gian thực hiện là bao lâu vậy?

Trang 1 / 2 12 LastLast

Bookmarks

Quy định

  • Bạn không thể tạo chủ đề mới
  • Bạn không thể trả lời bài viết
  • Bạn không thể gửi file đính kèm
  • Bạn không thể sửa bài viết của mình
  •