Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 9 trên tổng số 9 kết quả

Đề tài: Meta Programming và Lý thuyết số

  1. #1
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Mặc định Meta Programming và Lý thuyết số

    Lý thuyết số là lĩnh vực Toán học áp dụng khá nhiều vào thực tế, tuy nhiên nhìn từ góc độ Lập trình thì nó dường như ít được coi trọng, nếu được coi trọng thì nó chỉ "hời hợt" với giải thuật mang trong mình cái speed chậm chạp. Kỹ thuật Meta-programming đã xâm nhập nhằm khắc phục nhược điểm này; vậy nó được dùng để giải quyết các vấn đề về lý thuyết số như thế nào? Sau đây Peter lần lượt sẽ giới thiệu với các bạn vấn đề áp dụng kỹ thuật Meta-programming (Ở đây Peter xin được viết tắt là M-P) trong giải các bài toán lý thuyết số. Để có thể nắm được phần này xin mời các bạn kiếm cho mình cuốn "Số học thuật toán" của thầy Hà Huy Khoái (nguyên Viện trưởng Viện Toán học Việt Nam) biên soạn. (Nếu ai không tìm được Peter sẽ share!).


    p/s: Peter đang xây dựng bài viết; sẽ tiếp tục! Mong các bạn chờ. OK? Chủ đề tạm Close!
    Attached Files Attached Files
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Đã được chỉnh sửa lần cuối bởi peterdrew : 27-09-2010 lúc 03:35 PM. Lý do: Up file đính kèm!

  2. #2
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Sau đây chúng ta đi từ những vấn đề đơn giản nhất, sau đó sẽ đi dần đến các mục phức tạp,...

    Vấn đề 1: Kiểm tra tính chia hết của hai số nguyên (dương):

    Số nguyên dương a được gọi là chia hết cho số nguyên dương b nếu và chỉ nếu Tồn tại số nguyên dương c sao cho a=b*c. Khi b=0 thì rõ ràng phép chia không thực hiện được; bình thường chúng ta có thể xây dựng một hàm kiểm tra việc chia hết của hai số nguyên dương như sau:
    PHP Code:
    int Divisible(int u,int v)
    {
        if (
    v)
            if (
    u%v)
                return 
    0;
            else
                return 
    1;
        else
            return -
    1;

    Và dùng nó bình thường như sau:

    PHP Code:
    int main()
    {
        
    cout<<Divisible(2,3);  //Trả về 0; vì không chia hết
        
    cout<<Divisible(2,2);  //Trả về 1; vì chia hết
        
    cout<<Divisible(2,0);  //Trả về -1; vì chia cho 0
        
    return 0;

    Ở đây Peter quy định:
    - Nếu b khác 0 và a không chia hết cho b thì Divisible() trả về 0.
    - Nếu b khác 0 và a chia hết cho b thì Divisible() trả về 1.
    - Còn nếu b bằng 0 thì Divisible() trả về -1.

    Và khi làm với M-P thì chúng ta xây dựng nó như sau:
    PHP Code:
    template <int uint v>
    struct Divisible
    {
        
    enum value == };
    };

    template <int u>
    struct Divisible<u0>
    {
        
    enum value = -};
    }; 
    Dĩ nhiên sử dụng M-P này:
    PHP Code:
    int main()
    {
        
    cout<<Divisible<2,3>::value<<endl;  //Trả về 0; vì không chia hết
        
    cout<<Divisible<2,2>::value<<endl;  //Trả về 1; vì chia hết
        
    cout<<Divisible<2,0>::value<<endl;  //Trả về -1; vì chia cho 0
        
    return 0;

    Các bạn hãy thử nghiệm chúng nhé. (Phần sau sẽ tiếp tục những vấn đề khác).

  3. #3
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 2: Giai thừa của một số nguyên dương

    Tiếp tục Peter xin giới thiệu kỹ thuật này với việc tính giai thừa của một số nguyên dương bất kỳ.

    Như chúng ta thấy: Giai thừa của một số được tính thông qua một hàm đệ quy, hoặc một hàm có vòng lặp. Đây chính là cách làm thông thường như vậy:
    Dùng đệ quy:
    PHP Code:
    unsigned factorial(unsigned n
    {
        if (
    == 0)
            return 
    1;
        return 
    factorial(1);

    Hoặc vòng lặp:
    PHP Code:
    unsigned factorial(unsigned n
    {
        
    unsigned gt=1;
        if (
    n==0)
            return 
    1;
        else 
        {
            for (
    int i=1;i<=n;i++)
                
    gt*=i;
            return 
    gt;
        }

    Và cách gọi hàm chung cho cả hai hàm này trong main() là:
    PHP Code:
    int main()
    {
        
    unsigned n;
        
    cin>>n;
        
    cout<<n<<"!= "<<factorial(n);
        return 
    0;

    Còn với M-P thì chúng ta lại xây dựng một template factorial như sau:
    PHP Code:
    template <int n>
    struct factorial 
    {
        
    enum value factorial<1>::value };
    };

    template <>
    struct factorial<0
    {
        
    enum value };
    }; 
    Với việc xây dựng một template như vậy thì chúng ta gọi M-P trong main() - Hoặc bất cứ ở đâu cần đến:
    PHP Code:
    int main()
    {
        
    cout<<"2!= "<<factorial<2>::value<<endl;
        return 
    0;

    Đây là một phần quan trọng, tuy nhàm chán nhưng các bạn sẽ thấy tốt sau khi Peter viết hết và tổng kết sử dụng kỹ thuật M-P này. OK?

  4. #4
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 3: Phần nguyên và phần thập phân của một số thực

    Trong môn Toán chắc các bạn thường xuyên phải tiếp xúc với hai loại hàm phổ dụng, đó là Hàm Phần nguyên (Có ký hiệu trong Toán học là [], ví dụ [2.3]=2) và Hàm phần lẻ (phần thập phân, có ký hiệu toán học là {}, ví dụ {2.3}=0.3) - Các tài liệu toán của thầy Phan Huy Khải nói rất nhiều về vấn đề này. Các tính chất của hàm này được áp dụng rất rộng rãi trong Tin học, vì thế mà trong thư viện của các ngôn ngữ Lập trình luôn có mặt những hàm này. Sau đây chúng ta sơ lược về cách dùng thông thường và dùng M-P xây dựng chúng!

    Trong math.h thì hàm Phần nguyên có prototype là floor(); còn hàm Phần lẻ có prototype ceil(). Với cách làm thông thường thì chúng ta chỉ cần include math.h là sử dụng được. Tuy nhiên nếu không cần đến math.h thì cũng có một cách khác là:
    PHP Code:
    floor(xtương đương với (int)x;
    ceil(xtương đương với x-(int)x
    Như thế hàm phần nguyên chúng ta xây dựng thông thường như sau:
    PHP Code:
    int Floor(float x)
    {
        return (int)
    x;

    Hàm phần lẻ:
    PHP Code:
    float Ceil(float x)
    {
        return 
    x-(int)x;

    Gọi hai hàm này trong main():
    PHP Code:
    int main()
    {
        
    cout<<"[2.3]= "<<Floor(2.3)<<endl;
        
    cout<<"{2.3}= "<<Ceil(2.3)<<endl;
        return 
    0;

    Với M-P thì:
    Phần nguyên của một số (kiểu T):
    PHP Code:
    template <typename T>
    struct Floor
    {
        static 
    inline int value (T a)
        { return (
    1); }
    }; 
    Phần lẻ một số (kiểu T):
    PHP Code:
    template <typename T>
    struct Ceil
    {
        static 
    inline int value (T a)
        { return (
    ); }
    }; 
    OK?

  5. #5
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 4: Kiểm tra tính chẵn/lẻ của một số nguyên dương

    Một số được gọi là chẵn nếu số đó chia hết cho 2, và ngược lại, một số được gọi là lẻ nếu nó không chia hết cho 2 (Quá dễ nhỉ!). Như vậy làm sao để kiểm tra nó là chẵn hay lẻ? Có rất nhiều cách, trong đó đại diện truyền thống vẫn là:
    Hàm kiểm tra một số là số chẵn hay không:
    PHP Code:
    int IsEven(int u)
    {
        if (
    u%2==0)
            return 
    1;
        else
            return 
    0;

    Hàm kiểm tra một số là số lẻ hay không:
    PHP Code:
    int IsOdd(int u)
    {
        if (
    u%2!=0)
            return 
    1;
        else
            return 
    0;

    Dĩ nhiên hai hàm này có điểm tương đồng đối ngược, nhưng Peter xây dựng ra như vậy để tiện sau này giải quyết các bài toán số học lớn (hữu ích đó); các quy ước cho nó là gì? À,
    Với hàm kiểm tra Chẵn (IsEven) thì:
    - Nếu u là số chẵn thì hàm trả về 1.
    - Ngược lại thì hàm trả về 0. (Chúng ta không nói u là số lẻ!).
    Với hàm kiểm tra Lẻ (IsOdd) thì:
    - Nếu u là số lẻ thì hàm trả về 1.
    - Ngược lại thì hàm trả về 0. (Mà chúng ta không nói u là số chẵn!)
    Việc gọi nó cũng dễ dàng trong main() hoặc bất cứ đâu:
    PHP Code:
    int main()
    {
        
    int n;
        
    cout<<"n= "<<endl;
        
    cin>>n;
        
    cout<<"IsEven("<<n<<") la: "<<IsEven(n)<<endl;
        
    cout<<"IsOdd("<<n<<") la: "<<IsOdd(n);
        return 
    0;

    Nhìn chung như vậy cũng OK rồi đó; nhưng chúng ta hãy chuyển qua M-P xem sao?!: Với M-P thì chúng ta dùng các template kế thừa từ những cái trước đó (phần trước) mà chúng ta đã làm:
    PHP Code:
    template <int u>
    struct IsEven
    {
        
    enum value Divisible<u2>::value };
    };

    template <int u>
    struct IsOdd
    {
        
    enum value Divisible<u2>::value == };
    }; 
    À, ra vậy, chúng ta vận dụng lại Divisible<> ở Vấn đề 1; còn gọi nó như thế nào? Đây:
    PHP Code:
    int main()
    {
        
    cout<<"IsEven(2) la: "<<IsEven<2>::value<<endl;  //Trả về 1
        
    cout<<"IsOdd("2") la: "<<IsOdd<2>::value<<endl;  //Trả về 0
        
    cout<<"IsEven(3) la: "<<IsEven<3>::value<<endl;  //Trả về 0
        
    cout<<"IsOdd("3") la: "<<IsOdd<3>::value<<endl;  //Trả về 1
        
    return 0;

    OK? Chúc vui vẻ!

  6. #6
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Mặc định Meta Programming và Lý thuyết số

    Vấn đề 5: Ước chung lớn nhất của hai số nguyên dương

    Ước chung lớn nhất của hai số nguyên dương bất kỳ chẳng phải là xa lạ gì; giải thuật Ơclit là một giải thuật vô cùng tối ưu và được áp dụng rộng rãi; tuy nhiên với các số lớn thì e rằng nó là một vấn đề không nhỏ. Chúng ta sẽ vận dụng M-P vào vấn đề này. Trước khi đi vào trọng tâm Peter xin đưa ra một hàm tìm Ước chung lớn nhất của hai số nguyên dương bất kỳ thông thường (Trong Toán học thì chúng ta ký hiệu Ước chung lớn nhất của hai số là (a,b), điều đó có nghĩa là d=(a,b) thì d là ước chung lớn nhất của a và b; ngược lại Bội chung nhỏ nhất được ký hiệu là [a,b]; và đẳng thức sau luôn đúng a*b=[a,b]*(a,b). Hai số a và b có (a,b)=1 được gọi là hai số "Nguyên tố cùng nhau"). Ký hiệu hàm là gcd().
    Theo công thức truy toán: gcd(m, n) = gcd(n, m mod n) ta có:
    PHP Code:
    int gcd(int m,int n)
    {
        return (
    n==0)?m:gcd(n,m%n);

    Sau đó gọi hàm này như sau:
    PHP Code:
    int main()
    {
        
    int n,m;
        
    cout<<"m= "<<endl;
        
    cin>>m;
        
    cout<<"n= "<<endl;
        
    cin>>n;
        
    cout<<"Uoc chung lon nhat cua "<<m<<" va "<<n<<" la: "<<gcd(n,m)<<endl;
        return 
    0;

    Khi đó chúng ta có thể tìm ước chung lớn nhất của nhiều số cùng một lúc; Còn dùng M-P chúng ta làm như sau:
    PHP Code:
    template <int uint v>
    struct gcd
    {
        
    enum value gcd<vv>::value };
    };

    template <int u>
    struct gcd<u0>
    {
        
    enum value };
    };

    template <>
    struct gcd<00>
    {
        
    enum value = -};
    }; 
    Các công thức nêu trên chỉ là tính chất của Ước chung lớn nhất thôi; duy chỉ có điều là chúng ta quy ước rằng gcd(0,0)=-1. OK không?
    Chúng ta gọi chúng kiểu thế này:
    PHP Code:
    int main()
    {
        
    cout<<"Uoc chung lon nhat cua 2 va 3 la: "<<gcd<2,3>::value<<endl;
        return 
    0;

    Tạm thời như vậy đã. Đó là những việc làm cơ bản để chúng ta tiến hành sâu vào Lý thuyết số sau này. Chúc vui vẻ. Hôm nay post nhiều quá, mệt thật.

  7. #7
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 6: Bội chung nhỏ nhất của hai số nguyên dương

    Ước chung lớn nhất và Bội chung nhỏ nhất của 2 số nguyên dương gắn liền và phổ dụng nhất trong lĩnh vực Số học thuật toán; chúng ta thường xuyên phải làm việc với chúng. Như vấn đề 5 đã thông tin thì việc tính Bội chung nhỏ nhất của 2 số nguyên dương bằng tích hai số nguyên dương đó chia cho Ước chung lớn nhất của hai số nguyên dương đó. Ngoài ra chúng ta còn có thể tính nó thông qua các vòng lặp (cái này ít dùng hơn). Và theo hướng của Vấn đề 5 thì chúng ta xây dựng hàm tính Bội chung nhỏ nhất của hai số nguyên dương là (ký hiệu của hàm lcm()):
    PHP Code:
    int lcm(int m,int n)
    {
        return 
    m*n/gcd(m,n);

    Chúng ta gọi nó cũng chẳng có gì là khó khăn cả:
    PHP Code:
    int main()
    {
        
    int n,m;
        
    cout<<"m= "<<endl;
        
    cin>>m;
        
    cout<<"n= "<<endl;
        
    cin>>n;
        
    cout<<"Boi chung nho nhat cua "<<m<<" va "<<n<<" la: "<<lcm(n,m)<<endl;
        return 
    0;

    Đến đây chúng ta thử với M-P xem sao?:
    PHP Code:
    template <int mint n>
    struct lcm
    {
        
    enum value gcd<mn>::value };
    }; 
    Chính lúc này chúng ta tận dụng lại kết quả từ vấn đề 5. Gọi trong main():
    PHP Code:
    int main()
    {
        
    cout<<"Boi chung nho nhat cua 2 va 3 la: "<<lcm<2,3>::value<<endl;
        return 
    0;

    Các bạn thử xem thế nào?

  8. #8
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 7: Kiểm tra số nguyên tố cùng nhau

    Trong khi thao tác với các con số nhiều lúc các bạn gặp phải cụm từ hai số nguyên tố cùng nhau!; lúc đó có bạn nghĩ rằng đó phải là 2 số nguyên tố gần nhau. Hì, sai mất rồi đó; vậy nên trong Vấn đề 5 Peter đã khái quát qua (dẫn các bạn trước khi vào vấn đề này) là: Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau khi và chỉ khi Ước chung lớn nhất của chúng là 1; tức là (a,b)=1; chứ không hẳn a và b phải là 2 số nguyên tố đứng gần nhau (hoặc có một cái hiểu tương tự), dĩ nhiên nếu a và b là hai số nguyên tố khác nhau thì chúng cũng thoả mãn tính chất là hai số "nguyên tố cùng nhau" (Lẫn lộn quá, nhưng các bạn chú ý cho điều này).

    Vậy làm sao để kiểm tra chúng nguyên tố cùng nhau hay không? Rất đơn giản là (ký hiệu hàm là CoPrime()):
    - Nếu ước chung lớn nhất của chúng khác 1 thì trị trả về cho hàm kiểm tra là 0, báo hiệu hai số không nguyên tố cùng nhau.
    - Ngược lại, thì trị trả về cho hàm kiểm tra là 1, báo hiệu hai số nguyên tố cùng nhau.

    Và chúng ta xây dựng hàm kiểm tra theo lối thông thường này như sau:
    PHP Code:
    int CoPrime(int m,int n)
    {
        return 
    gcd(m,n)==1?1:0;

    Và chẳng ai còn lạ gì cách gọi hàm này cả:
    PHP Code:
    int main()
    {
        
    cout<<CoPrime(2,3)<<endl;
        return 
    0;

    M-P chúng ta dùng cho trường hợp này sẽ là:
    PHP Code:
    template <int mint n>
    struct CoPrime
    {
        
    enum value gcd<mn>::value == };
    }; 
    Gọi M-P này trong main():
    PHP Code:
    int main()
    {
        
    cout<<CoPrime<2,3>::value<<endl;
        return 
    0;

    He he, đọc những cái này thấy rời rạc quá; Peter viết vậy cũng thấy chán tay. Nhưng sau này chúng ta sẽ thấy Hiệu quả của công việc nhàm chán này. OK?

  9. #9
    Ngày gia nhập
    01 2010
    Nơi ở
    до свидания!
    Bài viết
    1,766

    Vấn đề 8: Số các ước số nguyên dương của một số nguyên dương

    Trong toán lý thuyết số thì vấn đề về liệt kê các ước nguyên dương của một số nguyên dương chiếm một vị trí cũng khá quan trọng, số các ước số nguyên dương của một số nguyên dương n được cho bởi công thức sau:
    Công thức toán học Latex; các bạn thường gặp một bài toán phổ biến là Phân tích một số ra tích các thừa số nguyên tố (mà ngày xưa học lớp 6 Peter mới được tiếp cận); nhìn thấy các bạn giải quyết chúng khá đơn giản bằng các vòng lặp for. Đó là:
    PHP Code:
    int NoOfDivisor(int n)
    {
        
    int dem=0;
        for (
    int i=1;i<=n;i++)
            if (
    n%i==0)
                
    dem++;
        return 
    dem;

    Khi dùng nó được gọi như sau:
    PHP Code:
    int main()
    {
        
    int n;
        
    cout<<"n= ";
        
    cin>>n;
        
    cout<<"So cac uoc nguyen duong cua "<<n<<" la: "<<NoOfDivisor(n);
        return 
    0;

    Với n tương đối lớn thì việc làm trên cũng không được hay lắm. Chúng ta áp thằng M-P vào đây xem thế nào?:
    PHP Code:
    template <int Startint End>
    struct NumDivisorsLoop
    {
        
    enum value Divisible<EndStart>::value +NumDivisorsLoop<Start 1End>::value };
    };

    template <int End>
    struct NumDivisorsLoop<EndEnd>
    {
        
    enum value };
    };

    template <int n>
    struct NoOfDivisor
    {
        
    enum value NumDivisorsLoop<1n>::value };
    }; 
    Và gọi nó:
    PHP Code:
    int main()
    {
        
    cout << IsOddNoOfDivisor <3>::value>::value  << endl;
        
    cout << IsOddNoOfDivisor <25>::value>::value << endl;
        
    cout << IsOddNoOfDivisor <47>::value>::value << endl;
        return 
    0;

    Cái IsOdd<> các bạn đã được theo dõi từ các vấn đề trước rồi (mời các bạn xem lại).

    Hôm nay rảnh rảnh ngồi viết, nhưng thấy Đại lễ mà chẳng đi đâu chơi, kể cũng chán, hì, viết tạm vậy thôi đã. Chúc anh em vui vẻ, mừng Đại lễ 1000 năm Thăng Long thành công tốt đẹp (Tối nay bắn pháo hoa mà đường Hà Nội tắc quá, Peter vừa ra khỏi ngõ thì quay về, đành ngồi xem trên TV và viết mấy thứ linh tinh thế này thôi.).
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

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

  1. Geo meta là gì ? Tool tạo Geo Meta nhanh chóng cho website ?
    Gửi bởi ttsdung1388 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 29-01-2013, 08:41 AM
  2. Lập Trình QT C++ GUI Programming with Qt 3
    Gửi bởi haian trong diễn đàn Tài liệu, ebooks và công cụ
    Trả lời: 1
    Bài viết cuối: 09-11-2012, 09:07 AM
  3. cần tìm công việc về C programming
    Gửi bởi panfider trong diễn đàn Tuyển dụng - Việc làm CNTT
    Trả lời: 2
    Bài viết cuối: 14-06-2010, 08:42 PM
  4. [Lý Thuyết Đồ Thị]. đồ thị có trọng số
    Gửi bởi hoangedward trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 26-03-2010, 03:23 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