1) Trình bày giải thuật 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, bằng cách dùng thủ tục đệ qui quay lui.
Bài làm:
Procedure Dathau(j)
For i:=1 to 8 do
If a[i] and b[i+j] and c[i-j] then
Begin
x[j] := i;
a[i] := False; b[i+j] := False; c[i-j] := False;
If j < 8 then
Dathau(j+1);
Else
//In nghiệm
For k := 1 to 8 do
Write (x[k]);
//Cất hậu để tìm nghiệm tiếp theo
a[i] := True;
b[i+j] := True;
c[i-j] := True;
End;
Program Con_hau;
For i:=1 to 8 do a[i] := True;
For i:=2 to 16 do b[i+j] := True;
For i:= -7 to 7 do c[i-j] := True;
Dathau(1);
End.
2) Trình bày giải thuật đánh giá biểu thức hậu tố bằng cách dùng STACK. Minh họa diễn biến của quá trình đọc biểu thức và sự thay đổi trong STACK với biểu thức: 5 9 – 2 6 / + theo dạng:
Diễn biến đọc biểu thức Diễn biến STACK Thực hiện phép toán
9 – 2 6 / + 5
9
- 2 6 / + 5
2 6 / + - 4 5 – 9
…
Bài làm:
Procedure Danh_gia;
Repeat
<Đọc phần tử tiếp theo của biểu thức>
If <x là toán hạng> then
Push (S,T,x);
Else
Begin
X:= Pop(S,T);
Y:= Pop(S,T);
Z := Y x X ; //x đang lưu trữ toán tử
Push (S,T,Z) ;
End ;
Until // Gặp dấu kết thúc biểu thức
Write (Pop (S,T))
Return;
Diễn biến đọc biểu thức
Diễn biến STACK
Thực hiện phép toán
9 – 2 6 / +
5
9
- 2 6 / +
5
2 6 / +
- 4
5 – 9
2
6 / +
- 4
6
2
/ +
- 4
1/3
2/6
+
- 4
- 11/3
- 4 + 1/3
3) Trình bày giải thuật giải hệ phương trình đại số tuyến tính dạng:
A11X1 = b1
A21X1 + A22X2 = b2
…
An1X1 + An2X2 + … + AnmXn = bn
Trong đó để tiết kiệm các hệ số của ma trận được lưu trữ trong một mảng có n(n+1)/2 phần tử.
Bài làm:
Procedure gt(A[1..n, 1..n], B[1..n]);
i := 1;
x[i] := B[1] / A[1,1];
<Lưu x[i] vào mảng>
For i := 2 to n do
S := 0;
Begin
For j := 1 to k – 1 do
S := S + A[k,j]*x[j]
x[k] := (B[k] – S)/ A[k,k];
<Lưu x[k] vào tiếp mảng>
End;
Return;
<In nghiệm>
4) Trình bày giải thuật bổ sung 1 nút mới có chứa dữ liệu X vào trước nút trỏ bởi Q trong danh sách móc nối 2 chiều với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có các trường: Data, P_Trai, P_Phai.
Bài làm:
Procedure Insert (Pdau, Pcuoi, Q, X)
New(p); //Tạo nút mới
Data(p):= X;
If Pcuoi := Null then //Danh sách rỗng
P_trai(p) := P_Phai(p) := Null;
Pdau := Pcuoi := p;
Return
End ;
If Q = Pdau then begin //Q trỏ tới nút cực trái
P_Trai(p) := null;
P_Phai(p) := Q;
P_Trai(p) := p;
Pdau :=p;
Return
End ;
P_Trai(p) := P_Trai(Q); //Bổ sung vào giữa
P_Phai(p) := Q;
P_Trai(Q) := p;
P_Phai(P_Trai(p)) :=p;
Return.
5) Trình bày giải thuật loại bỏ nút trỏ bởi M trong danh sách móc nối 2 chiều với : Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có các trường: Data, P_Trai, P_Phai.
Bài làm:
Procedure Delete(Pdau, Pcuoi, M)
If Pcuoi = null then begin //Trường hợp danh sách rỗng
Write (“Danh sach rong”);
Return
End;
Case //Loại bỏ
Pdau := Pcuoi; //Danh sách chỉ có 1 nút và M trỏ tới nút đó
Pdau := Pcuoi := null
M: = Pdau //Phần tử đầu bị loại
Pdau := P_Phai(Pdau);
P_Trai(Pdau) := null;
M := Pcuoi //Phần tử cuối bị loại
Pcuoi := P_Trai(Pcuoi) ;
P_Phai(Pcuoi) := null ;
Else
P_Phai(P_Trai(M)) := P_Phai(M) ;
P_Trai(P_Phai(M)) := P_Trai(M) ;
End case;
Dispose(M) ;
Return.
6) Trình bày giải thuật duyệt cây theo thứ tự: trước, giữa, sau. Cho biết thứ tự các nút được thăm theo các thứ tự: trước, giữa, sau đối với cây nhị phân sau:
A gốc
B: Con trái của A, C: Con phải của A
D: Con trái của B, E: Con phải của B, F: Con trái của C, G: Con phải của C
H: Con trái của E, I: Con phải của F, J: Con phải của G I J
Bài làm:
Thăm Trước:
Procedure Tham_Truoc(T);
If T = null then
Begin
Write (Info (T));
Tham_Truoc(T(P_Trai));
Tham_Truoc(T(P_Phai)) ;
End ;
Return;
Thăm Giữa
Procedure Tham_Giua(G);
If G <> null then
Begin
Tham_Giua(G(P_Trai);
Write(Info(G));
Tham_Giua(G(P_Phai);
End;
Return;
Thăm Sau
Procedure Tham_Sau(S);
If S <> null then
Begin
Tham_Sau(S(P_Trai));
Tham_Sau(S(P_Phai));
Write(Info(S));
End;
Return;
Duyệt thứ tự trước: A B D E H C F I G J
Duyệt thứ tự giữa: D B H E A F I C G J
Duyệt thứ tự sau: D H E B I F J G C A
7) Biết thứ tự duyệt cây nhị phân theo thứ tự trước là: A B D E H C F I G và theo thứ tự giữa là: D B H E A F I C G, hãy dựng lại cây nhị phân.
Bài làm:
Duyệt theo thứ tự trước: Thăm gốc, cây con trái theo thứ tự trước, cây con phải theo thứ tự trước
Duyệt theo thứ tự giữa: Cây con trái theo thứ tự giữa, thăm gốc, cây con phải theo thứ tự giữa
=> Cây dựng lại: A gốc
B: Con trái của A, C: Con phải của A
D: Con trái của B, E: Con phải của B, F: Con trái của C, G: Con phải của C
H: Con trái của E, I: Con phải của F
Giải thích:
Dựa vào duyệt trước => A: Gốc
Dựa vào duyệt giữa => D, B, H, E thuộc cây con trái của A và F, I, C, G thuộc cây con phải của A
Kết hợp => B: Con trái của A
Dựa vào duyệt giữa => D thuộc cây con trái của B và H, E thuộc cây con phải của B
Kết hợp => D: Con trái của B, E: Con phải của B, H: Con trái của E
C: Con phải của A
Dựa vào duyệt giữa => I, F thuộc cây con trái của C và G thuộc cây con phải của C
Kết hợp => G: Con phải của C, F: Con trái của C, I: Con phải của F
8) Biết thứ tự duyệt cây nhị phân theo thứ tự giữa là: D H B E A F C I G và theo thứ tự sau là: H D E B F I G C A, hay dựng lại cây nhị phân.
Bài làm:
Duyệt theo thứ tự sau: Cây con trái theo thứ tự sau, cây con phải theo thứ tự sau, thăm gốc
Duyệt theo thứ tự giữa: Cây con trái theo thứ tự giữa, thăm gốc, cây con phải theo thứ tự giữa
=> Cây dựng lại: A gốc
B: Con trái của A, C: Con phải của A
D: Con trái của B, E: Con phải của B, F: Con trái của C, I: Con phải của C
H: Con phải của D, G: Con phải của I
Giải thích:
Dựa vào duyệt sau => A: Gốc
Dựa vào duyệt giữa => D H B E thuộc cây con trái của A và F C I G thuộc cây con phải của A
Kết hợp => C: Con phải của A
Dựa vào duyệt giữa => F thuộc cây con trái của C và I G thuộc cây con phải của C
Kết hợp => F: Con trái của C, I: Con phải của C, G: Con phải của I
B: Con trái của A
Dựa vào duyệt giữa => D H thuộc cây con trái của B và E thuộc cây con phải của B
Kết hợp => E: Con phải của B, D: Con trái của B, H: Con phải của D
9) Trình bày giải thuật sắp xếp nhanh (QuickSort)? Trình bày thời gian thực hiện giải thuật với dãy n phần tử. Minh họa diễn biến ở từng bước khi áp dụng giải thuật này với dãy số: 24, 42, 74, 11, 65, 58, 83, 36, 88, 99
Bài làm:
Procedure Quick_Sort(a, vt_dau, vt_cuoi);
Kt:= True;
If vt_cuoi > vt_dau then
Begin
i:= vt_dau + 1;
j:= vt_cuoi - 1;
x:= a[vt_dau];
While kt do
While a[i] < x and I =< vt_cuoi do i:= i+1;
While a[i] > x and j > vt_dau do j:= j+1;
If j>i then
Begin
y := a[j];
a[j] := a[i];
a[i] := y;
End;
Else
Begin
Kt := False;
y := a[vt_dau];
a[vt_dau] := a[j];
a[j] := y;
Quick_Sort(a, vt_dau, j – 1);
Quick_Sort(a, j + 1, vt_cuoi);
End;
End;
Return;
Thời gian thực hiện giải thuật:
Gọi T(n) là thời gian thực hiện giải thuật với dãy n phần tử
P(n) là thời gian để phân chia dãy n phần tử thành 2 đoạn
=> T(n) = P(n) + T(j – vt_dau) + T(vt_cuoi – j)
= C.n + …
Giả sử: Sau mỗi bước dãy được chia làm 2 phần bằng nhau
=> T(n) = C.n + 2.T(n/2)
= C.n + 2 C.n/2 + 4.T(n/4)
= …
= C.n + 2 C.n/2 + 4 C.n/4 + 2log2n C(n/2log2n) T(1)
= C.n + C.n + … + C.n
T(1) = 1 khi thực hiện đến bước thứ log2n
Có log2n phần tử C.n
T(n) = C.n log2n = O(nlog2n)
10) Trình bày giải thuật sắp xếp hòa nhập (Merge Sort)? Trình bày thời gian thực hiện giải thuật với dãy n phần tử. Minh họa diễn biến ở từng bước khi áp dụng giải thuật này với dãy số: 34, 15, 74, 11, 65, 58, 83, 36, 88, 99.
Bài làm:
Hòa nhập 2 đường
Procedure Merge(X, b, m, n, Z);
i := b j := m+1; k := b; //Khởi tạo các chỉ số
While (i<m) and (j<n) do //So sánh để chọn phần tử nhỏ hơn
Begin
If X[i] < X[j] then
Begin
Z[k] := X[i; i:= i+ 1;
End;
Else
Begin
Z[k] := X[j]; j := j+1;
End;
k := k+1;
End;
If i > m then
(Z[k],…,Z[n]) := (X[j],…,X[n])
Else //Đoạn sau hết phần tử
(Z[k],…,Z[n]) := (X[i],…,X[m])
Return;
Hòa nhập 2 đường trực tiếp
Thủ tục sắp xếp hòa nhập từng cặp mạch kề cận:
Procedure MPass(X,Y,n,k)
i := 1;
While i =< n – 2k+ 1 do //Vẫn còn đủ 2 mạch ở phía sau
Begin
Merge (X, i, i + k- 1, i + 2k – 1, Y);
i := i + 2k;
end;
//Hòa nhập mạch còn lại có độ dài tổng >k, <2k
If i + k – 1 < n then
Merge(X, i, i + k – 1, n);
Else //Chỉ còn 1 mạch cuối cùng
(Y[i],…,Y[n]) := (X[i],…,X[n]);
Return;
Thủ tục sắp xếp hòa nhập
Procedure Straight_Msort (X,n);
k := 1;
While k < n do
Begin
MPass (X, Y, k); k := 2*k;
MPass (Y,X,k); k := k*2;
End;
Return;
Thời gian thực hiện giải thuật:
Dễ nhận thấy phép chuyển đổi chỗ nhiều hơn phép so sánh do vậy ta chọn phép đổi chỗ làm phép toán tích cực.
Ta thấy mỗi khi gọi đến MPass thì toàn bộ các phần tử của mảng được duyệt qua 1 lần và chuyển sang 1 vùng mới từ X sang Y hoặc từ Y sang X. Do vậy MPass có cấp độ thực hiện thời gian là O(n)
Số lần gọi MPass chính là log2n
=> Độ phức tạp O(nlog2n)
11) Trình bày giải thuật tìm kiếm nhị phân. Trình bày thời gian thực hiện giải thuật với cây có n nút.
Bài làm:
Function Binary_Search (k,r,a,X);
If k>r then
tg := 0 then //Không tìm thấy
Else
Begin
m := (k + r) div 2;
If a[m] = X then
tg := X; //Tìm thấy
Else
If X < a[m] then
Binary_Search (k, m – 1, a, X);
Else
Binary_Search (m+1, r, a, X);
End;
Return tg;
Thời gian thực hiện:
Thuận lợi nhất khi tìm thấy ngay ở giữa: O(1)
Không thuận lợi khi phải gọi đệ qui, gọi thời gian cần thực hiện trong trường hợp này là:
W(r – k + 1)
Với lần gọi ban đầu: k = 1, r = n
Có W(n – 1 + 1) = W(n) = 1 + W(n/2)
= 1 + 1 + W(n/4)… = 1 + 1 + … + W(n/2x)
Dừng khi (n/2x) = 1 vì W(1) = 1
Mà (n/2x) = 1 ó x = log2n
Tức là ta phải gọi đệ qui log2n lần
=> Độ phức tạp là O(log2n)
12) Trình bày giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm kiếm. Dựng cây nhị phân tìm kiếm với dãy khóa nhập vào là: 10, 7, 19, 11, 3, 16, 13, 4, 22, 5.
Bài làm:
Function BST(T,X);
P := null; q = T;
While q <> null do
Case
X <Key(q): p := q; //Lưu cha của q
q := P_Trai(q);
X = Key(q) : Return(q);
X > Key(q) : p := q;
q := P_Phai(q);
End Case; //Không tìm thấy, cần bổ sung
New(q);
Key(q) := X;
P_Trai(q) := null;
P_Phai(q) := null;
Case
T = null : T := q;
X < Key(P) : P_Trai(P) := q;
X > Key(P) : P_Phai(P) := q;
End Case;
Write(“Khong tim thay, da bo sung”);
Return (q);
Dựng cây nhị phân:
10: Gốc
7: Con trái của 10, 19: Con phải của 10
3: Con trái của 7, 11: Con trái của 19, 22: Con phải của 19
4: Con phải của 3, 16: Con phải của 11
5: Con phải của 4, 13: Con trái của 16
Bạn đang đọc truyện trên: Truyen2U.Pro