Bài tập 3

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:

Khi nói đến tổng các chữ số của 1 số ta liên tưởng ngay đến tính chất chia hết cho 3 và chia hết cho 9.

Nhắc lại kiến thức cũ:”Một số chia hết cho 9(hay 3) thì có tổng các chữ số chia hết cho (hay 3).

Giá trị của hàm F(x) chỉ nằm trong khoảng từ 1 đến 9.Nếu làm theo định nghĩa thì số lần lặp sẽ cực kì lớn chưa kể với n! (1<=n<=500) nên cần phải sử dụng một số tính chất để làm đơn giản bài toán.

Trở lại với tính chất trên, ta thấy ngay n! với n>=6 luôn chia hết cho 9 và S(n) cũng chia hết cho 9.Dễ dàng chứng minh bằng qui nạp ta có ngay số cuối cùng của dãy số trên là số từ 1 đến 9 và chia hết cho 9.

Suy ra với n>= 6 , F(n!)=9.

Ở đây ta không dùng tính chất chia 3 vì đơn giản trong khoảng 1 đến 9 có 3 số chia hết cho 3.

Với các giá trị n thuộc từ 1 đến 6 ta có thể vét cạn các giá trị này.

n	1	2	3	4	5
F(n)	1	2	6	6	3

Mã nguồn:

#include <stdio.h> int F(int a); int F(int a) {        int result;        switch(a){               case 1:result=1;break;               case 2:result=2;break;               case 3:result=6;break;               case 4:result=6;break;               case 5:result=3;break;               default:result=9;        }        return result; }