Giải thuật và lập trình

Lê Minh Hoàng  Bài Giảng Chuyên Đề Đại Học Sư Phạm Hà Nội, 1999-2002 Lời Cảm Ơn Tôi Muốn Bày Tỏ Lòng Biết Ơn Đối Với Những Người Thầy Đã Chỉ Dạy Tận Tình Trong Những Năm Tháng Đầy Khó Khăn Khi Tôi Mới Bước ...

 vii  Hình 40: Xóa nút có cả hai nhánh con trên cây BST thay bằng nút cực phải của cây con trái 120 Hình 41: Xóa nút có cả hai nhánh con trên cây BST thay bằng nút cực trái của cây con phải 120 Hình 42: Đánh số các bit 123 Hình 43: Cây tìm ...

A 2 = b 2 … a k-1 = b k-1 a k = b k a k+1 < b k+1 Trong trường hợp này, ta có thể viết a < b. Thứ tự đó gọi là thứ tự từ điển trên các dãy độ dài n. Khi độ dài hai dãy a và b không bằng nhau, người ta cũng xác định được thứ tự ...

InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 30; var x: array[1.max] of Integer; n: Integer; f: Text; procedure PrintResult; {In cấu hình tìm được, do thủ tục tìm đệ quy Try gọi khi tìm ra một cấu hình} var i: Integer; begin for i := 1 to n do ...

QUEENS.INP QUEENS.OUT 5 (1, 1); (2, 3); (3, 5); (4, 2); (5, 4); (1, 1); (2, 4); (3, 2); (4, 5); (5, 3); (1, 2); (2, 4); (3, 1); (4, 3); (5, 5); (1, 2); (2, 5); (3, 3); (4, 1); (5, 4); (1, 3); (2, 1); (3, 4); (4, 2); (5, 5); (1, 3); (2, 5); (3, 2); (4, 4); (5, 1); (1, 4); (2, 1); (3, 3); (4, 5); (5, ...

End; {Hàm Check(i) cho biết X i có làm hỏng tính không lặp của dãy X 1 X 2 … X i hay không} function Check(i: Integer): Boolean; var l: Integer; begin for l := 1 to i div 2 do {Thử các độ dài l} if Same(i, l) then {Nếu có xâu độ dài l kết thúc bởi X i bị ...

Lỗi thuật toán: Lỗi này ít gặp nhất nhưng nguy hiểm nhất, nếu nhẹ thì phải điều chỉnh lại thuật toán, nếu nặng thì có khi phải loại bỏ hoàn toàn thuật toán sai và làm lại từ đầu. 1.5.2. Xây dựng các bộ test Có nhiều chương ...

3.3. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY 3.3.1. Hàm tính giai thừa function Factorial(n: Integer): Integer; {Nhận vào số tự nhiên n và trả về n!} begin if n = 0 then Factorial := 1 {Phần neo} else Factorial := n * Factorial(n - 1); {Phần đệ quy} end; Ở đây, phần neo ...

A) Tạo ra một nút mới NewNode chứa giá trị V: V b) Tìm nút q là nút đứng trước nút p trong danh sách (nút có liên kết tới p). b 1 ) Nếu tìm thấy thì chỉnh lại liên kết: q liên kết tới NewNode, NewNode liên kết tới p Head A B C D E q p V b 2 ) ...

