Đề thi
NHẬP MÔN PHÂN TÍCH THUẬT TOÁN
(120 phút, được phép dùng tài liệu) Câu 1
Với n nguyên dương, ta đặt: 1 1 1 H = 1+ + + ...+ S = H + H + ... + H n và . 2 3 n n 1 2 n
a) Chứng minh: H = n +1 H − nH −1 n ( ) n+1 n
b) Tìm công thức tính Sn theo Hn.
c) Ước lượng độ lớn của Sn (so với n) theo kí hiệu Θ. Câu 2
Giả sử n là một số nguyên dương. Xem thuật toán mã giả trong bảng sau đây. I=1, result=0, h=1
While I<=n do J=1, t =1
a) Phân đoạn thuật toán thành các thành
While J<=h do
phần để có thể ước lượng số lượng các t = x * I * J
phép toán được thực hiện. J = J + 1
b) Hãy tính theo n số phép gán và số Endw
phép so sánh được thực hiện trong I = I + 1 thuật toán.
h = h + 1/I {phép chia số thực} result = result + x
c) Xác định độ phức tạp của thuật toán. Endw Câu 3
Giả sử n là một số nguyên dương. Xem hàm được viết trong bảng sau đây.
float Si(float x, long n) {
long i=1; float z=0; while(i<=n){
a) Phân đoạn hàm này thành các thành phần để có
long j=1; float t=1;
thể ước lượng số lượng các phép toán được thực
while(j-i<=i*i*i){ hiện. if(j>=i*i)
b) Ước lượng theo n số phép gán được thực hiện. t = t/2; t = t*x; j = j + 1; } z = z + i*t; i = 2*i; } return z; } (Đề thi gồm 1 trang)
Document Outline

• Câu 1
• Câu 2
• a) Phân đoạn thuật toán thành các thành phần để có thể ước lượng số lượng các phép toán được thực hiện.
• b) Hãy tính theo n số phép gán và số phép so sánh được thực hiện trong thuật toán.
• c) Xác định độ phức tạp của thuật toán.
  • Câu 3