Vậy Tx = O(log2(n))
Người ta cũng chứng minh được Ttb = log2(n)
- Có một lưu ý đó là muốn sử dụng thuật toán tìm kiếm
nhị phân thì ta phải sử dụng dãy đã được sắp xếp trước,
vậy nên phải tính thêm thời gian sắp xếp vào với những
dãy khoá biến động, luôn thêm bớt. Vậy đây chính là
nhược điểm của phương pháp tìm kiếm nhị phân
8. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm kiếm. Mỗi nút trên cây có cấu trúc như sau:
P_L Trỏ tới cây con trái
KEY Chứa giá trị khoá
P_R Trỏ tới cây con phải
BST(T, x, P){
/*
Tìm giá trị x trên cây T, nếu thấy thì trỏ P vào,
nếu k tìm thấy thì tạo thêm nút rồi trỏ P vào
*/
P = T; Q = null;
while(P != null){
if(P->KEY = x){
return P;
}
Q = P;
if(x < P->KEY){
P = P->P_L;
}else{
P = P->P_R;
}
}
P = malloc();
P->KEY = x;
P->P_L = null;
P->P_R = null;
if(x < Q->KEY){
Q->P_L = P;
}else{
Q->P_R = P;
}
printf("Không tìm thấy, đã bổ sung!");
return P;
}
Câu 9 : Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật đệ qui quay lui tìm tất cả các cách đặt 8 quân hậu vào bàn cờ vua sao cho không quân nào ăn quân nào. Khi trình bày giải thuật bằng ngôn ngữ tựa C có mô tả cách tổ chức dữ liệu trong giải thuật
Xét bàn cờ vua có kích thước 8x8, ta cần đặt 8 quân hậu vào bàn cờ vua sao cho k quân nào ăn quân nào, 8 quân hậu k ăn nhau tức chúng nằm ở các hàng, các cột, các dường chéo khác nhau. Giả sử, ta đặt 8 con hậu vào 8 cột: con hậu j nằm ở cột j, hàng i, hai đường chéo là (i+j) và (i-j)
Quy tắc chọn hàng: để hàng I được chấp nhận thì hàng i và 2 đường chéo i+j và i-j được tự do hay là k có con hậu nào trên hàng đó.
Xét trường hợp tổng quát:Ta tìm cách dặt quân hậu j vào hàng i cột j bằng cách cho i chạy từ 1 đến 8 nếu tìm được 1 vị trí an toàn thì:
Đặt con hậu j vào hàng đấy. Vị trí I,j không an toàn nữa
Nếu là con hậu cuối cũng thì thu được 1 kết quả
Nếu không phải con hậu cuối cùng, ta đặt caccs con hậu còn lại ở các cột đến khi j=8 thì kết thúc
Sau khi tìm được vị trí của con hậu j ta lại đặt vị trí i,j trở thành an toàn để tìm các cách khác nhau
Quy ước:
x[j]=i: con hậu thứ j được đặt ở hành thứ i
a[j]=1: hàng i an toàn
b[i+j]=1: đường chéo i+j an toàn
c[i-j]=1: đường chéo i-j an toàn
10. Trình bày (bằng ngôn ngữ tựa C) giải thuật cài đặt hàm đệ qui có dung STACK cho bài toán tính n!. Minh hoạ diễn biến của STACK, trong quá trình thực hiện giải thuật ứng với n = 3, theo dạng:
Số mức | Các bước thực hiện | Nội dung của STACK
Chia sẻ với bạn bè của bạn: |