End; begin Last := (Last + 1) mod max; {Last chạy theo vòng tròn} Queue[Last] := V; Inc(n); end; function Pop: Integer; {Lấy một phần tử khỏi Queue, trả về trong kết quả hàm} begin if n = 0 then WriteLn('Queue is Empty') else begin Pop := Queue[First]; First := (First ...

6.4.2. Duyệt theo thứ tự giữa (inorder traversal) Trong phép duyệt theo thứ tự giữa thì giá trị trong mỗi nút bất kỳ sẽ được liệt kê sau giá trị lưu ở nút con trái và được liệt kê trước giá trị lưu ở nút con phải của nút đó, có ...

T := ''; {Đặt lại T để chuẩn bị đọc phần tử mới} end; WriteLn(RPN, ' = ', Pop:0:4); {In giá trị biểu thức RPN được lưu trong Stack} end. 7.4. CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ Có thể nói rằng việc tính toán biểu ...

Thứ tự sắp xếp. Một cách tổng quát, ta sẽ sắp xếp dãy k 1 , k 2 , …, k i trong điều kiện dãy k 1 , k 2 , …, k i-1 đã sắp xếp rồi bằng cách chèn k i vào dãy đó tại vị trí đúng khi sắp xếp. procedure InsertionSort; var i, j: Integer; tmp: ...

9 8 6 7 4 2 1 3 5 5 8 6 7 4 2 1 3 9 Hình 33: Vun phần còn lại thành đống rồi lại đảo trị k 1 cho k n-1 Thuật toán HeapSort có hai thủ tục chính: Thủ tục Adjust(root, endnode) vun cây gốc root thành đống trong điều kiện hai cây gốc 2.root và 2.root +1 ...

8.11. THUẬT TOÁN SẮP XẾP TRỘN (MERGESORT) 8.11.1. Phép trộn 2 đường Phép trộn 2 đường là phép hợp nhất hai dãy khoá đã sắp xếp để ghép lại thành một dãy khoá có kích thước bằng tổng kích thước của hai dãy khoá ban đầu và dãy ...

( EXCHANGE RADIXSORT ) procedure RadixSort; const MaxBit = 13; var MaskBit: array[0.MaxBit] of Integer; MaxValue, i: Integer; procedure Partition(L, H, BIndex: Integer); var i, j, Mask: Integer; begin if L >= H then Exit; i := L; j := H; Mask := MaskBit[BIndex]; repeat while (i < j) and (k[i] ...

4 2 6 1 3 5 7 9 Hình 37: Cây nhị phân tìm kiếm Thuật toán tìm kiếm trên cây có thể mô tả chung như sau: Trước hết, khoá tìm kiếm X được so sánh với khoá ở gốc cây, và 4 tình huống có thể xảy ra: Không có gốc (cây rỗng): X không có trên ...

Về mặt trung bình, các thao tác tìm kiếm, chèn, xoá trên cây tìm kiếm số học đều có độ phức tạp là O(log 2 n) còn trong trường hợp xấu nhất, độ phức tạp của các thao tác đó là O(z), bởi cây tìm kiếm số học có chiều cao không ...

Ví dụ với n = 5, bảng F sẽ là: F 0 1 2 3 4 5 0 1 0 0 0 0 0 1 1 1 1 1 1 1 2 1 1 2 2 3 3 3 1 1 2 3 4 5 4 1 1 2 3 5 6 5 1 1 2 3 5 7 m v Nhìn vào bảng F, ta thấy rằng F[m, v] được tính bằng tổng của: Một phần tử ở hàng trên: F[m - 1, v] và một phần tử ở ...

§3. MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG 3.1. DÃY CON ĐƠN ĐIỆU TĂNG DÀI NHẤT Cho dãy số nguyên A = a 1 , a 2 , …, a n . (n  5000, -10000  a i  10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy ...

STR.INP STR.OUT PBBCEFATZQABCDABEFA 7 PBBCEFATZ -> Delete(9) -> PBBCEFAT PBBCEFAT -> Delete(8) -> PBBCEFA PBBCEFA -> Insert(4, B) -> PBBCBEFA PBBCBEFA -> Insert(4, A) -> PBBCABEFA PBBCABEFA -> Insert(4, D) -> PBBCDABEFA PBBCDABEFA -> Replace(2, A) -> PABCDABEFA ...

Procedure Result; var fo: Text; i, t, j: Integer; Sum: LongInt; begin t := 0; {Tính lại các Count[i] := Số phần tử phương án tối ưu sẽ chọn trong lớp i} for i := k - 1 downto 0 do begin j := Trace[i, t]; t := Sub(t, j * i); Count[i] := j; end; Assign(fo, OutputFile); ...

A B C D A A A B B B C D A B C B C B A D B D D D Cho xâu S gồm n ký tự chỉ gồm các chữ A, B, C, D. Xét phép co R(i): thay ký tự S i và S i+1 bởi ký tự nằm trên hàng S i , cột S i+1 của bảng H. Ví dụ: S = ABCD; áp dụng liên tiếp 3 lần R(1) sẽ được ...

Đối với danh sách kề, việc duyệt tất cả các đỉnh kề với một đỉnh v cho trước là hết sức dễ dàng, cái tên "danh sách kề" đã cho thấy rõ điều này. Việc duyệt tất cả các cạnh cũng đơn giản vì một cạnh thực ra là ...

U := FindNext(u); until u = 0; end; 3.3. THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG (BREADTH FIRST SEARCH) 3.3.1. Cài đặt bằng hàng đợi Cơ sở của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Việc thăm một đỉnh sẽ lên lịch duyệt ...

Đồ thị đầy đủ K n có đúng: C 2  n .(n  1) cạnh và bậc của mọi đỉnh đều bằng n - 1. n 2 K 3 K 4 K 5 Hình 62: Đồ thị đầy đủ 4.3.2. Bao đóng đồ thị: Với đồ thị G = (V, E), người ta xây dựng đồ thị G' = (V, E') cũng ...

Thuộc nhánh DFS gốc u tới một đỉnh thăm trước u. Khi đó chỉ việc liệt kê các đỉnh thuộc thành phần liên thông mạnh chứa u là nhánh DFS gốc u. Để công việc dễ dàng hơn nữa, ta định nghĩa một danh sách L được tổ chức dưới ...

5.2. TẬP CÁC CHU TRÌNH CƠ BẢN CỦA ĐỒ THỊ Xét một đồ thị vô hướng liên thông G = (V, E); gọi T = (V, F) là một cây khung của nó. Các cạnh của cây khung được gọi là các cạnh trong, còn các cạnh khác là các cạnh ngoài. Nếu thêm một ...

Tra lại điều kiện: nếu u là gốc cây DFS thì nó là khớp khi và chỉ khi nó có ít nhất 2 nhánh con, nếu không thoả mãn điều kiện đó thì đánh dấu lại u không là khớp. Input: file văn bản GRAPH.INP với khuôn dạng như bài toán liệt kê cầu ...

Break; end; if u = Get then {Nếu phần tử ở đỉnh ngăn xếp vẫn là u  vòng lặp trên không tìm thấy đỉnh nào kề với u} begin Inc(count); Write(f, Pop, ' '); {In ra phần tử đỉnh ngăn xếp} end; end; Close(f); end; begin Enter; FindEulerCircuit; end. ...

2 2 3 1 20 1 3 4 20 5 6 4 5 MINPATH.INP MINPATH.OUT 6 7 1 4 Distance from 1 to 4: 15 1 2 1 4<-5<-6<-3<-2<-1 1 6 20 2 3 2 3 6 3 3 4 20 5 4 5 6 5 4 8.3. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH ÂM - THUẬT TOÁN FORD BELLMAN Thuật toán Ford-Bellman có thể phát biểu ...

Init; Dijkstra; PrintResult; end. 8.6. TRƯỜNG HỢP ĐỒ THỊ KHÔNG CÓ CHU TRÌNH - THỨ TỰ TÔ PÔ Ta có định lý sau: Giả sử G = (V, E) là đồ thị không có chu trình (có hướng - tất nhiên). Khi đó các đỉnh của nó có thể đánh số sao cho mỗi cung ...

Thứ nhất, làm thế nào để xét được các cạnh từ cạnh có trọng số nhỏ tới cạnh có trọng số lớn. Ta có thể thực hiện bằng cách sắp xếp danh sách cạnh theo thứ tự không giảm của trọng số, sau đó duyệt từ đầu tới cuối ...

§10. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG Ta gọi mạng (network) là một đồ thị có hướng G = (V, E), trong đó có duy nhất một đỉnh A không có cung đi vào gọi là điểm phát (source), duy nhất một đỉnh B không có cung đi ra gọi là đỉnh thu ...

IncFlow; until False; PrintResult; end. Định lý về luồng cực đại trong mạng và lát cắt hẹp nhất: Luồng cực đại trong mạng bằng khả năng thông qua của lát cắt hẹp nhất. Khi đã tìm được luồng cực đại thì theo thuật toán trên sẽ ...

Người ta đã chứng minh được chi phí thời gian thực hiện giải thuật này trong trường hợp xấu nhất sẽ là O(n 3 ) đối với đồ thị dày và O(n(n + m)logn) đối với đồ thị thưa. Tuy nhiên, cũng giống như thuật toán Ford-Fulkerson, trên ...

Tức là nếu như cạnh (X[i], Y[j]) thuộc bộ ghép thì matchX[i] = j và matchY[j] = i. Quy ước rằng: Nếu như X[i] chưa ghép với đỉnh nào của tập Y thì matchX[i] = 0 Nếu như Y[j] chưa ghép với đỉnh nào của tập X thì matchY[j] = 0. Để thêm một ...

Repeat i := Pop; {Rút một đỉnh X[i] khỏi hàng đợi} for j := 1 to k do {Quét những Y_đỉnh chưa thăm} if Trace[j] = 0 then begin w := GetC(i, j); {xét cạnh (X[i], Y[j])} if w = 0 then {Nếu là 0_cạnh} begin Trace[j] := i; {Lưu vết đường đi} if matchY[j] = 0 then ...

Input: file văn bản GMATCH.INP  Dòng 1: Chứa hai số n, m lần lượt là số cạnh và số đỉnh của đồ thị cách nhau ít nhất một dấu cách (n  100)  m dòng tiếp theo, mỗi dòng chứa hai số u, v tượng trưng cho một cạnh (u, v) của đồ ...