Đề tài 1
: Trình bày về giải thuật đệ quy và các phương pháp khử đệ quy
+ cấu trúc dữ liệu :
1-
định nghĩa
:
Ta nãi mét ®èi tîng lµ ®Ö quy nÕu nã bao gåm chÝnh nã nh mét bé phËn hoÆc nã ®îc ®Þnh nghi· díi d¹ng cña chÝnh nã
. đệ quy là trong bản thân nó chứa một thành phần của chính nó với kích thước nhỏ hơn . Có hai loại đệ quy :
+ Đệ quy trực tiếp : là trong thân hàm chứa lời gọi đến nó
+ Đệ quy gián tiếp: trong thân hàm có lời gọi đến hàm khác và hàm đó có lời gọi đến chính hàm hiện tại
2-
biểu diễn dữ liệu :
- Cot[8]:mảng chứa chỉ số hàng i của quân hậu ở cột j.
- Hang[8]:có các phần tử bằng 0 là hàng còn tự do, nếu có phần tử bằng 1 thì hàng không còn tự do.- Cheoxuoi[i+j]:có các phần tử bằng 0 là đường chéo (i+j) còn tự do, nếu có phần tử bằng 1 thì hàng không còn tự do.-Cheonguoc[i-j]:có các phần tử bằng 0 biểu diễn đường chéo (i-j) còn tự do, nếu có phần tử bằng 1 thì hàng không còn tự do.
Ta biết :0<=i,j<8
=> -8 <= i-j <8
2 <= i+j <16
3-
các phép toán :
-
tư tưởng :
-
thủ tục :
procedure SEARCH(dict , word)
{
dict được coi là đầu mối để truy nhập được vào tự điểm đang xét , work chỉ từ cần tìm }
1 . if tự điểm chỉ còn một trang
then tìm từ work trong trang này .
else begin
2. Mở tự điểm vào trang “giữa ”
Xác định xem nửa nào của tử điển chứa từ work ;
If word nằm ở nửa trước của từ điển .
Then call SEARCH (dict 1 . word)
else call SEARCH (dict 2 . word)
end ;
{ dict 1 và dict 2 là đầu mối để truỳ nhập được vào nửa trước và nửa sau của tử điển }
3 . return
-
