Đồ án NMCNTT1: 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.

Phân tích: Đây là một bài toán khá đơn giản về mặt toán học. Nhưng xét về khía cạnh lập trình khó khăn chính là  phải tính giai thừa một số rất lớn. Thông thường nếu dùng các kiểu dữ liệu cơ bản khi tính giai thừa một số rất lớn chắc chắn sẽ  bị tràn số. 
   Một giải pháp khả thi là dùng mảng để lưu trữ, và giả lập tính toán các phép tính cộng, trừ, nhân, chia. Trong khuân khổ bài toán này ta sẽ 1 mảng một chiều để lưu trữ con số rất lớn.

Ta sẽ dùng một mảng 5000 phần tử mỗi phần tử lưu trữ một chữ số: như vậy giá trị tối đa mà mảng này lưu trữ sẽ là 10⁵⁰⁰⁰ >> 500!
Ta sẽ dùng mảng 1 chiều để tính toán giai thừa và lưu trữ kết quả.

  
void giaiThua(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    giaiThua(arr,n-1);
}

Code hoàn chỉnh:

  
#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
     if (!ctr && arr[i]) ctr = 1;
     if(ctr)
            std::cout<<arr[i];
    }
}


void giaiThua(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    giaiThua(arr,n-1);
}
int SX(int n)
{
 int result = 0;
 while(n != 0)
 {
  result += n % 10;
  n = n / 10;
 }

 return result;
}
int SX(int arr[],int n)
{
 int result =0;//Tong cac chu so cua n!

 giaiThua(arr,n);

  int ctr = 0;
    for(int i=0; i<max; i++){
     if (!ctr && arr[i])   ctr = 1;
     if(ctr)
           result += arr[i];
    }
 return result;
}

int FX(int n)
{
 int result;
 if(n <=9){
  result = n;
 }
 else
 {
        result = SX(n);
 }
 return result;
}
int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Nhap So";
    std::cin>>num;

     int result = FX(SX(SX(arr,num)));
     std::cout << std::endl << "F(" << num << "!) = " << result <<std::endl;

    delete[] arr;
 system("pause");
    return 0;
}