Xét công thức truy toán để tính số tổ hợp chập k của n như sau
Bài tập trong giáo trình phân tích và thiết kế thuật toán
Bài 5: Xét công thức truy toán để tính số tổ hợp chập k của n như sau:
C n ^ k = 1 nếu k=0 hoặc k = n \\ C n-1 ^ k-1 +C n-1 ^ k nếu 0<k<n
a) Viết một hàm đệ qui để tính số tổ hợp chập k của n.
b) Tính thời gian thực hiện của giải thuật nói trên.
Bài 6: Xây dựng hàm đệ qui để sắp xếp tăng dần màng một chiều, sau đó xác định độ phức tạp của hàm đã xây dựng.
Bài 7: : Cho một màng một chiều gồm n số nguyên được sắp thứ tự tăng dần. Viết hàm tìm một số nguyên trong mảng đó theo phương pháp tìm kiếm nhị phân, nếu tìm thấy thì trả về TRUE (1), ngược lại trả về FALSE (0).
dụng hai kỹ thuật là vòng lặp và đệ qui. Với mỗi kỹ thuật hãy viết một hàm tìm và tính thời gian thực hiện của hàm đó.
Bài 5: Xét công thức truy toán để tính số tổ hợp chập k của n như sau:
C n ^ k = 1 nếu k=0 hoặc k = n \\ C n-1 ^ k-1 +C n-1 ^ k nếu 0<k<n
a) Viết một hàm đệ qui để tính số tổ hợp chập k của n.
b) Tính thời gian thực hiện của giải thuật nói trên.
Bài 6: Xây dựng hàm đệ qui để sắp xếp tăng dần màng một chiều, sau đó xác định độ phức tạp của hàm đã xây dựng.
Bài 7: : Cho một màng một chiều gồm n số nguyên được sắp thứ tự tăng dần. Viết hàm tìm một số nguyên trong mảng đó theo phương pháp tìm kiếm nhị phân, nếu tìm thấy thì trả về TRUE (1), ngược lại trả về FALSE (0).
dụng hai kỹ thuật là vòng lặp và đệ qui. Với mỗi kỹ thuật hãy viết một hàm tìm và tính thời gian thực hiện của hàm đó.