Computer Science ++

January 20, 2013

Bài tập NMCNTT1 - LaTeX

Đây là bài tập LaTeX của mình. Bạn nào cần tham khảo thì hãy vào link này.

November 28, 2012

NMCNTT1 - Các bài tập đã làm

Mình đã up những bài tập NMCNTT1 đã làm lên dropbox. Bạn nào cần xem thì hãy vào link:
BT NMCNTT1 - Duy Bao

November 25, 2012

ĐỒ Á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;
}

ĐỒ ÁN MÔN HỌC NM CNTT1 - 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.

Bài làm

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

o Rõ ràng điểm khó nhất bài này là tìm cách giải mà chỉ dùng 1 vòng lặp. Bởi vì với công thức đã cho, ta hoàn toàn có thể giải bằng 2 vòng lặp bằng cách cho vòng lặp thứ nhất nhập số vào và đồng thời tìm Max, Min của dãy số, còn vòng lặp thứ 2 thì tính toán theo công thức.

o Do đề bài có nói rõ là không dùng mảng, vậy ta sẽ phải dùng 1 vòng lặp vừa nhập, vừa tính toán rồi sau đó in ra kết quả.

- Theo công thức đề bài, ta phải biết sẵn Max và Min của dãy số ở mỗi lần lặp. Vậy không thể tính thẳng theo công thức này được mà phải biến đổi nó. Cách biến đổi đơn giản nhất chính là bung hằng đẳng thức ra:

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

= Σ(a_i² – 2a_iMax + Max²) + Σ(a_i² – 2a_iMin + Min²) + ⁿ/₂(Max – Min)²

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

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

o Đến đây, ta thấy rằng mỗi số hạng đều có thể tính độc lập với nhau:

§ 2Σa_i²: dùng vòng for tính tổng a_i² rồi nhân kết quả cho 2.

§ – 2(Max + Min)Σa_i: dùng vòng for tính tổng a_i và lưu Max, Min của dãy số rồi nhân với -2(Max + Min).

§ n(Max² + Min²): dùng 1 vòng for lưu Max, Min của dãy số, tính Max + Min rồi nhân với n.

§ ⁿ/₂(Max – Min)²: dùng 1 vòng for lưu Max, Min của dãy số, tính (Max – Min)² rồi nhân với ⁿ/₂.

- Nếu làm như trên ta sẽ cần ít nhất 4 vòng lặp, thế nhưng nếu nhìn kĩ ta sẽ thấy trong một vòng lặp hoàn toàn có thể dùng nhiều biến để lưu trữ và tính toán tất cả các giá trị cần thiết cho cả 4 số hạng trên. Sau đó, khi thoát khỏi vòng lặp, ta sẽ dùng những giá trị đã tìm được để tính ra kết quả như công thức.

Mã nguồn

#include <iostream>
#include <iomanip>
using namespace std;
void main()
{
 int iN;
 double dA, dMin, dMax, dTong = 0, dTongMu2 = 0, dSoHang1, dSoHang2, dSoHang3, dSoHang4, dKetQua;

 cout << "Nhap so phan tu N: ";
 cin >> iN;
 for (int i = 0; i < iN; i++)
 {
  cout << "Nhap phan tu thu " << i + 1 << " :";
  cin >> dA;
  if (i == 0)
  {
   dMin = dA;
   dMax = dA;
  }
  if (dMin > dA) 
   dMin = dA;
  if (dMax < dA)
   dMax = dA;
  dTong += dA;
  dTongMu2 += dA * dA;
 }

 dSoHang1 = 2 * dTongMu2;
 dSoHang2 = -2 * dTong * (dMax + dMin);
 dSoHang3 = iN * (dMax * dMax + dMin * dMin);
 dSoHang4 = 0.5 * iN * (dMax - dMin) * (dMax - dMin);
 dKetQua = dSoHang1 + dSoHang2 + dSoHang3 + dSoHang4;

 cout << "Ket qua bai toan la: " << fixed << setprecision(9) << dKetQua << endl;
}

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

