Follow us on...
Follow us on Twitter Follow us on Facebook Watch us on YouTube

Giúp các bé đáng thương ấy với

Gameshow “Ai Là Triệu Phú” trên VTV đang chờ đón bạn – Tải ngay!

Bán đấu giá ủng hộ từ thiện

Sự kiện công nghệ lớn nhất trong năm của Sony sắp đổ bộ Hà Nội

Chiêm ngưỡng BaoMoi đẹp "tuyệt diệu" trên Windows Phone

Tin tức công nghệ mới
Trang 1/2 1 2 cuốicuối
kết quả từ 1 tới 15 trên 16
  1. #1
    gaara18's Avatar
    gaara18 vẫn chưa có mặt trong diễn đàn Búa Gỗ Đôi
    Tham gia
    Jul 2012
    Bài
    42
    Cảm ơn
    24
    Điểm
    2/2 bài viết

    Default Tính giai thừa số nguyên cưc lớn

    Mình đang học viết C. Mọi người giúp mình bài tập này nha.
    Viết chương trinh nhập 1 số tự nhiên N (N<=30000) và in ra tất cả số 0 của N!

  2. #2
    Logachune's Avatar
    Logachune vẫn chưa có mặt trong diễn đàn Rìu Bạc
    Tham gia
    Nov 2010
    Bài
    366
    Cảm ơn
    425
    Điểm
    70/56 bài viết

    Default

    chả có kiểu dữ liệu nào chứa nổi số đó đâu. Ngày xưa mình học tính đến 65! là hết rồi

  3. #3
    programmer2010's Avatar
    programmer2010 vẫn chưa có mặt trong diễn đàn Rìu Chiến Chấm
    Tham gia
    Feb 2010
    Bài
    2.650
    Cảm ơn
    39
    Điểm
    659/596 bài viết

    Default

    Trích Logachune View Post
    chả có kiểu dữ liệu nào chứa nổi số đó đâu. Ngày xưa mình học tính đến 65! là hết rồi
    Thì mình tự viết BigInt

  4. #4
    LordTNT's Avatar
    LordTNT vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Aug 2012
    Bài
    487
    Cảm ơn
    0
    Điểm
    163/150 bài viết

    Default

    nếu in ra tất cả các số 0 ở đuôi của N! thì dễ lắm.

    Để ý chỉ cứ 1 số chia hết cho 5 thì tạo được 1 số 0, 1 số chia hết cho 5^2 thì tạo đc 2 số 0, 1 số chia hết cho 5^3 thì tạo đc 3 số 0, ..., 1 số chia hết cho 5^n thì tạo đc n số 0.

    Vậy đơn giản là tìm số n sao cho 5^n < N < 5^(n+1). Khi đó tổng số các số 0 sẽ là N/5 + N/5^2 + ... + N/5^n. Làm 1 vòng lặp for in ra là xong.


    Còn tất cả số 0 kể cả ở giữa thì

  5. #5
    lyvinhloi.cntt's Avatar
    lyvinhloi.cntt vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Dec 2012
    Bài
    652
    Cảm ơn
    67
    Điểm
    164/152 bài viết

    Default

    Chịu, bài này tính số số 0 ở cuối được thôi, bignum tính lâu lắm, N = 20
    => N! = 2432902008176640000
    4 số cuối thì còn có cách tính chứ mấy số ở giữa thì mệt @@
    Điều quan trọng là Bạn hôm nay có giỏi hơn Bạn hôm qua không, chứ không phải Bạn có giỏi hơn người ta hay không.
    Email liên hệ: lyvinhloi.cntt@gmail.com

  6. #6
    luuvanson_ML's Avatar
    luuvanson_ML vẫn chưa có mặt trong diễn đàn Rìu Sắt
    Tham gia
    Oct 2009
    Bài
    140
    Cảm ơn
    15
    Điểm: 1/1 bài viết

    Default

    Trích LordTNT View Post
    nếu in ra tất cả các số 0 ở đuôi của N! thì dễ lắm.

    Để ý chỉ cứ 1 số chia hết cho 5 thì tạo được 1 số 0, 1 số chia hết cho 5^2 thì tạo đc 2 số 0, 1 số chia hết cho 5^3 thì tạo đc 3 số 0, ..., 1 số chia hết cho 5^n thì tạo đc n số 0.

    Vậy đơn giản là tìm số n sao cho 5^n < N < 5^(n+1). Khi đó tổng số các số 0 sẽ là N/5 + N/5^2 + ... + N/5^n. Làm 1 vòng lặp for in ra là xong.


    Còn tất cả số 0 kể cả ở giữa thì
    Bác code đoạn đó cho xem với đc k?

  7. #7
    LordTNT's Avatar
    LordTNT vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Aug 2012
    Bài
    487
    Cảm ơn
    0
    Điểm
    163/150 bài viết

    Default

    python:
    PHP Code:
    def factorialTrailingZeros(n):
        
    0
        
    while n:
            
    += n/5
            n 
    /= 5
        
    return '0' s
        
    print factorialTrailingZeros(1000
    cái này đơn giản ai cũng hiểu. s là tổng số các số 0 ở đuôi của n!

  8. #8
    lyvinhloi.cntt's Avatar
    lyvinhloi.cntt vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Dec 2012
    Bài
    652
    Cảm ơn
    67
    Điểm
    164/152 bài viết

    Default

    Trích LordTNT View Post
    nếu in ra tất cả các số 0 ở đuôi của N! thì dễ lắm.

    Để ý chỉ cứ 1 số chia hết cho 5 thì tạo được 1 số 0, 1 số chia hết cho 5^2 thì tạo đc 2 số 0, 1 số chia hết cho 5^3 thì tạo đc 3 số 0, ..., 1 số chia hết cho 5^n thì tạo đc n số 0.

    Vậy đơn giản là tìm số n sao cho 5^n < N < 5^(n+1). Khi đó tổng số các số 0 sẽ là N/5 + N/5^2 + ... + N/5^n. Làm 1 vòng lặp for in ra là xong.


    Còn tất cả số 0 kể cả ở giữa thì
    Bạn cho ví dụ được không ? Mình không hiểu lắm
    Tưởng là phải chia cho 2*5 thì tạo được số 0, 2^2*5^2 => 2 số 0 ... cứ thế
    Nếu đếm các số 0 cuối thì quy về tích các thừa số nguyên tố, sau đó lấy số mũ bằng nhau của 2 và 5 thôi, nhưng hơi rắc rối @@

    Vd: 5! = 1*2*3*4*5 = 2*3*2*2*5 = (2^3)*3*5 ( lúc này tính dc 1 số 0, vì chỉ có 1 số 5 thôi ) = 8*5*3 = 120 <~ 1 số 0
    Điều quan trọng là Bạn hôm nay có giỏi hơn Bạn hôm qua không, chứ không phải Bạn có giỏi hơn người ta hay không.
    Email liên hệ: lyvinhloi.cntt@gmail.com

  9. #9
    programmer2010's Avatar
    programmer2010 vẫn chưa có mặt trong diễn đàn Rìu Chiến Chấm
    Tham gia
    Feb 2010
    Bài
    2.650
    Cảm ơn
    39
    Điểm
    659/596 bài viết

    Default

    ^ Uh thì cứ 2*5 là ra đc 1 số 0 đuôi, nhưng lấy hết thừa số 5 rồi thì đâu ra nữa mà kết hợp.
    Mà thừa số 2 thì bao la nên đếm thừa số 5 là đủ.

    Giải thích: Do cứ 5 số tự nhiên liên tiếp thì có 1 số chia hết cho 5 nên chia ngay cho 5.
    Vấn đề là trong mớ số chia hết cho 5 thì lại có số chia hết cho 25 và chúng có thêm 1 thừa số 5 nữa, nên cần phải chia cho 25 để lấy cho hết...
    ... Và cứ thế.

  10. #10
    LordTNT's Avatar
    LordTNT vẫn chưa có mặt trong diễn đàn Rìu Bạc Đôi
    Tham gia
    Aug 2012
    Bài
    487
    Cảm ơn
    0
    Điểm
    163/150 bài viết

    Default

    Trích lyvinhloi.cntt View Post
    Bạn cho ví dụ được không ? Mình không hiểu lắm
    Tưởng là phải chia cho 2*5 thì tạo được số 0, 2^2*5^2 => 2 số 0 ... cứ thế
    Nếu đếm các số 0 cuối thì quy về tích các thừa số nguyên tố, sau đó lấy số mũ bằng nhau của 2 và 5 thôi, nhưng hơi rắc rối @@

    Vd: 5! = 1*2*3*4*5 = 2*3*2*2*5 = (2^3)*3*5 ( lúc này tính dc 1 số 0, vì chỉ có 1 số 5 thôi ) = 8*5*3 = 120 <~ 1 số 0
    khỏi cần phân tích thành thừa số nguyên tố. Tại cứ 5 số liên tiếp thì có 1 số chia hết cho 5 và có nhiều hơn 1 số chia hết cho 2, 25 số liên tiếp có 1 số chia hết cho 25 và có nhiều hơn 1 số chia hết cho 4, v.v... Tóm lại 2^m * 5^n thì m luôn lớn hơn n, nên đếm các số 0 ở đuôi thì chỉ cần đếm số mũ của 5 là được rồi. Mà chỉ đếm số mũ của 1 số thì khỏi cần phân tích thành thừa số, chia từ từ là đc rồi.

    Vd: 1000!
    từ 1 tới 1000 có:
    1000/5=200 số chia hết cho 5 (5,10,15,20,...,1000 = 5*[1,2,3,4,...,200] => 200 số)
    1000/25=40 số chia hết cho 25 (25*[1,2,3,4,...,40] => 40 số)
    1000/125=8 số chia hết cho 125 (125*[1,2,3,4,...,8] => 8 số)
    1000/625=1 số chia hết cho 625 (625* [1] => 1 số)
    1000/3125=0 số chia hết cho 3125 //dừng tại đây
    tổng = 200+40+8+1.

    giải thích theo kiểu khác thì từ 1 tới 1000 có 200 số chia hết cho 5 (5^1)
    trong 200 số chia hết cho 5 này lại có 40 số chia hết cho 25 (5^2)
    trong 40 số chia hết cho 25 này lại có 8 số chia hết cho 125 (5^3)
    trong 8 số chia hết cho 125 này lại có 1 số chia hết cho 625 (5^4)
    vậy tổng số số 0 ở đuôi của 1000! là 200 + 40 + 8 + 1 = 249 số 0.

    Với dãy 5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,105,110,115,120,125,130,....
    thì cứ 5 phàn tử là có 1 phần tử chia hết cho 25, nên cứ 200 phần tử chia hết cho 5 liên tục thì có 200/5=40 phần tử chia hết cho 25.

    tương tự 25,50,75,100,125,... thì cũng 5 phần tử lại có 1 phần tử chia hết cho 125. Suy ra 40 phần tử liên tiếp chia hết cho 25 thì có 40/5=8 phần tử chia hết cho 125.

    ...
    Cứ thế cho tới khi chia ra bằng 0 thì dừng.


    Vd khác: 123456!
    5 * [1,2,3,...,24691] => 24691 số chia hết cho 5^1
    25 * [1,2,3,...,4938] => 4938 số chia hết cho 5^2
    125 * [1,2,3,...,987] => 987 số chia hết cho 5^3
    625 * [1,2,3,...,197] => 197 số chia hết cho 5^4
    3125 * [1,2,3,...,39] => 39 số chia hết cho 5^5
    15625 * [1,2,3,...,7] => 7 số chia hết cho 5^6
    78125 * [1] => 1 số chia hết cho 5^7

    tổng số các số 0 = 24691 + 4938 + 987 + 197 + 39 + 7 + 1 = 30860

    Thay vì lấy 4938 * 2 + 987 * 3... thì vì trong 24691 số chia hết cho 5 đã chứa 4938 số chia hết cho 25 rồi nên 4938 số chia hết cho 25 ko cần nhân 2 nữa, tương tự trong 4938 số chia hết cho 25 đã có 987 số chia hết cho 5^3 rồi nên 987 số chia hết cho 125 này ko cần nhân 3 nữa (vì 5^2 đã được cộng trong 4938 số kia rồi, chỉ cần cộng thêm số 5 thứ 3)
    Thay đổi nội dung bởi LordTNT; 24-08-2013 lúc 21:34.

  11. #11
    luuvanson_ML's Avatar
    luuvanson_ML vẫn chưa có mặt trong diễn đàn Rìu Sắt
    Tham gia
    Oct 2009
    Bài
    140
    Cảm ơn
    15
    Điểm: 1/1 bài viết

    Default

    code bằng Pascal đi các thím
    thật không đơn giản chút nào

  12. #12
    K4hit0102's Avatar
    K4hit0102 vẫn chưa có mặt trong diễn đàn Búa Đá
    Tham gia
    Jan 2010
    Đến từ
    Nam Đàn
    Bài
    64
    Cảm ơn
    8
    Điểm
    16/15 bài viết

    Default

    với n= 2500, thời gian thực thi hơi tồi tệ, khoảng 30 giây tùy máy , ko biết ai có cách nào tối ưu thời gian ko, tui làm dựa trên phép nhân 2 số cực lớn. Và với giai thừa số cực lớn, dựa trên thuật toán nó cũng giải quyết được mà ko dính ngoại lệ (trừ khi bộ nhớ ko đủ lớn để cấp cho chuỗi kết quả) nhưng có lẽ thời gian thực thi sẽ cực kì lớn,...

    "BigNum.h"
    PHP Code:
    #pragma once
    #include <string>
    class BigNum
    {
    private:
        
    std::string num;
        
    bool Check(const std::string);
    public:
        
    BigNum(const std::string);
        
    //BigNum(const BigNum&);
        //BigNum& operator=(const BigNum&);
        
    ~BigNum(void);
        
    BigNum Add(const BigNum&); //phep cong
        
    BigNum Sub(const BigNum&); //phep tru
        
    BigNum Mul(const BigNum&); //phep nhan
        
    BigNum Fac(); //giai thua
        
    BigNum operator+(const BigNum&);
        
    BigNum operator-(const BigNum&);
        
    BigNum operator*(const BigNum&);
        
    bool operator==(const BigNum&);
        
    std::string ToStr();
        
    BigNumSetNum(const std::string);
    }; 

    "BigNum.cpp"
    PHP Code:
    #include "BigNum.h"
    #include <iostream>
    using namespace std;

    bool BigNum::Check(const std::string _num)
    {
        for(
    size_t i 0_num.length(); i++)
            if(
    _num.at(i) - '0' || _num.at(i) - '0' 9)
                return 
    false;
        return 
    true;
    }

    BigNum::BigNum(const std::string _num)
    {
        if(!
    Check(_num))
            
    this->num "0";
        
    this->num _num;
    }

    string BigNum::ToStr()
    {
        return 
    this->num;
    }

    BigNumBigNum::SetNum(const std::string _num)
    {
        
    this->num _num;
        return *
    this;
    }

    BigNum BigNum::Add(const BigNum_num)
    {
        
    string n1(num), n2(_num.num);
        
    int s1 n1.length(), s2 n2.length();
        if(
    s1 s2)
        {
            
    string n3(n1); int s3 s1;
            
    n1 n2s1 s2;
            
    n2 n3s2 s3;
        }
        
    string result("");
        
    result.resize(s1'0');
        
    int mem 0;
        for(
    int i s1-1s2-1>= 0i--, j--)
        {
            if(
    0)
                
    result.at(i) = (char)n1.at(i) + mem;
            else
                
    result.at(i) = (char)n1.at(i) + n2.at(j) - '0' mem;
            if(
    result.at(i) - '0' >= 10)
            {
                if(
    != 0)
                {
                    
    result.at(i) = char(result.at(i) - 10);
                    
    mem=1;
                }
                else
                {
                    
    char temp result.at(0);
                    
    result.replace(0,1,"00");
                    
    result.at(0) = (char)(temp '0')/10 '0';
                    
    result.at(1) = (char)(temp '0')%10 '0';
                    break;
                }
            }
            else
                
    mem 0;
        }
        return 
    BigNum(result);
    }

    BigNum BigNum::Mul(const BigNum_num)
    {
        
    string n2(_num.num);
        
    int s2 n2.length();
        
    BigNum result("0");
        for(
    int i s2-1>= 0i--)
        {
            
    BigNum temp("0");
            for(
    int j 0n2.at(i) - '0'j++)
                
    temp temp.Add(*this);
            
    string StrNumTemp temp.num;
            
    StrNumTemp.append(s2-1-i'0');
            
    temp.SetNum(StrNumTemp);
            
    result result.Add(temp);
        }
        return 
    result;
    }

    BigNum BigNum::Fac()
    {
        
    BigNum result("1");
        for(
    BigNum i("1"); i.num.length() != num.length() || i.num.compare(num) <= 0i.Add(BigNum("1")))
            
    result result.Mul(i);
        return 
    result;
    }

    BigNum BigNum::operator+(const BigNum_num)
    {
        return 
    this->Add(_num);
    }

    BigNum::~BigNum(void)
    {


    "main.cpp"
    PHP Code:
    #include "BigNum.h"
    #include <iostream>
    using namespace std;
    void main()
    {
        
    BigNum a("2500");
        
    BigNum b("3628800");
        
    BigNum c("10");
        
    cout<<a.Fac().ToStr(); //in ra ket cua qua 2500!
        //cout<<b.Mul(c).ToStr();
        
    cin.get();

    0 VNĐ

  13. #13
    programmer2010's Avatar
    programmer2010 vẫn chưa có mặt trong diễn đàn Rìu Chiến Chấm
    Tham gia
    Feb 2010
    Bài
    2.650
    Cảm ơn
    39
    Điểm
    659/596 bài viết

    Default

    ^@: Cái này tốt hơn:
    Kết hợp với việc hình thành các tích nằm gọn trong 64 bit, sau đó nhân chúng lại với nhau (overhead sẽ giảm khi 2 thừa số cùng cỡ với nhau).
    Thay đổi nội dung bởi programmer2010; 26-08-2013 lúc 14:40.

  14. Có 1 thành viên cảm ơn programmer2010 cho bài viết này:
    K4hit0102 (26-08-2013)

  15. #14
    K4hit0102's Avatar
    K4hit0102 vẫn chưa có mặt trong diễn đàn Búa Đá
    Tham gia
    Jan 2010
    Đến từ
    Nam Đàn
    Bài
    64
    Cảm ơn
    8
    Điểm
    16/15 bài viết

    Default

    Trích programmer2010 View Post
    ^@: Cái này tốt hơn:
    Kết hợp với việc hình thành các tích nằm gọn trong 64 bit, sau đó nhân chúng lại với nhau (overhead sẽ giảm khi 2 thừa số cùng cỡ với nhau).
    đã tìm hiểu và... không hiểu vì toàn tiếng Anh , cậu nói rõ hơn đi.hjx
    0 VNĐ

  16. #15
    lamdetien36's Avatar
    lamdetien36 vẫn chưa có mặt trong diễn đàn Rìu Vàng
    Tham gia
    Jun 2013
    Bài
    688
    Cảm ơn
    52
    Điểm
    196/164 bài viết

    Default

    Trích K4hit0102 View Post
    với n= 2500, thời gian thực thi hơi tồi tệ, khoảng 30 giây tùy máy , ko biết ai có cách nào tối ưu thời gian ko, tui làm dựa trên phép nhân 2 số cực lớn. Và với giai thừa số cực lớn, dựa trên thuật toán nó cũng giải quyết được mà ko dính ngoại lệ (trừ khi bộ nhớ ko đủ lớn để cấp cho chuỗi kết quả) nhưng có lẽ thời gian thực thi sẽ cực kì lớn,...

    "BigNum.h"
    PHP Code:
    #pragma once
    #include <string>
    class BigNum
    {
    private:
        
    std::string num;
        
    bool Check(const std::string);
    public:
        
    BigNum(const std::string);
        
    //BigNum(const BigNum&);
        //BigNum& operator=(const BigNum&);
        
    ~BigNum(void);
        
    BigNum Add(const BigNum&); //phep cong
        
    BigNum Sub(const BigNum&); //phep tru
        
    BigNum Mul(const BigNum&); //phep nhan
        
    BigNum Fac(); //giai thua
        
    BigNum operator+(const BigNum&);
        
    BigNum operator-(const BigNum&);
        
    BigNum operator*(const BigNum&);
        
    bool operator==(const BigNum&);
        
    std::string ToStr();
        
    BigNumSetNum(const std::string);
    }; 

    "BigNum.cpp"
    PHP Code:
    #include "BigNum.h"
    #include <iostream>
    using namespace std;

    bool BigNum::Check(const std::string _num)
    {
        for(
    size_t i 0_num.length(); i++)
            if(
    _num.at(i) - '0' || _num.at(i) - '0' 9)
                return 
    false;
        return 
    true;
    }

    BigNum::BigNum(const std::string _num)
    {
        if(!
    Check(_num))
            
    this->num "0";
        
    this->num _num;
    }

    string BigNum::ToStr()
    {
        return 
    this->num;
    }

    BigNumBigNum::SetNum(const std::string _num)
    {
        
    this->num _num;
        return *
    this;
    }

    BigNum BigNum::Add(const BigNum_num)
    {
        
    string n1(num), n2(_num.num);
        
    int s1 n1.length(), s2 n2.length();
        if(
    s1 s2)
        {
            
    string n3(n1); int s3 s1;
            
    n1 n2s1 s2;
            
    n2 n3s2 s3;
        }
        
    string result("");
        
    result.resize(s1'0');
        
    int mem 0;
        for(
    int i s1-1s2-1>= 0i--, j--)
        {
            if(
    0)
                
    result.at(i) = (char)n1.at(i) + mem;
            else
                
    result.at(i) = (char)n1.at(i) + n2.at(j) - '0' mem;
            if(
    result.at(i) - '0' >= 10)
            {
                if(
    != 0)
                {
                    
    result.at(i) = char(result.at(i) - 10);
                    
    mem=1;
                }
                else
                {
                    
    char temp result.at(0);
                    
    result.replace(0,1,"00");
                    
    result.at(0) = (char)(temp '0')/10 '0';
                    
    result.at(1) = (char)(temp '0')%10 '0';
                    break;
                }
            }
            else
                
    mem 0;
        }
        return 
    BigNum(result);
    }

    BigNum BigNum::Mul(const BigNum_num)
    {
        
    string n2(_num.num);
        
    int s2 n2.length();
        
    BigNum result("0");
        for(
    int i s2-1>= 0i--)
        {
            
    BigNum temp("0");
            for(
    int j 0n2.at(i) - '0'j++)
                
    temp temp.Add(*this);
            
    string StrNumTemp temp.num;
            
    StrNumTemp.append(s2-1-i'0');
            
    temp.SetNum(StrNumTemp);
            
    result result.Add(temp);
        }
        return 
    result;
    }

    BigNum BigNum::Fac()
    {
        
    BigNum result("1");
        for(
    BigNum i("1"); i.num.length() != num.length() || i.num.compare(num) <= 0i.Add(BigNum("1")))
            
    result result.Mul(i);
        return 
    result;
    }

    BigNum BigNum::operator+(const BigNum_num)
    {
        return 
    this->Add(_num);
    }

    BigNum::~BigNum(void)
    {


    "main.cpp"
    PHP Code:
    #include "BigNum.h"
    #include <iostream>
    using namespace std;
    void main()
    {
        
    BigNum a("2500");
        
    BigNum b("3628800");
        
    BigNum c("10");
        
    cout<<a.Fac().ToStr(); //in ra ket cua qua 2500!
        //cout<<b.Mul(c).ToStr();
        
    cin.get();

    Chuyển sang nhân cơ số 10^9 cho nhanh

 

 
Trang 1/2 1 2 cuốicuối

Quyền sử dụng

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