Bài giảng cấu trúc dữ liệu và giải thuật

File download: Bai giang CTDL (https://4fire.files.wordpress.com/2007/06/bai-giang-ctdl.pdf) (900 Kb). Bản cập nhật ngày 28/06/2007.

Số bè bạn và số hoàn hảo

Số bè bạn và số hoàn hảo 

Chủ đề của bài báo: C++, Thuật toán, Số nguyên tố, Số bè bạn, Số hoàn hảo.

Cập nhật ngày 16/03/2014: Hai số hoàn hảo đầu tiên, 6 và 28, đã được Pythogoras và các người bạn của ông tìm ra từ thời Hy lạp cổ đại. Hai số này có, hoặc không, sự liên hệ tới cấu trúc của vũ trụ: Chúa tạo ra thế giới trong 6 ngày, mặt trăng quay quanh trái đất theo một chu kỳ 28 ngày. Euler đã chứng minh được tất cả các số hoàn hảo chẵn đều có dạng p(p+1)/2 trong đó p là một số nguyên tố Mersenne. Một bài toán vẫn chưa có lời giải là: liệu có tồn tại một số hoàn hảo lẻ?

Trong quá trình học lập trình và thuật toán, đa số trong chúng ta đã từng nghe tới và làm các bài tập về các số bè bạn (friend numbers) và số hoàn hảo (perfect numbers). Các số bè bạn n, m là hai số nguyên mà tổng ước số của n bằng m và tổng các ước của m bằng n, ví dụ như cặp số bè bạn nhỏ nhất là 220 và 284. Các số hoàn hảo là các số mà tổng các ước thực sự của nó bằng chính nó, ví dụ như các số hoàn thiện đầu tiên là 6, 28 … Bài toán thường liên quan tới các số bè bạn và số hoàn hảo là in ra tất cả các cặp số bè bạn và các số hoàn hảo không vượt quá một số nguyên N nào đó. Đây là hai bài toán khác nhau song lại có liên quan mật thiết với nhau vì trong quá trình xây dựng giải thuật cho bài toán chúng ta đều cần đến khái niệm gọi là tổng các ước của một số nguyên. Trong trường hợp N là một số nguyên nhỏ (N < 10000) thì một thuật toán đơn giản và hết sức trực quan cũng tạm chấp nhận được là:

·           Xây dựng một hàm tính tổng ước của một số nguyên

·           Duyệt các số từ 2 tới N, nếu tồn tại hai số i, j khác nhau mà tổng ước của i bằng j và tổng ước của j bằng i thì in ra i, j. Khi đó i, j chính là một cặp số bè bạn.

·           Duyệt các số từ 2 tới N, nếu tổng ước của số đó bằng chính nó thì in ra màn hình, đó chính là một số hoàn thiện cần tìm.

Trước hết ta đi xây dựng hàm tính tổng các ước số của một số nguyên m: ta đã biết các ước số của m, nếu có sẽ không vượt quá căn bậc 2 của m (tức là sqrt(m)), và khi a là một ước của m thì m/a (m chia a) cũng là một ước của m (phần này xin đọc thêm bài báo “Số nguyên tố” để biết thêm chi tiết) nên một thuật toán hiệu quả sẽ xét các ứng cử viên có thể là ước của m nằm trong khoảng 1 tới sqrt(m) (gọi ước này là a), sau đó cộng a và m/a vào tổng ước của số m. Cài đặt cụ thể bằng ngôn ngữ C của thuật toán như sau:

int tong_uocso(int m)

{

            int i;

            int z = (int)(sqrt(m+1));

            int ret = 1;

            for(i=2;i<=z;i++)

                        if(m%i==0)

                                    ret = ret + i + (m/i);

            return ret;

}

            Sau khi đã có hàm tính tổng ước số của một số nguyên, việc in ra các số hoàn thiện trở nên dễ dàng với 1 vòng lặp, nên ta chỉ xét đoạn chương trình in ra các cặp số hoàn thiện phân biệt (không kể thứ tự của các số):

void sobeban1(int n)

{

            int i, j;

            for(i=2;i<=n;i++)

                        for(j=i+1;j<=n;j++)

                                    if(tong_uocso(i)==j&&tong_uocso(j)==i)

                                                printf(“%d %d\n”, i, j);

}

            Hầu hết các lập trình viên mới học lập trình và thuật toán sẽ dừng lại ở đây. Thuật toán in ra các cặp số bè bạn có hai vòng lặp lồng nhau, thuật toán sẽ chạy cỡ khoảng O(N) = N*(N+1)/2 bước, mỗi bước gọi tới hàm tong_uocso() hai lần để thực hiện so sánh nên độ phức tạp của thuật toán sẽ là O(N) = N2 * O(hàm tong_uocso()). Nếu N = 1000000 thì chắc chắn thuật toán không thể chạy trong thời gian 3 giây (thời gian test tối đa của các bài toán trong các cuộc thi lập trình).

            Tuy nhiên quan sát kỹ thuật toán, ta thấy rằng mỗi lần xét i trong vòng lặp thứ nhất, ta không cần thiết phải chạy một vòng lặp để xét các ứng cử viên có thể làm thành một cặp số bè bạn với i, mà chỉ cần xét số z = tong_uocso(i). Vì vậy một thuật toán hiệu quả hơn nhiều sẽ là như sau:

void sobeban2(int n)

{

            int i, z;

            for(int i=2;i<=n;i++)

            {

                        z = tong_uocso(i);

                        if(z<=n && tong_uocso(z)==i && z>i)

                                    printf(“%d %d\n”, i, j);

            }

}

            Ta cần thêm điều kiện z > i để in ra các cặp số khác nhau (vì z bây giờ đóng vai trò thay j trong thuật toán trước).

            Rõ ràng thuật toán thứ hai này có độ phức tạp nhỏ hơn nhiều so với thuật toán thứ nhất, thay vì chạy hai vòng lặp, ta chỉ cần một vòng lặp là đủ. Tất nhiên cải tiến này không thể áp dụng cho bài toán số hoàn hảo vì ta cũng chỉ cần một vòng lặp để in ra tất cả các số hoàn hảo không vượt quá N.

            Rõ ràng bây giờ các cải tiến của chúng ta, nếu có, sẽ không thể tập trung vào các vòng lặp, mà chỉ có thể nằm ở việc tính tổng ước số của mỗi số nguyên.

            Chúng ta đã biết thuật toán sàng Erastosthene để đánh dấu các số nguyên không phải là số nguyên tố (các số còn lại không được đánh dấu sẽ là số nguyên tố – có thể tham khảo trong bài báo số nguyên tố). Thuật toán sàng Erastosthene dựa trên một chi tiết hết sức tinh tế sau: nếu z là một số nguyên tố (hay hợp số) thì các bội số của z sẽ là các hợp số. Chúng ta hoàn toàn có thể áp dụng chi tiết này cho việc tính tổng ước số của các số nguyên: với bất kỳ giá trị z (z £ N) nào, z sẽ là ước số của các bội số của z nên ta sẽ cộng z với các biến chứa các tổng các ước số tương ứng với các bội số của z đó. Cũng tương tự như thuật toán sàng Erastosthene, ta sẽ sử dụng một mảng để lưu tổng ước cho tất cả các số nguyên không vượt quá N. Cụ thể thuật toán được cài đặt bằng ngôn ngữ C như sau:

void sobeban3(int n)

{

            int * s; // dùng mảng động s để lưu tổng ước của các số từ 1 tới N

            int i, z;

            int m;

            // cấp phát bộ nhớ, hàm malloc nằm trong thư viện stdlib.h

            s = (int *)malloc((n+1)*sizeof(int));

            if(s==NULL)

            {

                        printf(“Khong du bo nho”);

                        return;

            }

            // khởi tạo mảng s bằng 1 vì 1 mặc định là ước của tất cả các số nguyên

            for(i=0;i<=n;i++)

                        s[i] = 1;

            // tính s[2..n];

            m = n/2;

            for(i=2;i<=m;i++)

            {

                        z = i + i;

                        // cộng i vào các s[z], z luôn là bội số của i

                        while(z <= n)

                        {

                                    s[z] += i;

                                    z += i;

                        }

            }

            // in ra các cặp số bè bạn

            for(i=2;i<=n;i++)

                        if(s[i]<=n && s[s[i]]==i && i < s[i])

                                    printf(“%d %d\n”, i, s[i]);

           

            free(s); // giải phóng bộ nhớ

}

            Thực ra trong cài đặt trên, chúng ta có thể thay vòng lặp while trong thân vòng lặp for chính bằng một vòng lặp for, nhưng khi đó sẽ cần sử dụng các phép nhân, chậm hơn so với dùng vòng lặp while và phép cộng tích lũy vào biến z.

            Để in ra các số hoàn hảo chúng ta có thể áp dụng thuật toán tương tự với một chút sửa đổi nho nhỏ, và phần này xin dành cho bạn đọc như một bài tập.

            Chúng ta cũng có thể đo thời gian thực hiện của các thuật toán 1, 2, 3 ở trên để thấy được hiệu quả khác nhau của chúng, chẳng hạn như sau:

            float time;

            time_t start, finish; // kiểu time_t nằm trong thư viện time.h

            start = clock(); // hàm tính thời gian clock() nằm trong thư viện time.h

            sobeban1(n);

            finish = clock();

            time = (finish – start)/CLK_TCK; // hằng số CLK_TCK nằm trong thư viện time.h

            Việc tính thời gian của các thuật toán 2, 3 được thực hiện tương tự. Tôi đã chạy thử nghiệm chương trình với DevCpp và kết quả là thuật toán 3 có thể chạy tới N = 2000000 trong vòng 2 giây.

            Chú thích:

1.      O(N): ký hiệu độ phức tạp của thuật toán, thường là số phép toán thực hiện của thuật toán, với dữ liệu input có kích thước là N

           

            Mặc dù đã hết sức thận trọng và xem xét kỹ các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

                                                                                               

Hải Phòng, ngày 23, tháng  03, năm 2007
    

Nguyễn Hữu Tuân

Bài toán số nguyên tố

Bài toán số nguyên tố 

Chủ đề của bài báo: C, Thuật toán, Số nguyên tố.

Có lẽ một trong những bài toán mà tất cả các lập trình viên đều gặp phải khi học lập trình cũng như khi tham gia vào các cuộc thi lập trình là bài toán kiểm tra một số nguyên có phải là một số nguyên tố hay không. Có rất nhiều dạng phát biểu khác nhau của bài toán nhưng suy cho cùng, các lập trình viên vẫn phải viết một hàm kiểm tra với input là 1 số nguyên n, output là đúng (TRUE – 1) nếu n là một số nguyên tố và sai (FALSE – 0) nếu n không phải là một số nguyên tố. Các thuật toán kiểm tra số nguyên tố mà tôi trình bày với các bạn trong bài viết này chỉ là các thuật toán hết sức đơn giản, nhưng đủ sức đáp ứng cho nhu cầu của các lập trình viên trong các cuộc thi lập trình cũng như những công việc đòi hỏi xử lý những số nguyên không quá lớn.

Trước hết cũng nên nhắc lại khái niệm số nguyên tố (prime number): số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Theo định nghĩa này số nguyên tố là số tự nhiên và chỉ có hai ước số phân biệt, đó chính là số 1 và bản thân nó. Từ đó suy ra số 1 không phải là một số nguyên tố (có rất nhiều sinh viên mới học lập trình nhầm số 1 là số nguyên tố). Một kết quả khác cũng không kém quan trọng được rút ra đó là số 2 là số nguyên tố đầu tiên (nhỏ nhất) và cũng là số nguyên tố chẵn duy nhất.

Như vậy để kiểm tra một số nguyên có là số nguyên tố hay không, theo suy nghĩ trực quan của tất cả các lập trình viên hay thậm chí một người không hiểu biết gì về thuật toán thì chúng ta cần kiểm tra xem số đó có ước số nào khác 1 và chính nó hay không, nếu có thì đó là hợp số (combine number) còn nếu không có số nào thì đó chính là một số nguyên tố. Thuật toán đầu tiên đến với chúng ta đó là: kiểm tra các số có khả năng là ước số của n (số cần kiểm tra tính nguyên tố), các số này nằm trong khoảng từ 2 tới n – 1. Thuật toán được cài đặt bằng C đơn giản như sau:

int  ktnguyento1(int n)

{

            // hàm kiểm tra n có là số nguyên tố hay không

            // kết quả: 1 nếu đúng, 0 nếu sai

            int i;

            int kq = 1; // gia sử n là số nguyên tố

            for(i=2;i<n;i++)

                        if(n % i == 0)

                        {

                                    // n có ước số là i, không cần kiểm tra tiếp các giá trị tiếp theo

                                    kq = 0;

                                    break;

                        }

            return kq;

}

Cài đặt này rất dễ dàng chuyển thành các cài đặt trên các ngôn ngữ khác nhau Pascal, C++ … Tuy nhiên trong ngôn ngữ C khi gặp lệnh return hàm sẽ kết thúc nên cài đặt trên có thể chuyển thành dạng ngắn gọn như sau:

int  ktnguyento1(int n)

{

            // hàm kiểm tra n có là số nguyên tố hay không

            // kết quả: 1 nếu đúng, 0 nếu sai

            int i;    

            for(i=2;i<n;i++)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Hàm này vẫn chưa đúng hoàn toàn vì khi n = 1 kết quả chạy hàm là: 1 là số nguyên tố vì thế nên cần sửa lại như sau:

int  ktnguyento1(int n)

{

            // hàm kiểm tra n có là số nguyên tố hay không

            // kết quả: 1 nếu đúng, 0 nếu sai

            int i;

            if (n==1)

                        return 0;          

            for(i=2;i<n;i++)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Một số sinh viên lại cài đặt thuật toán theo kiểu khác như sau:

int  ktnguyento0(int n)

{

            // hàm kiểm tra n có là số nguyên tố hay không

            // kết quả: 1 nếu đúng, 0 nếu sai

            int i;

            int dem = 0; // đếm tổng các ước của n

                        for(i=1;i<=n;i++)

                        if(n % i == 0)

                                    dem = dem + i;

            if(dem==n+1)

return 1;

                        return 0; // tương tự như else return 0;

}

Về cài đặt thì khác nhau nhưng đều là kiểm tra các ước số của n với các ứng cử viên là từ 2 (1) cho tới n-1 (n) và tất nhiên thuật toán kiểu cộng các ước số này sẽ chạy chậm hơn trong đa số các trường hợp. Một số sinh viên lại cài đặt khác đôi chút: thay vì đếm tổng các ước số, ta đếm số các ước số lưu vào biến dem, cuối cùng so sánh biến dem với 2 để kết luận.

Trong các cài đặt trên, nếu n là số nguyên tố thì vòng lặp for sẽ chạy tới khi i = n – 1 để có thể đưa ra kết luận cuối cùng. Tuy nhiên, suy nghĩ thêm một chút chúng ta sẽ thấy rằng không cần phải kiểm tra đến giá trị i = n – 1 mà thực chất chỉ cần tới n/2 (n div 2) vì không có ước số nào của n lớn hơn n/2. Vì vậy thuật toán 2 sẽ là như sau:

int  ktnguyento2(int n)

{

            // hàm kiểm tra n có là số nguyên tố hay không

            // kết quả: 1 nếu đúng, 0 nếu sai

            int i;

            if (n==1)

                        return 0;          

            for(i=2;i<=n/2;i++)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Lại suy nghĩ thêm một chút chúng ta sẽ thấy rằng cũng không cần thiết phải kiểm tra đến giá trị n/2 mà chỉ cần đến căn bậc 2 của n là được (các bạn hãy tính toán một chút để thấy tại sao lại như vậy?). Do đó thuật toán mới (3) là như sau:

int  ktnguyento3(int n)

{

            int i;

            if (n==1)

                        return 0;          

            for(i=2;i<=(int)sqrt(n);i++)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Ở đây chúng ta cần chú ý đôi chút vì nếu chỉ để như trên thì đôi khi chương trình của chúng ta chạy không đúng, lý do là C có hai hàm sqrt để lấy căn bậc hai của một số; hàm thứ nhất là dành cho các số thực kiểu double (hàm này là hàm mà chúng ta dùng ở trên), hàm thứ hai dành cho các số phức, và bình thường nếu không include file math.h thì Turbo C sẽ dùng hàm dành cho các số phức (file complex.h, DevCpp không bị hiện tượng này).

Với cài đặt trên vẫn có thể có cải tiến được (hầu hết các sinh viên và những người mới học lập trình không để ý điều này), đó là thay vì mỗi lần lặp đều tính sqrt(n) ta chỉ cần tính một lần trước khi thực hiện vòng lặp:

int  ktnguyento3(int n)

{

            int i;

int m;

            if (n==1)

                        return 0;

            m = (int)sqrt(n);          

            for(i=2;i<=m;i++)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Thực tế chạy chương trình cho thấy nếu để nguyên cài đặt thuật toán 2 ở trên thì kết quả chạy lại chậm hơn thuật toán 1 vì mỗi bước đều phải thực hiện phép chia đối với n, nên cần phải chỉnh lại cài đặt của thuật toán 2 giống như thuật toán 3: tính m = n/2 trước khi chạy vòng lặp mới đạt được hiệu quả.

Lại để ý rằng các số nguyên tố chỉ có thể là các số lẻ trừ số 2, và do đó chúng không thể chia hết cho các số chẵn nên ta chỉ cần kiểm tra các ước số (giá trị của i) là số lẻ, do vậy thuật toán tiếp theo (4) sẽ như sau:

int  ktnguyento4(int n)

{

            int i;

int m;

if(n == 2)

            return 1;

            if (n == 1||n % 2 == 0)

                        return 0;

            m = (int)sqrt(n);

            for(i=3;i<=m;i=i+2)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

Rõ ràng so với thuật toán trước đó, số giá trị của i cần kiểm tra giảm đi một nửa. Như vậy mấu chốt trong việc tăng tốc và cải tiến thuật toán nằm ở câu lệnh thay đổi giá trị của biến điều khiển i, ta chỉ cần giảm số giá trị của i cần kiểm tra là sẽ dẫn tới một thuật toán hiệu quả hơn.

Vừa rồi ta đã loại bỏ được một nửa số giá trị của i bằng cách xét ước số 2 có thể có của n. Tiếp theo ta sẽ cải tiến thuật toán bằng cách xét ước số nguyên tố tiếp theo có thể có của n là số 3. Nếu n chia hết cho 2 hoặc 3 thì dễ dàng kết luận nó là hợp số (tất nhiên n phải khác hai giá trị đó). Ngược lại n sẽ có ước số có dạng , , ta sẽ bắt đầu với giá trị i = 5 nên sẽ chọn công thức . Nhưng nếu chỉ kiểm tra i sẽ thiếu mất ứng cử viên ở dạng  nên ta sẽ kiểm tra thêm giá trị i+2 ( ) cho đủ. Vậy thuật toán mới (5) sẽ là như sau:

int  ktnguyento5(int n)

{

            int i;

int m;

if(n == 2 || n == 3)

            return 1;

            if (n == 1||n % 2 == 0||n % 3 == 0)

                        return 0;

            m = (int)sqrt(n);

            for(i=5;i<=m;i=i+6)

                        if(n % i == 0 || n % (i+2) == 0)

                                    return 0;

            return 1;

}

            Cũng có thể cài đặt thuật toán này dựa vào nhận xét sau: nếu ta bắt đầu bằng số i  = , thì lần sau sẽ cần cộng i với 2 để kiểm tra giá trị tiếp theo của i (khi đó i sẽ có dạng ), lần sau nữa sẽ cộng i với 4 (để i lại có dạng ), lần tiếp theo lại là 2… Từ nhận xét này dẫn tới cài đặt sau (không hiệu quả hơn cài đặt trên khi chạy trên thực tế):

int  ktnguyento51(int n)

{

            int i;

int m, y;

if(n == 2 || n == 3)

            return 1;

            if (n == 1||n % 2 == 0||n % 3 == 0)

                        return 0;

            m = (int)sqrt(n);

y = 2;

            for(i=5;i<=m;i=i+y, y = 6 – y)

                        if(n % i == 0)

                                    return 0;

            return 1;

}

            Trong các bài toán mà việc kiểm tra số nguyên tố bị lặp lại nhiều lần ta cũng có thể cải thiện thuật toán kiểm tra tính nguyên tố của một số nguyên bằng cách chỉ kiểm tra các ước số có thể có của n nhưng là số nguyên tố, vì nếu n là hợp số thì chắc chắn sẽ chia hết cho một số nguyên tố nào đó nhỏ hơn nó. Vì vậy ta sẽ sinh trước một mảng các số nguyên tố (về bản chất là đánh dấu các số đó là số nguyên tố) không vượt quá giới hạn của n (giá trị lớn nhất của n). Sau đó khi kiểm tra các ước số của n chỉ cần kiểm tra xem n có chia hết cho các số nguyên tố nhỏ hơn căn bậc hai của n nằm trong mảng đã cho hay không. Để làm việc này có một thuật toán nổi tiếng gọi là sàng Erastosthene như sau:

            const int MAX_N = 10000; // giá trị lớn nhất của n

int nt[MAX_N]; // mảng đánh dấu, nt[i] = 0 nếu i là số nguyên tố, 1 nếu ngược lại

           

void sangnt(int n)

            {

                        // đánh dấu các số nguyên tố nhỏ hơn n

                        int i, k;

            for (i=2; i<n; i++)

if (nt[i] == 0) // nếu i là số nguyên tố thì các bội của i sẽ là hợp số

                                    {

                                                k = 2;

                                                // đánh dấu các bội số của i

                                    while (k*i<n)

                                                            nt[i*k++] = 1;

                                    }

            }

            Kết luận.

            Qua việc trình bày các thuật toán đơn giản để kiểm tra các số nguyên tố nhỏ, tôi hy vọng mang đến cho các bạn một thuật toán tốt để có thể sử dụng trong các cuộc thi lập trình hay các bài toán trong phạm vi nhỏ, đồng thời qua đó minh họa quá trình tinh chỉnh cài đặt một thuật toán. Có thể cùng một thuật toán nhưng với các cài đặt khác nhau, hiệu quả sẽ khác nhau, và nhiều khi hiệu quả đó lại dựa trên những chi tiết tưởng chừng như rất nhỏ nhặt, không đáng lưu tâm.

            Mặc dù đã hết sức thận trọng và xem xét kỹ các ví dụ đưa ra trong bài viết, tuy vậy vẫn có thể không tránh khỏi các sai sót, rất mong nhận được sự đóng góp ý kiến của các bạn độc giả. Mọi góp ý, thắc mắc xin gửi về địa chỉ email: tuannhtn@yahoo.com.

                                                                                               

Hải Phòng, ngày 16, tháng 02, năm 2007
    

Nguyễn Hữu Tuân

Bài tập 1 – Mảng một chiều

Nhập vào N sinh viên (tên, điểm thi Toán, Lý, Hóa), in ra danh sách vừa nhập. Nhập vào 2 số thực x < y, hãy in ra tên và điểm các môn của các sinh viên có điểm trung bình nằm trong khoảng (x, y).