Dùng tính chất chia hết để giải quyết bài toán

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.

Giải:

Đặt vấn đề:

- Để xử lí bài toán này thông thường ta sẽ tính n! để tính F(x).

Vấn đề: Nếu n là một số nhỏ thì ta có thể lưu trữ được giá trị của n! nhưng ở đây 

$1 \le n \le 500$, giả sử với $n = 500$, ta có $500!$ là một con số quá lớn vượt xa giới hạn lưu trữ của các kiểu số trong ngôn ngữ lập trình C/C++.
- Để giải quyết vấn đề này một số bạn sẽ dùng mảng để xử lí số lớn. Nhưng ở vị trí là người chưa biết về mảng mình sẽ dùng cách khác để giải quyết bài toán này.

Cách giải quyết bài toán:

- Ta thử xét một số trường hợp của n.
$\begin{array}{l} F(3!) = F(6) = 6\\ F(5!) = F(S(120)) = F(3) = 3\\ F(6!) = F(S(720)) = F(9) = 9\\ F(7!) = F(S(5040)) = F(9) = 9\\ F(11!) = F(S({\rm{39916800}})) = F(S(36)) = F(9) = 9 \end{array} $
….
- Nhận xét: Dễ thấy với $n \ge 6$ ta có $n!$  luôn là một số chia hết cho  9. Chứng minh:
Giả thiết: $n \geqslant 6 \Rightarrow n! = 9k \Leftrightarrow n \vdots 9\;(n,k \in \mathbb{N})\;(1)$
· Ta có:  $n = 6 \Rightarrow n! = 6! = 720 \vdots 9$ $ \Rightarrow (1)$ đúng
· Giả sử với $n = l \geqslant 6$ thì $(1)$ đúng nghĩa là  $n! = l! = 9k{\kern 1pt} (l,k \in \mathbb{N})$
· Ta đi chứng minh $(1)$ đúng với $n=l+1$
· Thật vậy, ta có $(l + 1)! = l!(l + 1) = 9k(l + 1) \vdots 9$ $ \Rightarrow (1)$ đúng
- Mặt khác tổng các chữ số của một số chia hết cho 9 thì chia hết cho 9 do đó ta kết luận:
$F(n!) = F(S(9k)) = F(S(9k')) = ... = F(9) = 9\;\forall n \geqslant 6,n \in \mathbb{N}$
- Như vậy để giải quyết bài toán này ta chia làm 2 trường hợp là:
· $n < 6$
· $n \geqslant 6$

Thuật toán:

-  Xậy dựng hàm tính giai thừa và tổng các chữ số của một số.
- Dùng hàm if để xét hai trường hợp của $n$

· $n \geqslant 6 \Rightarrow F(n!) = 9$
· $n < 6$ thì tính $n!$ và xét $n! \leqslant 9 \vee n! > 9$
     + $n! \leqslant 9 \Rightarrow F(n!) = 9$
     + $n! > 9 \Rightarrow F(n!) = F(S(n!)) = S(n!)$

- Xuất kết quả ra màn hình.

Source code:

#include <stdio.h>

#include <conio.h>

int giaithua(long n)

{

       int gthua;

       gthua = 1;

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

             gthua=gthua*i;

       return gthua;

}

int tongchuso(long n)

{

       int S;

       S = 0;

       while (n != 0)

       {

             S = S + n%10;

             n = n/10;

       }

       return S;

}

void main()

{

       long n, kqua;

       printf("Nhap vao n: ");

       scanf("%ld", &n);

       if (n < 6)

       {

             long gthua;

             gthua = giaithua(n);

             if (gthua <= 9)

                    kqua = gthua;

             else

                    kqua = tongchuso(gthua);

       }

       else

             kqua = 9;

       printf("Gia tri cua F(%ld!) la: %ld\n", n, kqua);

       getch();

}