Hướng Dẫn Đề Thi Giải Thuật

Câu 1:
Đây là phần lý thuyết, các bạn cần ôn lý thuyết. Sau đây là hướng dẫn các dạng thường gặp ở câu này:

*Trình bày thuật toán:Tìm kiếm nhị phân, Tìm kiếm tuyến tính, Chọn trực tiếp ( Selectionsort), Đổi chỗ (InterchangeSort), Chèn trực tiếp (InsertionSort), Nổi bọt (BubleSort).
+ trình bày 2 phần: ý tưởng của thuật toán, thuật toán ( code hoàn chỉnh,hoặc mã giả,hoặc ngôn ngữ tự nhiên)
*Áp dụng sắp xếp dãy:
+Vẽ ra các bước trong quá trình sắp xếp. Để ngắn gọn chỉ vẽ ra các bước mà dãy có sự thay đổi, và nêu quá trình bước đó.
+Trong phần áp dụng có thêm 2 thuật toán sử dụng đó là Trộn trực tiếp (MegerSort), Sắp xếp nhanh (QuickSort).
*Tính số lần lặp ( hoán vị, so sánh) trong đoạn chương trình:
+các vòng lặp lồng vào nhau thì số lần lặp (hoán vị, so sánh) là tích của các vòng lặp
+các vòng lặp không lồng nhau thì số lần lặp (hoán vị, so sánh) là tổng của các vòng lặp
+nếu vòng lặp bằng ( vòng lặp chạy từ i=x tới i<=y (hoặc i>=y)):

Trích dẫn :

số lần lặp sẽ bằng (y+1) - x.
ví dụ: for(i=1;i<=n;i++)
số lần lặp là (n+1)-1=n

+nếu vòng lặp không bằng (chạy từ i=x tới i < y ( hoặc i>y)):

Trích dẫn :

số lần lặp bằng y-x
ví dụ: for(i=1;i < n; i++)
số lần lặp là n-1

*Độ phức tạp thuật toán:
+nếu vòng lặp lồng nhau thì độ phức tạp O sẽ bằng bậc cao nhất của đa thức.

Trích dẫn :

ví dụ: ta có tổng vòng lặp là n(n-1) thì độ phức tạp là O(n*n)

+nếu vòng lặp không lồng thì độ phức tạp sẽ lấy giá trị max giữa các vòng lặp rời.

Lưu ý: công thức tính vòng lặp, số lần so sánh, số lần hoán vị... như trên không chắc hoàn toàn đúng 100%. chỉ có tính hên xui. Không có trách nhiệm bảo hiểm.

Câu 2: Thiết kế thuật toán
trình bày 4 nội dung
+Input
+Output
+Ý tưởng giải quyết bài toán
+Thuật toán

Câu 3 viết hàm đệ quy. Ôn lại kiến thức đệ quy ở môn C, Cấu trúc dữ liệu và Pascal để nắm rõ.

Up link
http://adf.ly/2mrdv
http://adf.ly/2mreK

thanks kiu pác nhiều. Mấy cái đánh giá độ phức tạp thì nói chung là rất phức tạp.