Đề tài 01: BÀI TOÁN NHÂN SỐ NGUYÊN LỚN BẰNG KỸ THUẬT
CHIA ĐỂ TRỊKỹ thuật chia để trị là một kỹ thuật được sử dụng tương đối rộng rãi trong thiết kế giải thuật.
Đề tài nhằm tìm hiểu về kỹ thuật chia để trị và minh họa bằng bài toán nhân 02 số nguyên
lớn.
Gợi ý:
Giả sử X, Y là 2 số nguyên lớn có độ dài là n chữ số. Ta có thể viết:
Kỹ thuật chia để trị được áp dụng ở đây dẫn đến độ phức tạp của giải thuật nhân là
O(n2).
XY được viết lại:
X.Y=A.C.10n + [(A-B).(D-C)+A.C+B.D].10n/2 + B.D
Độ phức tạp của giải thuật cải tiến: O(nlog3).
Yêu cầu: Cài đặt giải thuật nhân 02 số nguyên lớn bằng kỹ thuật chia để trị với độ phức tạp
của giải thuật nhân là O(nlog3).
Đề tài 05: CÀI ĐẶT CÂY TÌM KIẾM NHỊ PHÂN BẰNG MẢNG
Có nhiều cách thức để cài đặt cây tìm kiếm nhị phân. Một trong những cách là cài đặt bằng
mảng.
Thí dụ:
Yêu cầu:
- Cài đặt cây tìm kiếm nhị phân cài đặt bằng mảng theo mô tả ở trên.
- Cài đặt các phép toán trên cây tìm kiếm nhị phân:
o Tìm kiếm một khóa trên cây
o Thêm một khóa vào cây.
o Xóa một khóa khỏi cây.
o Các phép duyệt cây: tiền tự, trung tự, hậu tự, mức.
o Tính độ sâu 1 nút.
o Tính chiều cao của cây
o Tìm khóa của nút cha của 1 nút
o Tìm khóa của nút anh em ruột phải của một nút.
--> Các bác nào có làm các đề tài này rồi xin post len để giúp đở nhe!
Chúc các bác học tốt!