Đồ á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;
}

Đồ án NMCNTT1: Bài 2

ĐỒ Á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 2: Xem công thức tính sau đây (đề thi tuyển sinh cao học ngành KHMT, năm 2011):

  Aver = Σ(a_i – Max)² + Σ(a_i – Min)² + ⁿ/₂(Max – Min)²

Trong đó Max, Min lần lượt là giá trị lớn nhất, nhỏ nhất của n số thực (được nhập vào từ thiết bị nhập chuẩn) a₀, a₁, …, a_n-1.

Chỉ dùng duy nhất 1 vòng lặp (for hoặc while), đề xuất cách thức để nhập n số thực như trên và tính giá trị của biểu thức Aver, xuất kết quả tính ra thiết bị xuất chuẩn. Viết chương trình để minh họa đề xuất đó.

Lưu ý: Phần này sinh viên chưa học về mảng, như vậy vấn đề chính của bài toán này là không thể dùng mảng để lưu giá trị của n số thực nói trên. Như vậy phải đề xuất một giải pháp “thông minh” để nhập và tính toán mà không đưa trước các số thực này vào mảng.

Phân tích : Thông thường bái toán xử lý tính toán trên dãy số nhập vào, các giá trị nhập vào sẽ được lưu trữ trong một mảng, sau đó tùy vào yêu cầu tính toán ta sẽ duyệt các phần tử của mảng để làm tính.   Nhưng ở bài toán trên yêu cầu của đề là không dùng mảng, vì vậy ta phải tìm một giải pháp để tính trực tiếp tổng ngay trong quá trình nhập liệu.
 Ta phân tích lại phép tính như sau:
 Aver = Σ(a_i – Max)² + Σ(a_i – Min)² + ⁿ/₂(Max – Min)²
         =2Σa_i² – 2(Max + Min)Σa_i + n(Max² + Min²) + ⁿ/₂(Max – Min)²
Sau khi phân tích lại Aver ta nhận thấy bài toán trở thành hai bài toán đơn giản hơn
  - Tính 2Σa_i² và Σa_i các tổng này có thể tính toán trực tiếp ngay sau quá trình nhập liệu
  - Tính  ⁿ/₂(Max – Min)² và (Max² + Min²) bằng thuật toán ta sẽ tìm được Min, Max sau khi quá trình nhập liệu kết thúc.

Sau đây là code bài toán:

  
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;

void main()
{
 int i =0;// so luong so hang nhap vao
 double  Max= -numeric_limits<double>::min();
 double Min = numeric_limits<double>::max();
 double a;
 double S1 = 0; // s1 = a1^2 + a2^2 + .... + an^2
 double S2 =0; // s2 = a1 + a2 + a3 + a4... + an;
 double aver;
 
 while((cout <<"Nhap so a" << i << " = ")&&(cin >> a))
 {
  S2 +=  a;
  S1 +=  a*a;
  if(Max < a) Max = a;
  if(Min > a) Min = a;

  i++;
 }

 aver = 2 * S1 - 2 * (Max + Min) * S2 + i * (Max * Max + Min * Min) + (double)i/2 * (Max - Min) * (Max - Min);
 cout << "Gia tri Aver tinh duoc la " << aver;
 system("pause");
}
    

Đồ án NMCNTT1: Bài 1

Bài 1: Cho số tự nhiên A. Hãy Tìm số tự nhiên N nhỏ nhất sao cho N lũy Thừa N (hân N cho chính nó N lần) chia hết cho A.  Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤  10⁹

Ví dụ:

Số nhập vào là A	Số xuất ra là N
8	4
13	13

Nhận xét: Bài toán đòi hỏi phải tìm số nguyên nhỏ nhất dạng N^N chia hết cho số nguyên A được nhập vào từ bàn phím. Dễ thấy nếu N = A thì hiển nhiên A^A  chia hết cho A vì vậy ta luôn có N ≤ A. Trong trường hợp  A nhỏ bài toán có thể dễ dàn giải quyết bằng cách duyệt từ 0 tới A, tính  N^N và kiểm tra điều kiện chia hết cho A.
Nhưng vấn đề của bài toán này là khi N lớn (xấp xỉ 1 tỉ) thì N^N Có giá trị rất lớn mà không có một kiểu dữ liệu căn bản nào có thể chứa được. Vì vậy ở đây ta sẽ đi tìm một giải pháp khác mà không phải tính toán số cực lớn N^N
 Dễ thấy A luôn có thể phân tích thành tích lũy thừa các số nguyên tố   A = p₁^x1 p₂^x2 … p_k^xk  Do đó điều kiện cần để N^N chia hết cho A là N chia hết cho tích T =p₁p₂ … p_k (Ta có thể chứng minh điều này đễ dàn bằng phản chứng). Ta đăt N = T * i  (i ≤ N)  Khi đó N^N = (T*i)^T*i  = T^T*i * i^T*i  (với T = P₁P₂....P_k)
Ta tìm điều kiện đủ để NN chia hết cho A:
    Gọi Xmax = MAX{x1, x2.....xn} khi đó nếu N= T*i ≥ Xmax lúc đó  T^T*i sẽ chia hết cho A vì vậy N^N chia hết cho A. Vì T, Xmax luôn là hằng số với mỗi giá trị nhập vào của A ta sẽ có i ≥ Xmax \ T bài toán trở thành tìm giá trị nhỏ nhất của i thỏa mãn i ≥ Xmax \ T.
Qua các bước phân tích ở trên, bài toán sẽ được giải thông qua các bước sau:

1. Phân tích A ra tích lũy thừa nguyên tố dạng A = p₁^x1 p₂^x2 … p_k^xk  Tính T = p1p2...pn và Xmax = Max{x1,x2, ...xn}
2. Tìm giá trị nhỏ nhất thỏa mãn i ≥ Xmax \ T
3. Xuất ra kết quả N = T * i

Sau đây là code bài toán

  
#include <iostream>
#include <conio.h>
using namespace std;

int PhanTichNguyenTo( int soNhap, int& Xmax);
bool isPrime(int num);
void NhapXuat();

void main()
{
 
 NhapXuat();
}

void NhapXuat()
{
 int Xmax = 0;
 int A ;
 int i;
 while((cout << endl<< "Nhap so A = ")&&cin >> A)
 {
  int temp = PhanTichNguyenTo(A,Xmax);
     i = ceil(Xmax/(float)temp);
     cout  << "So N nho nhat thoa man dieu kien tren la " << temp * i;
 }
}
/*Ham tra ve tich cac uoc nguyen to cua so nhap 
va so mu lon nhat cua tich nguyen to*/
int PhanTichNguyenTo( int soNhap, int& Xmax)
{
 int T=1;
 int maxExp = 0;

 if(isPrime(soNhap))
 {
  maxExp =1;
  T= soNhap;
 }
 else
  for(int i = 2; i <= sqrt(soNhap); i++)
  {
   int j = 0;
     if(isPrime(i) && (soNhap % i ==0))
     {
      T *= i;
      int temp = soNhap;
      int exp =0;
      while(temp % i ==0)
      {
       temp = temp / i;
       exp++;
      }
   
      if(maxExp < exp)  maxExp = exp;
     }
  }
 
 Xmax = maxExp;
 return T;
}


 bool isPrime(int num)
  {
  bool result = true;
  if(num == 0|| num == 1)
    result = false;
  else
  {
    num = abs(num);

    for(int i = 2; i <= sqrt(num); i++)
    if(num % i == 0)
   result = false;
  }

  return result;
 }