Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: Tính phần dư của phép chia_với số lớn ??? Ai có cách j` giúp e với!

  1. #1
    Ngày gia nhập
    07 2007
    Bài viết
    2

    Mặc định Tính phần dư của phép chia_với số lớn ??? Ai có cách j` giúp e với!

    Cho một số nguyên dương n viết dưới dạng thập phân gồm k chữ số (k < 10000), một số nguyên dương a viết dưới dạng thập phân gồm l chữ số (l < 10000) và một số nguyên dương m (m < 10000). Hãy tính phần dư trong phép chia a^m(a mũ m) cho n.

    ==> ai có thể hướng dẫn hộ e phương hướng giải quyết nó thê nào hok !
    nghĩ mãi mà hok ra ???mong các pro chỉ giáo !

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Mình đặt L=33216.

    Bạn hãy xây dựng:
    1/ hàm đọc xâu biểu diễn số ở dạng thập phân (dài không quá 9999 chữ số) và đổi nó thành số (nhị phân). Số này sẽ có không quá L bit. Trên một compiler 32 bit, nó có thể chứa trong một mảng không quá 1038 từ unsigned.

    2/ các phép dịch trái, dịch phải số L bit.
    3/ phép cộng, trừ số L bit.
    4/ phép nhân số L bit với số L bit (mod n).
    5/ phép bình phương số L bit (mod n).
    6/ phép lũy thừa a^m mod n.

    ad 6/. Dựa vào công thức x*y mod n = (x mod n)*(y mod n) mod n, ta có thể tính a^m mod n bằng cách quét từng bit của m từ bit cao nhất đến bit thấp nhất, cứ quét 1 bit thì bình phương tích lên 1 phát và nếu bit ấy bằng 1 thì lại nhân a vào tích. Bằng mã giả thì phép lũy thừa ấy như thế này:
    Code:
    void expmod(Bigint n, Bigint a, Bigint m)
    {
        Bigint p = 1;
        for(int i = L-1; i>=0; i--)
        {
            p = p*p % n;
            if( m[i] == 1 ) p = p*a % n;
        }
        return p;
    }
    Phép bình phương riêng là để tính cho nhanh. Nếu ít thời gian thì bạn có thể không cần viết phép bình phương riêng mà dùng luôn phép nhân để tính bình phương.
    Đã được chỉnh sửa lần cuối bởi Ada : 19-05-2008 lúc 12:45 PM.

  3. #3
    Ngày gia nhập
    07 2007
    Bài viết
    2

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Mình đặt L=33216.

    Bạn hãy xây dựng:
    1/ hàm đọc xâu biểu diễn số ở dạng thập phân (dài không quá 9999 chữ số) và đổi nó thành số (nhị phân). Số này sẽ có không quá L bit. Trên một compiler 32 bit, nó có thể chứa trong một mảng không quá 1038 từ unsigned.

    .
    Cảm ơn bạn đã bỏ ít thời gian jiúp mình !

    Cái phần 1 mà bạn bảo xây dựng ! chuyển đổi thập phân thì theo cách thông thường thì dễ ,nhưng ko thể chuyển xâu với số lớn như vậy !
    ==> Cái này mình cũng chưa nghĩ ra ..hic ...hic ... bạn hướng dẫn giúp mình được ko ? Nếu bạn co code thì cho mình xin với !
    Thanks bạn !

  4. #4
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi nguoimaulanh Xem bài viết
    chuyển đổi thập phân thì theo cách thông thường thì dễ ,nhưng ko thể chuyển xâu với số lớn như vậy !
    ==> Cái này mình cũng chưa nghĩ ra ..hic ...hic ... bạn hướng dẫn giúp mình được ko ?
    Chuyển xâu lớn thành số cũng chẳng khác gì chuyển xâu thông thường.

    Để cho nhanh hơn một chút bạn có thể code riêng một hàm làm phép nhân số L bit với số nhỏ (số nằm gọn trong 1 biến unsigned) và một hàm làm phép cộng số L bit với số nhỏ. Và trong thủ tục chuyển xâu này bạn sẽ dùng chúng để nhân số L bit với 10 và cộng số L bit với một số nhỏ hơn 10.

    Sau đó bạn hãy nghĩ xem có thể dùng chúng nhân với 100, 1000, 10000,..., 1E9 và cộng với số nhỏ hơn 100,1000,10000,...,1E9 để tăng tốc thủ tục chuyển xâu thành số hay không.

    Trích dẫn Nguyên bản được gửi bởi nguoimaulanh Xem bài viết
    Nếu bạn co code thì cho mình xin với !
    Code thì mình không có. Bạn có thể tham khảo code thư viện nguồn mở GMP ( http://gmplib.org/ ). Nhưng thư viện này dùng các thuật toán khá phức tạp. Nếu thực sự bạn chỉ làm bài này để phục vụ cho 1 bài tập chứ không có những nhu cầu code các chương trình thực tiễn về số lớn thì mình nghĩ thay vì đọc code GMP, bạn tự code sẽ nhanh hơn.

  5. #5
    Ngày gia nhập
    07 2007
    Bài viết
    2

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Mình đặt L=33216.

    Bạn hãy xây dựng:
    1/ hàm đọc xâu biểu diễn số ở dạng thập phân (dài không quá 9999 chữ số) và đổi nó thành số (nhị phân). Số này sẽ có không quá L bit. Trên một compiler 32 bit, nó có thể chứa trong một mảng không quá 1038 từ unsigned.

    2/ các phép dịch trái, dịch phải số L bit.
    3/ phép cộng, trừ số L bit.
    4/ phép nhân số L bit với số L bit (mod n).
    5/ phép bình phương số L bit (mod n).
    6/ phép lũy thừa a^m mod n.

    ad 6/. Dựa vào công thức x*y mod n = (x mod n)*(y mod n) mod n, ta có thể tính a^m mod n bằng cách quét từng bit của m từ bit cao nhất đến bit thấp nhất, cứ quét 1 bit thì bình phương tích lên 1 phát và nếu bit ấy bằng 1 thì lại nhân a vào tích. Bằng mã giả thì phép lũy thừa ấy như thế này:
    Code:
    void expmod(Bigint n, Bigint a, Bigint m)
    {
        Bigint p = 1;
        for(int i = L-1; i>=0; i--)
        {
            p = p*p % n;
            if( m[i] == 1 ) p = p*a % n;
        }
        return p;
    }
    Phép bình phương riêng là để tính cho nhanh. Nếu ít thời gian thì bạn có thể không cần viết phép bình phương riêng mà dùng luôn phép nhân để tính bình phương.
    mình cũng bik dùng nhị phân là tối ưu và nhanh hơn ! Nhưng nghe bạn nói mình cũng hiểu ít ít ! hic hic !!!

    Nếu mình làm với số thường ko chuyển sang nhị phân ! áp dụng đúng công thức như "6)" của bạn ở trên : thì có : (a mod n)^m mod n .

    Lại có m là số <10000(ko phải số chữ số 10000) .

    Code:
    t=1;
    for (i=0;i<m;i++)
    {
      t*= a mod n
    }
    return t mod n
    như zậy có ổn ko nhỉ ! Mình cũng mới học C mong bạn júp đỡ ! hì hì !

    mà cái phần nhân , chia số nhị phân (với sô bit <10000) mình tìm code hoài mà ko thấy ! bạn tìm hộ mình với ! search mã mà ko thấy .... hic...hic

  6. #6
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Mặc định Tính phần dư của phép chia_với số lớn ??? Ai có cách j` giúp e với!

    Trích dẫn Nguyên bản được gửi bởi nguoimaulanh Xem bài viết
    mình cũng bik dùng nhị phân là tối ưu và nhanh hơn ! Nhưng nghe bạn nói mình cũng hiểu ít ít ! hic hic !!!

    Nếu mình làm với số thường ko chuyển sang nhị phân !
    Các số lớn kia có thể dùng cơ số khác. Nhưng cơ số càng nhỏ tính càng chậm.

    Cơ số 2^32 là tối ưu đối với máy 32 bit, vì mỗi phép cộng/nhân cơ bản xử lý 32 bit. Nếu bạn dùng cơ số 10 thì mỗi phép cộng/nhân cơ bản chỉ xử lý được khoảng hơn 3 bit => phép cộng (~O(n)) sẽ chậm gấp 10 lần, phép nhân (~O(n^2)) sẽ chậm gấp 100 lần và phép lũy thừa (~O(n^3)) sẽ chậm gấp 1000 lần.

    Đấy là chưa kể lập trình phép tính trên cơ số 10^n rắc rối hơn lập trình cho cơ số 2^n. Phép tính lũy thừa chẳng hạn: đề bài viết m (số mũ của lũy thừa) là một số chứ không phải là một xâu, nghĩa là m đã cho ở dạng nhị phân rồi.



    Trích dẫn Nguyên bản được gửi bởi nguoimaulanh Xem bài viết
    áp dụng đúng công thức như "6)" của bạn ở trên : thì có : (a mod n)^m mod n .

    Lại có m là số <10000(ko phải số chữ số 10000) .

    Code:
    t=1;
    for (i=0;i<m;i++)
    {
      t*= a mod n
    }
    return t mod n
    như zậy có ổn ko nhỉ ! Mình cũng mới học C mong bạn júp đỡ ! hì hì !
    Là "đúng" nhưng không "ổn"! :P Vì bạn phải làm khoảng 10000 phép nhân số lớn, trong khi theo công thức "của mình" thì chỉ cần làm khoảng 20 phép nhân thôi.

    Thật ra, công thức "của mình" cũng mới chỉ là công thức cơ bản thôi. Mình đưa công thức này ra để giới thiệu vấn đề là chính chứ không định bảo bạn dùng nó ở nguyên dạng như thế. Cần phải cải tiến nó thêm 1 chút. Lúc nào bạn sắp làm đến phép lũy thừa, mình sẽ nói kỹ hơn.




    Trích dẫn Nguyên bản được gửi bởi nguoimaulanh Xem bài viết
    mà cái phần nhân , chia số nhị phân (với sô bit <10000) mình tìm code hoài mà ko thấy ! bạn tìm hộ mình với ! search mã mà ko thấy .... hic...hic
    Mình chỉ có thể giúp bạn code chứ không giúp bạn tìm code được. Sorry.

    Về việc chọn chọn cấu trúc dữ liệu để chứa các số lớn, mình đã nói rồi nhưng bây giờ nhắc lại: cấu trúc dữ liệu hiệu quả nhất và cũng đơn giản nhất là mảng.

    Tạm gác qua bên phép tính nhân chia. Bạn có thể bắt đầu từ phép tính đơn giản nhất, phép cộng. Hãy nói rõ thắc mắc và khó khăn của bạn trong phép tính này, hoặc post code của bạn lên đây.

  7. #7
    Ngày gia nhập
    12 2007
    Bài viết
    2

    Bài này có một thuật toán để giải quyết, chỉ mất khoảng 4-5 dòng xử lý:
    Code:
    (a^m) mod n= [(a mod n)^(m mod n)] mod n
    Cứ viết thử ra thấy ngay hiệu quả hìhì. Bài này mình chỉ viết bằng C thôi, C++ ko học nên ko biết. Còn thuật toán như nhau cả. Có file test đính kèm ở dưới í
    Attached Files Attached Files
    Đã được chỉnh sửa lần cuối bởi conmatrongnhaxi : 24-05-2008 lúc 05:20 PM.

  8. #8
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi conmatrongnhaxi Xem bài viết
    Bài này có một thuật toán để giải quyết, chỉ mất khoảng 4-5 dòng xử lý:
    Code:
    (a^m) mod n= [(a mod n)^(m mod n)] mod n
    Công thức này sai rồi.

    Ví dụ, 2^10 mod 5 = 1024 mod 5 = 4,
    nhưng (2 mod 5)^(10 mod 5) mod 5 = 2^0 mod 5 = 1 mod 5 = 1.

  9. #9
    Ngày gia nhập
    04 2008
    Nơi ở
    Phu yen
    Bài viết
    10

    thử nha :
    a=b*n+q
    a^m=(b*n+q)^m
    a^m=(b*n)^m + q *(b*n)^(m-1) + ... + q^m
    => " số dư phép chia a^m cho n bằng với số dư phép chia q cho n " OK ?
    cho nên code:

    for(int i=1;i<m;i++) {
    a=a%n;
    a=a*a;
    }

    printf("so du can tim la : %d ",a);

    như vậy số lớn nhất cũng chỉ 9999*9999 vẫn thỏa trong phạm vi "unsign long"
    ------------------------------
    he he
    ------------------------------
    mình làm như vậy được không nhỉ ???

  10. #10
    Ngày gia nhập
    01 2008
    Bài viết
    240

    Trích dẫn Nguyên bản được gửi bởi xinchigiao Xem bài viết
    thử nha :
    a=b*n+q
    a^m=(b*n+q)^m
    a^m=(b*n)^m + q *(b*n)^(m-1) + ... + q^m
    => " số dư phép chia a^m cho n bằng với số dư phép chia q cho n " OK ?
    cho nên code:

    for(int i=1;i<m;i++) {
    a=a%n;
    a=a*a;
    }

    printf("so du can tim la : %d ",a);

    như vậy số lớn nhất cũng chỉ 9999*9999 vẫn thỏa trong phạm vi "unsign long"
    ------------------------------
    he he
    ------------------------------
    mình làm như vậy được không nhỉ ???
    the mình nghĩ thì số này rất lớn có thể đến hàng trăm,hàng nghìn số đó chứ
    Time

Các đề tài tương tự

  1. Trả lời: 0
    Bài viết cuối: 16-03-2012, 07:05 PM
  2. cách ghi phần tử vào mảng lập trình c#.giúp em với
    Gửi bởi hoangkien trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 01-04-2011, 09:41 PM
  3. kiểm tra phần cứng máy tính, giúp mình?
    Gửi bởi huutrieu2005 trong diễn đàn Thắc mắc chung
    Trả lời: 6
    Bài viết cuối: 25-03-2009, 01:53 PM

Quyền hạn của bạn

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