ĐỒ ÁN MÔN HỌC NM CNTT1 - BÀI 3

ĐỒ ÁN MÔN HỌC NM CNTT1

LỚP CỬ NHÂN TÀI NĂNG KHÓA 2012

Giảng viên ra đề:

ThS. Trương Phước Hưng

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.

Bài làm

-         Nhận xét ban đầu:

o   Ta cần phải tìm F(500!). 500! là một số hết sức lớn, nằm ngoài khả năng lưu trữ của các kiểu dữ liệu. Vậy ta cần tìm cách tính hàm F mà không cần phải tính n!.

o   Từ công thức đề bài, không khó để thấy kết quả luôn là số nguyên không âm bé hơn 10.

-         Trước hết, ta khoan xét đến F(n!) mà hãy xét F(x) với x nguyên dương. Lúc này, hàm F(x) chính là giá trị nhận được khi ta lặp đi lặp lại quá trình cộng các chữ số của x, với lần lặp sau dùng kết quả đã có của lần lặp trước làm dữ liệu đầu vào. Đến đây, ta có thể viết một vài giá trị đầu tiên của dãy F(x) để tìm kiếm quy luật: 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3 ,4 … Không quá khó để thấy qui luật của dãy số này:

o   F(x) = 9 với x chia hết cho 9.

o   F(x) = x % 9 với x không chia hết cho 9. (% là phép chia lấy phần dư).

-         Từ đây, ta có thể dễ dàng tính được F(x). Vậy còn F(n!) thì sao? Với n≥6, ta có n! chia hết cho 9, vậy thì F(n!) sẽ bằng 9. Còn với n<6 thì ta chỉ việc lặp và tính kết quả do khi đó n! hoàn toàn có thể lưu trữ được.

Mã nguồn

#include <iostream>
using namespace std;
void main()
{
 int iN, iFact = 1;
 cout << "Nhap n: ";
 cin >> iN;
 cout << "F(" << iN << "!) = ";

 if (iN > 6) 
  iN = 6;

 for (int i = 2; i <= iN; i++)
  iFact *= i;

 if (iN == 0)
  iFact = 0;

 cout << 1 + ((iFact - 1) % 9) << endl;
}