VẤN ĐỀ Ở ĐÂY LÀ GÌ (bài 3 - đề án)

Lời nói đầu: có những vấn đề nhìn vào rất phức tạp và hoàn toàn không thể tìm ra một hướng đi phù hợp nhưng khi bạn chịu khó đầu tư vào mặt “chất xám” cho vấn đề ấy bạn sẽ tìm ra những nhận xét dễ đến ngỡ ngàng. Trong lập trình cũng vậy, người lập trình càng đầu tư cho việc tối ưu hoá thuật toán cũng như tìm ra những “ bí quyết độc môn” cho bài toán ấy thì chương trình chạy càng nhanh và hiệu quả. Sau đây mình xin xét lại hàm f(x) mà trong bài đăng VÒNG LẶP WHILE TRONG C/C++ mình đã từng đề  cập đến chỉ là ở đâu bài toán sẽ phức tạp hơn nhiều lần.

Bài toán đặt ra:

                                   Tính F(x)

Cho hàm F(x), x ≥ 0 được định nghĩa như sau:

F(x) = x, nếu x ≤ 9

F(x) = F(S(x)), nếu x > 9

     Trong đó S(x): tổng các chữ số của x và x=n!   1≤   n  ≤ 500

Giải quyết vấn đề:

Như các bạn thấy ở đây x= n! nếu n nhỏ thì ta có thể dễ dàng tính n! bằng nhiều cách thế nhưng khi n=500 thì 500! Vượt xa tất cả cách kiểu lưu trữ chúng ta có trong ngôn ngữ C/C++ như vậy ở đây chúng ta có 2 cách lựa chọn:

-          Tạo ra một kiểu số mới với miền giá trị đủ sức chứa 500!

-          Suy nghĩ một giải thuật đặc biệt mà mọi người thường gọi là “mẹo”.

Nếu bạn là người mới bước chân vào việc lập trình cách 1 nghe có vẻ quá xa lạ và phức tạp và dường như ở đây cũng không cần thiết lắm. tại sao bạn không nghĩ đến cách 2 vì có lẽ đã là mẹo thì luôn gắn với 2 từ “kinh nghiệm” thế nhưng ở đây bạn hãy cùng mình tính thử vài giá trị f(x) xem sao:

f(2!)=f(2)=2;

f(4!)=f(24)=6;

….

F(6!)=f(720)=9;

F(7!)=f(5040)=9;

F(8!)=f(40320)=9;

….

F(x!)=9 với x>=6;

Vậy khi bạn thử nghiệm với những số nhỏ như trên bạn dự đoán được:                                                                                 F(x!)=9 với x>=6;

Để chắc chắn hơn bạn có thể thử tiếp với những n lớn hơn ( còn tính được) nhưng theo thông thường các bài toán như thế này thường luôn có 1 quy luật nên bạn có thể an tâm về kết quả này

Như trên ta chỉ cần chia ra 2 trường hợp:

-          TH1:  x≤5 tính f bình thường.                    TH2: x>=6 thì  f(x)=9 

Bài giải tham khảo:

#include

#include

long tongcso(int x)

{

            long kq;

            kq=0;

            while (x !=0)

                        {

                                    kq=kq+(x % 10);

                                    x=x/10;

                        }

            return kq;

}

void main()

{

            long k,n;

            printf(" nhap vao so n can tinh f(n!),n=");

            scanf("%ld",&n);

            k=1;

            if (n<6 o:p="o:p">

            {

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

                                    k=k*i;

                        while (k>9)

                                    {

                                                k=tongcso(k);

                                    }

            printf(" ket qua ham f(%ld!)= %ld ",n,k);

            }

            else

                        printf(" f(%ld !)= 9",n);

}