bài 3 đề phức tạp nhưng cách làm đơn giải

Bài 3: 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.

Yêu cầu: Hãy viết chương trình tính F(n!), với 1 <= n <= 500.

  Đề cho hơi bị phức tạp đòi hỏi phải có thời gian suy nghĩ. Bài toán có 2 vấn đề cần giải quyết là F(x) và n!.

  Đầu tiên là n!. có thể thấy 500! rất lớn (khỏi tính cũng biết)không có một dữ liệu cơ sở nào lưu trữ nổi. Vậy dùng gì để lưu trữ hay có cách khác khỏi cần tính số quá lớn như bài 1. Theo tìm kiếm trên mạng và mấy người bạn thì kêu dùng mảng để lưu trữ mà mảng là gì chưa học thôi tìm cách khác vậy.

  Phương pháp của bài 1 là bỏ qua việc tính số lớn mà đi sâu vào tính chất chia hết để giải quyết bài toán. Vậy bài 3 có tương tự. Như đã nói ở trên  có 2 vấn đề quan trọng là F(x) và n!. Vậy ta phải tìm hiểu tính chất của n! làm sao mà không cần tính giá trị của nó vẫn tìm được. Nhưng dường như rất khó sẽ dễ đi vào lối mòn.

  Vậy phải tìm hiểu F(x) coi có cách không. Có thể thấy F(x) chỉ có thể nằm trong khoảng [1;9] vì lớn hơn 9 sẽ lấy tổng các chữ số nên khi còn 1 chữ số thì đó sẽ là giá trị F(x). Vậy không cần tính n! có thể biết được F(x) mà đề hỏi. Nếu chú ý đến bước tính tổng chữ số và dấu hiệu chia hết cho 3 và 9 là tổng các chữ số chia hết cho 3 và 9.  Vậy đối với 1 số nếu chia hết cho 3 và 9 sau khi lấy tổng chữ số thì số tổng đó sẽ chia hết cho 3 và 9. Với suy luận trên thì tổng chữ số cuối cùng tương ứng với 1 chữ số có thể 3 và 9. Vậy khi nào n! chia hết cho 3 và 9. Với 3 thì ta thấy n>=3 thì n! đều chia hết cho 3 vì đều có thừa số 3. Tượng tự với 9 ta có n>=6 thì đều chia hết  cho 9 vì 6!=3*2*4*5*3*2=9*... . Vậy với n>=6 thì F(x)=9 vì tổng các chữ số cuối cùng đã chia hết cho 9 mà 9 lại là số lớn nhất trong khoảng[1;9].

 Vậy ta có kết luận sau:

n>=6 thì F(x)=9

 Vậy ta đã làm đơn giản bài toán rất nhiều.

 Với n<6 thì chỉ còn các trường hợp:

- n=1 thì F(X)=1

- n=2 thì F(X)=2

- n=3 thì F(X)=6

- n=4 thì F(X)=6

- n=5 thì F(X)=3

 Từ cách suy luận trên ta có đoạn mã sau:

#include <iostream>

using namespace std;

void bai3 (unsigned int ia, unsigned int& fx)

{

     switch(ia)

     {

           case 1: fx=1; break;

           case 2: fx=2; break;

           case 3:case 4: fx=6; break;

           case 5: fx=3; break;

           default: fx=9;

     }

}

void main ()

{

     unsigned int in,fx;

     cout<<"nhap 1 so nguyen n voi n(1 <= n <= 500)"<<endl;

     cin>>in;

     bai3(in,fx);

     cout<<"ket qua F(x) = "<<fx<<endl;

     system("pause");

}