Bài tập Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh
Bài tập Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Cấu trúc dữ liệu và giải thuật (IT003)
Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Thông tin:
Tác giả:
Thông tin :
Môn:
Cấu trúc dữ liệu và giải thuật (IT003)
Trường:
Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh
Tác giả:
Tài liệu liên quan:
Preview text:
Bài tập Cấu trúc Dữ liệu và Giải thuật – Buổi 1 1. Li near Search
- Ý tưởng: Cho một mảng arr[] gồm n phần tử, tìm kiếm giá trị x mong muốn trong
mảng đó bằng cách so sánh lần lượt từng phần tử trong mảng đó với x.
- T rình bày bằng ngôn ngữ tự nhiên:
1. Bắt đầu từ phần tử ngoài cùng bên trái (index = 0) của arr và lần lượt so sánh x
với từng phần tử của arr .
2. Nếu x khớp với 1 phần tử trong arr ,trả về giá trị 1.
3. Ngược lại, trả về giá trị 0. - Minh họa: Cho mảng sau 54 26 93 17 77 31 44 55 20 Tìm số 54: 54 26 93 17 77 31 44 55 20 0 1 2 3 4 5 6 7 8
Tìm thấy 54 tại vị trí 0, trả về giá trị 1. Tìm số 6: 54 26 93 17 77 31 44 55 20 0 1 2 3 4 5 6 7 8
i = 9, không tìm thấy giá trị cần tìm, trả về giá trị 0. Tìm số 20: 54 26 93 17 77 31 44 55 20 0 1 2 3 4 5 6 7 8
Tìm thấy 20 tại vị trí 8, trả về giá trị 1. 2. Bin ary Search.
- Ý tưởng: Cho một mảng arr[] gồm n phần tử, tìm kiếm giá trị x mong muốn bằng
cách tìm phần tử nằm giữa, nếu không thấy giá trị x, chia đôi mảng tại phần tử
giữa đó cho đến khi tìm được x.
- T rình bày bằng ngôn ngữ tự nhiên: Đầu tiên ta cần sắp xếp mảng theo chiều tăng
hoặc giảm. Bắt đầu tìm kiếm giá trị từ phần tử giữa.
1. Nếu phần tử giữa bằng giá trị cần tìm, trả về giá trị 1.
2. Nếu phần tử giữa nhỏ hơn giá trị cần tìm, loại bỏ nửa đầu tiên của mảng và xét tiếp.
3. Nếu phần tử giữa lớn hơn giá trị cần tìm, loại bỏ nửa sau của mảng và xét tiếp.
4. Nếu sau các lần thực hiện phía trên mà không tìm thấy giá trị cần tìm, trả về giá trị 0. - Minh họa: Cho mảng sau 54 26 93 17 77 31 44 55 20
T rước tiên ta cần sắp xếp lại mảng, dưới đây mảng được xếp theo chiều tăng dần. 17 20 26 31 44 54 55 77 93 Tìm số 54 0 1 2 3 4 5 6 7 8 17 20 26 31 44 54 55 77 93 F M L
Tìm thấy giá trị cần tìm, F = 5, M = 5, trả về giá trị 1. Tìm số 6 0 1 2 3 4 5 6 7 8 17 20 26 31 44 54 55 77 93 F M L
F= 0, L = -1, không tìm thấy giá trị cần tìm, trả về giá trị 0. Tìm số 20. 0 1 2 3 4 5 6 7 8 17 20 26 31 44 54 55 77 93 F M L
F = 0, L = 1, tìm thấy giá trị cần tìm, trả về giá trị 1.