Tinh Fx

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 giải

I. Phân tích yêu cầu
   - Input: n
   - Output: F(n!)

II. Đi tìm lời giải
   Theo đề bài ta có: x = n!. Để tính được F(x), trước hết phải tính được x, tức là tính được n!.
Sau đó xét nếu x > 9 thì cho x = tổng các chữ số của x, cho đến khi x <= 9 thì xuất ra kết quả.

   Nhưng vấn đề mắc phải ở đây là làm sao tính được n! với 1 <= n <= 500, vì 500! có tới 1135 chữ số, trong khi số lớn nhất của kiểu double cũng chỉ đạt tới 309 con số thôi. Vậy chúng ta không thể dùng các kiểu giá trị để lưu kết quả giai thừa được. Thế thì dùng cái gì bây giờ? Câu trả lời đó chính là mảng. Mảng có thể dài như mình mong muốn, khi lưu chúng ta sẽ lưu mỗi chữ số cho một phần tử của mảng. 

   Ví dụ dùng mảng a tính 5!, thì ta sẽ làm như sau, ban đầu cho phần tử đầu tiên của mảng là 1.
Tính 1!: a[1] = 1
Tính 2!: Lấy 1 * 2, so sánh với 9, thấy nhỏ hơn, vậy a[1] = 2
Tính 3!: Lấy 2 * 3, so sánh với 9, thấy nhỏ hơn vậy a[1] = 6
Tính 4!: Lấy 6 * 4, so sanh với 9, thấy lớn hơn vậy a[1] = 4(24 mod 10), a[2] = 2(24 div 10)
Tính 5!: Tương tự, ta có a[1] = 0, a[2] = 2, a[3] = 1
Sau khi tính xong, ta in mảng a theo chiều ngược sẽ được kết quả. Nhưng ở đây ta cần tổng các chữ số của giai thừa nên chạy chiều nào cũng được.

   Từ đó ta rút ra qui tắc sau:1. Khởi đầu mảng là 1, i = 1, j = 1(chỉ số mảng), rem = 0(phần nhớ)

2. Chạy i từ 2 tới n:
    - Lấy các phần tử của mảng a nhân với i
      + Gọi biến kq = a[j] * i + rem(phần dư)
      + Nếu kq <= 9 , thì a[j] = kq và rem = 0(vì nhỏ hơn 9, dĩ nhiên không còn nhớ nữa)
      + Nếu kq > 9, thì a[j] = kq mod 10 và rem = kq div 10
   - Sau khi nhân hết các phần tử của mảng rồi, thì ta xét rem:
     + Nếu rem > 0, thì mỗi phần tử tiếp theo của mảng sẽ nhận một chữ số của rem(phần nhớ)

3. Cuối cùng là chạy từ đầu tới cuối cộng các phần tử mảng lại, ta sẽ có được tổng các chữ số của giai thừa.

III. Source

1. Khai báo

  2. Hàm Main

  3. Hàm nhập n

  4. Hàm tính giai thừa

  4. Hàm tính tổng số giai thừa

  5. Tổng Hợp Code

#include <stdio.h>

#include <vector>    // khai bao thu vien vector

using namespace std; // su dung thu vien std trong c++

// prototype

void nhapN(int &n);  // ham nhap n

void tinhGiaiThua(int n, vector<int> &Fac);     // ham tinh n!, luu vao mang vector

int tongChuSo(vector<int> Fac);   // tong cac chu so cua n!

void main()

{

       int n;

       vector<int> Fac;     // khai bao mang vector co ten la Fac(Factorial: giai thua)

       nhapN(n);

       tinhGiaiThua(n, Fac);

       printf("\nF(%d!) = %d\n\n", n, tongChuSo(Fac));

}

// definition

void nhapN(int &n)

{

       do

       {

              printf("\nInput n: ");

              scanf("%d", &n);

       }

       while (n < 1 || n > 500);

}

void tinhGiaiThua(int n, vector<int> &Fac)

{

       if (n < 2)    // voi n = 0, n = 1, ta cho n! = 1 nen

              Fac.push_back(1);// chen gia tri 1 vao vector, luc nay vector co do dai la 1

       else // n >= 2

       {

              Fac.push_back(1);// ban dau chen 1 vao mang, coi nhu day la 1!

              for (int count = 2; count <= n; count++) // bien count la bac giai thua

              {

                     int total = 0;// tong(so truoc * bac giai thua) va (phan du)

                     int rem = 0;  // remainder: phan du

                     int i = 0;           // bien chay

                     while (i < Fac.size())

                     {

                           // calculate total

                           total = Fac[i] * count + rem;

                          

                           if (total <= 9)// neu tong < 9:thi lưu vào mảng

                           {

                                  Fac[i] = total;

                                  rem = 0;

                                  i++;

                           }

                           else //neu tong > 9: lấy tổng chia du cho 10 roi luu vào mảng

                           {      // con phan (chia nguyen cho 10) se la phan du.

                                  // Vd: 12 --> phan tu thu i se la 2, phan du se la 1.

                                  Fac[i] = total % 10;

                                  rem = total / 10;

                                  i++;

                           }

                     }

                     while (rem > 0) // sau khi nhan xong het mang, neu van con phan du

                     { //tiep tuc cho moi phan tu nhan mot chu so cho den het thi thoi.

                           Fac.push_back(rem % 10);

                           rem = rem / 10;

                     }

              }      // end for

       }// end else

}// end void

int tongChuSo(vector<int> Fac)

{

       int sum = 0;

       // cho bien i chay tu dau den cuoi mang, cong don vao bien sum

       for (int i = 0; i < Fac.size(); i++)

              sum = sum + Fac[i];

      

       // neu bien sum > 9 thi sum = tong cac chu so cua sum

       while (sum > 9)

       {

              int temSum = sum; // su dung bien tam de luu giai tri sum hien tai

              sum = 0;      // cho sum tro ve 0, de chuan bi nhan gia tri moi

              while (temSum > 0)

              {

                     sum = sum + temSum % 10;   // sum = sum + hang don vi cua temSum

                     temSum = temSum / 10;      // giam temSum di mot so hang don vi

              }

       }

       return sum;

}

Chúc các bạn thành công!!!