ĐỒ Á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 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 (nhâ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

Bài làm

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

o A^A luôn chia hết cho A nên chắc chắn kết quả N ≤ A. Vậy ta có thể lặp tìm N từ 1 đến A, gặp số N nào thoả N^N chia hết A thì ta dừng. Nhưng cách làm này gặp 2 vấn đề: N^Ntăng rất nhanh và nếu lặp từ 1 đến 10⁹ thì chương trình sẽ chạy khá chậm.

o Do chỉ cần xét N^N có chia hết cho A hay không mà không cần quan tâm kết quả này nên ta có thể phân tích N và A ra thừa số nguyên tố để kiểm tra tính chia hết. Như vậy sẽ không lo N^N tràn số. Nhưng chương trình vẫn phải duyệt từ 1 đến A nên vẫn chậm.

- Đầu tiên, ta sẽ phân tích A và N ra tích các thừa số nguyên tố để dễ xét tính chia hết:

A = p₁^x1 p₂^x2 … p_k^xk

N = q₁^y1 q₂^y2 … q_m^xm

=> N^N = q₁^y1*N q₂^y2*N … q_m^xm*N

o Trong cách phân tích này, ta thấy rằng mọi thừa số nguyên tố p_icủa A đều phải chứa trong N. Bởi vì nếu không có p_i thì tất cả các số nguyên tố q_j đều không chia hết cho p_i => N^N không chia hết cho A. Vậy nếu đặt r = p₁p₂…p_k, ta có N ≥ r. Ngoài ra, để N^N chia hết cho A thì mọi số mũ của p_i trong N^Nphải lớn hơn hoặc bằng số mũ của p_i trong A. (*)

- Vậy N sẽ có dạng: r*t = p₁p₂… p_k* t.
o Trong trường hợp r ≥ x_i ∀i thì ta chỉ cần đặt N = r thì khi đó N^N = p₁^rp₂^r… p_k^r => mọi số mũ của p_i trong N^Nđều lớn hơn hoặc bằng số mũ của p_i trong A => N^N chia hết cho A theo (*).

o Trong trường hợp ngược lại (tức ∃i : r < x_i), kết quả sẽ là N=r*t với t>1. Lúc này, ta sẽ phải xét t trong khoảng [2,max(x_i)] (chỉ xét đến max(x_i) là vì khi t=max(x_i) thì z_i*t ≥ x_i ∀i => N^N đã chia hết cho A, vậy không cần tìm t lớn hơn max(x_i) nữa). Khi đó, với mỗi ước p_i của A, ta xét số mũ của p_i trong N^N = p₁^r*tp₂^r*t… p_k^r*t t^r*tcó lớn hơn số mũ của p_i trong A không. Nếu mọi số mũ p_i trong N^N đều lớn hơn hoặc bằng số mũ của p_i trong A thì N^N sẽ chia hết cho A (theo (*)) => N=r*t chính là giá trị nhỏ nhất để N^N chia hết cho A.

Mã nguồn

#include <iostream>
#include <cmath>
using namespace std;

int demMu(int& iSo, int iUoc)
{
 int iDem = 0;
 while (iSo % iUoc == 0)
 {
  iSo /= iUoc;
  iDem++;
 }
 return iDem;
}

void main()
{
 int iA, iMaxMu = 1, iR = 1;
 cout << "Nhap gia tri cua A: ";
 cin >> iA;
 double dCanA = sqrt(iA * 1.0);
 int iABanDau = iA;

 for (int i = 2; i <= dCanA; i++)
  if (iA % i == 0)
  {
   int iMu = demMu(iA, i); 
   iR *= i;
   if (iMu > iMaxMu)
    iMaxMu = iMu;
  }

 if (iA > 1)
  iR *= iA;

 if (iMaxMu > iR)
  for (int k = 2; k <= iMaxMu; k++)
  {
   bool bEnd = true;
   iA = iABanDau;
   for (int i = 2; i <= dCanA; i++)
    if (iA % i == 0)
    {
     int iC = iR * k;
     int iMuA = demMu(iA, i);
     int iMuC = demMu(iC, i); 

     if (iMuC * iR * k < iMuA)
      bEnd = false;
    }
   if (bEnd) 
   {
    iR *= k;
    break;
   }
  }

 cout << "N nho nhat thoa N^N chia het cho A la: ";
 cout << iR << endl;
}

November 15, 2012

Blog Testing

Testing...