Tài liệu Bồi dưỡng học sinh giỏi môn tin học chuyên đề cấu trúc dữ liệu đặc biệt

Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 CẤU TRÚC DỮ LIỆU ĐẶC BIỆT Để đáp ứng được yêu cầu của công tác giảng dạy đội tuyển Tin học. Bản thân mỗi giáo viên chúng ta luôn phải tìm tòi, nghiên cứu, trao đổi kiến thức và kinh nghiệm giảng dạy với các đồng nghiệp. Bên cạnh đó, nguồn tài liệu trên mạng cũng là một nguồn quý giá đối với giáo viên chúng ta. Tuy nhiên, việc tổng hợp, biên tập thành tài liệu có nội dung phù hợp cho đối tượng học sinh của mình lại là một vấn đề quan trọng hơn nữa. Vì vậy, với chuyên đề này tôi xin được đề cập đến một tài liệu được sưu tầm mà tôi thường dùng để giảng dạy cho học sinh trong đội tuyển, những bài toán mà bản thân tôi thấy tâm đắc. Trong tài liệu này đề cập đến cấu trúc dữ liệu:  Heap  Disjoint-Set 1. HEAP Như bạn đã biết, Heap là một cấu trúc hữu dụng vào bậc nhất trong giải toán. Heap là một dạng hàng đợi có độ ưutiên, có ứng dụng to lớn trong nhiều dạng toán khác nhau. Heap thực chất là một cây cân bằng thoả mãn các điều kiện sau:  1 nút chỉ có không quá 2 nút con.  Nút cha là nút lớn nhất, mọi nút con luôn có giá trị nhỏ hơn nút cha. Trong đó, điều kiện quan hệ nhỏ hơn của nút con so với nút cha có thể được quy định trướctuỳ theo bài toán, không nhất thiết phải là nhỏ hơn theo nghĩa toán học. Ví dụ: Mặc dù được mô tả như cây nhưng Heap lại có thể lưu trữ trong mảng, nút gốc là nút 1, nút con của nút i là 2 nút 2*I và 2*I+1. Đặc điểm của Heap: Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014  Nút gốc luôn là nút lớn nhất [theo định nghĩa cótrước]  Độ cao của 1 nút luôn nhỏ hơn hoặc bằng O(logN) vìcây Heap cân bằng. * Ứng dụng của Heap: Tìm min, max trong một tập hợp động, nghĩa là tậpcó thể thay đổi, thêm, bớt các phần tử. * Các thao tác thường dùng trong xử lý HEAP:  Up_heap: Nếu 1 nút lớn hơn cha của nó thì di chuyển nó lên trên.  Down_heap: Nếu 1 phần tử nhỏ hơn 1 con của nó thì di chuyển nó xuống dưới  Push: Đưa 1 phần tử vào HEAP bằng cách thêm 1 nút vào cây và up_heap nút đó  Pop: Loại 1 phần tử khỏi HEAP bằng cách chuyển nó xuống cuối heap và loại bỏ, sauđó chỉnh sửa lại heap sao cho thoả mãn các điều kiện của HEAP. Ví dụ: Biến top là số phần tử của heap, A là mảng chứa heap,doicho(i,j) là thủ tục đổi chỗ 2 phần tử i và j của heap. Procedure Up_heap(i: longint ); Procedure Push(giatri :longint ); Begin Begin If (i = 1) or (a[i] > a[i div 2]) inc(top); then exit; // i div 2 là nút cha của i a[top]:=giatri; //mở rộng và thêm doicho(i, i div 2); 1 phần tử vào tập up_heap(i div 2); up_heap(top); //chỉnh lại heap end; cho thoả mãn điều kiện Procedure Down_heap(i: longint ); End; Begin Procedure Pop(vitri: longint ); j := i*2; Begin if j > top then exit; a[vitri]:=a[top]; if (j < top) and (a[j] > a[j -1]) dec(top); //loại 1 phần tử ra khỏi then j := j+1; //chọn nút lớn hơn trong heap 2 nút con //chỉnh lại heap, nếu phần tử bị doicho(i,j); loại luôn ở đầu heap có thể bỏ up_heap down_heap(j); up_heap(vitri); Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 End; down_heap(vitri); End; Trong quá trình đưa một phần tử ra khỏi heap tại vị trí bất kìphải thực hiện cả 2 quá trình up_heap và down_heap để đảm bảo Heap vẫn thoảmãn điều kiện đã cho. Qua đoạn chương trình ta có thể thấy được các điều kiện của HEAP vẫn được bảo tồnsau khi tập bị thay đổi. Heap được sử dụng trong thuật toán Dijkstra, Kruskal, Heap Sort nhằm giảm độphức tạp thuật toán. Heap còn có thể sử dụng trong các bài toán dãy số, quy hoạch động, đồthị... Với những ví dụ sau ta sẽ thấy phần nào sự đa dạng và linh hoạt trong sử dụngHeap. Để thuận tiện ta gọi Heap-max là heap mà giá trị nút cha lớn hơn giá trị nútcon (phần tử đạt max là gốc của Heap) và Heap-min là heap mà giá trị nút cha nhỏhơn giá trị nút con (phần tử đạt min là gốc của heap). Bài toán 1: MEDIAN Phần tử trung vị của 1 tập N phần tử là phần tử có giá trị đứng thứ N div 2+1 với N lẻ và N div 2 hoặc N div 2+1 với N chẵn. Cho 1 tập hợp ban đầu rỗng. Trong file Input c ó M ≤ 10000 thao tác thuộc 2 loại:  PUSH gtr đưa 1 phần tử giá trị gtr vào trong HEAP (gtr ≤ 109).  MEDIAN trả về giá trị của phần tử trung vị của tập hợp đó (nếu N chẵn trả về cả2 giá trị). Yêu cầu: Viết chương trình đưa ra file OUTPUT tương ứng. Input: Dòng đầu tiên ghi số M, M dòng tiếp theo ghi 1 trong 2 thao tác theo địnhdạng trên. Output: Tương ứng với mỗi thao tác MEDIAN trả về 1 (hoặc 2) giá trị tương ứng. Thuật giải: Dùng 2 heap, 1 heap (HA) lưu các phần tử từ thứ 1 tới N div 2 và heap còn lại (HB) lưu các phần tử từ N div 2 +1 tới N sau khi đã sort lại tập thành tăngdần. HA là Heap-max còn HB là Heap-min. Như vậy phần tử trung vị luôn là gốc HB(N lẻ) hoặc gốc của cả HA và HB (n chẵn). Thao tác MEDIAN do đó chỉ có độ phứctạp O(1). Còn thao tác PUSH sẽ được làm trong O(logN) như sau: Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014  Nếu gtr đưa vào nhỏ hơn hoặc bằng HA[1] đưa vào HA ngược lại đưa vào HB. Sốphần tử N của tập tăng lên 1.  Nếu HA có lớn hơn (hoặc nhỏ hơn N) div 2 phần tử thì POP một phần tử từ HA (hoặc HB) đưavào heap còn lại. Sau quá trình trên thì HA và HB vẫn đảm bảo đúng theo định nghĩa ban đầu. Bàitoán được giải quyết với độ phức tạp O(MlogM). Bài toán 2: Có N công việc buộc phải hoàn thành trước thời gian D[i] (thời gianhiện tại là 0). N công việc này được giao cho một programmer lười biếng. Xét một côngviệc i, bình thường programmer này làm xong trong B[i] thời gian nhưng nếu đượctrả thêm c($) thì sẽ làm xong trong B[i]-c*A[i] (nếu c=B[i]/A[i] thì anh ta có thể làmxong ngay tức khắc, t=0). Tất nhiên c ≤ B[i]/A[i]. Tiền trả thêm này với từng côngviệc là độc lập với nhau. Yêu cầu: Với các mảng D[], B[] và A[] cho trước, hãy tìm số tiền ít nhất phải trả thêm choprogrammer để mọi công việc đều hoàn thành đúng hạn. Input:  Dòng đầu tiên ghi số N.  Dòng thứ I trong N dòng tiếp theo mỗi dòng ghi 3 sốlần lượt là A[i], B[i] và D[i]. Output: Tổng số tiền nhỏ nhất phải trả thêm (chính xác tới 2 chữ số thập phân). Giới hạn: N ≤ 105, 1 ≤ A [i],B[i] ≤ 104, 1 ≤ D[i] ≤ 109. Thuật giải: Nhận thấy nếu xét tới thời điểm T thì mọi công việc có D[i]T: C[j]=C[j]-T/A[j]; tien= tien + T/A [j];kết thúc xử lý công việc I.  C[j]*A[j]=T: loại bỏ j ra khỏi heap; tien=tien + C[j];kết thúc;//thời gian làm j đã = 0  C[j]*A[j]4 kếtquả = -1. Thuật giải:Ta tính trước maxk=100 đường đi ngắn nhất từ a tới b. Với 1 đỉnh dùng thuật toán DIJKSTRA để tính maxkđường đi ngắn nhất tới tất cả các đỉnh còn lại. Giả sử đang xét tới đỉnh U, C[u,v,k] làđường đi ngắn thứ k từ u tới v. Với mỗi V <> U tính C[u,v,k] lần lượt với k từ 1 tớimaxk (tính xong giá trị cũ rồi mới tính tới giá trị mới), k0[v] là giá trị k đang đượctính của v (khởi tạo k0[v]=1). Sau đây là các bước cơ bản của thuật toán: CONNECTION(U) 1. Với v=1..N, v<>u: Tìm v: C[u,v,k0[v]] đạt GTNN, min=C [u,v,k0[v]]. 2. Xác nhận C[u,v,k0[v]] là đường cần tìm, K0[v]= K0[v]+1. 3. Với các v’ mà có đường từ v tới v’ (dài L) tạo thêm 1 đường từ u tới v’ độ dàiL’=min+L, cập nhật đường đi từ U tới V. End; Các bước 1 và 3 là của thuật toán Dijkstra thông thường. Vì các giá trị min chỉ đượcxét 1 lần nên với mọi đường đi mới từ U tới V’ ta đều phải lưu trữ lại, nhưng, do chỉcần tìm maxk đường ngắn nhất nên ta cũng chỉ cần lưu trữ lại maxk-k0[v’] đường. Bước 3 viết rõ ràng như sau: 3.Update(v’,L’) 3.1. Tìm đường dài nhất trong các đường đã lưu. 3.2. Nếu đường này ngắn hơn L’ kết thúc. 3.3. Loại bỏ đường này. 3.4. Lưu trữ đường dài L’. Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 Tập các đường được lưu trữ với 1 đỉnh V là tập động, ta dùng 1 heap-max để lưu trữtập các đường này. Lúc đó trong bước 1 thì C[u,v,k0[v]] phải chọn là min của tậptrên. Có thể kết hợp 1 heap-min để tìm nhanh C [u,v,k0[v]]. Cách này cài đặt phứctạp và đòi hỏi phải hiểu rõ về heap. Một cách khác đơn giản hơn là luôn cập nhậtC[u,v,k0[v]] trong mỗi bước tìm được đường mới: 3.Update(v’,L’) 1.2.3.4 {các bước này như cũ} 5. Nếu (L’ C[u,v,k0[v]]=L’. Nhưng khi đó trong bước 2 của thuật toán ban đầu cần bổ sung như sau: 2.a/ Xác nhận, K0[v]:= K0[v]+1. b/Nếu K0[v]0 do i:= P[i]; FindSet:=i; End; Procedure Union(i,j: longint ); Var u,v:longint ; Begin U:=FindSet(i);V:=FindSet(j); P[v]:=u; End; Trong trường hợp cây suy biến, hàm FindSet có thể phải thực hiện trong O(N). Vìvậy có 1 số heuristic để hỗ trợ cho disjoint-set đó là Union_by_rank vàPath_compression. Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 - Union_by_rank thực chất là xét ưu tiên các Set khi Union chứ không Union 1cách bất kì như trên. Một cách ưu tiên là nối tập có số phần tử ít hơn vào tập có sốphần tử nhiều hơn, như vậy hàm FindSet sẽ thực hiện nhanh hơn do độ cao củacác nút trong 1 cây giảm đi. Giá trị P[] của gốc sẽ lưu số lượng nút của câynhưng mang giá trị âm. Hàm Union được viết lại như sau: Procedure Union(i,j: longint ); Var u,v:longint ; Begin U:=findSet(i);v:=findset(j); If P[u] Union(Findset(i),Findset(j)); 2. I J là thù --> if (thu[i]=0) thu[i]=j otherwise Union(findset(i),findset(thu[j])). Tương tự với J. Độ phức tạp thuật toán chỉ còn là O(M*alpha(N)). Bài tập làm thêm: 1. Parity: Cho một dãy nhị phân có n phần tử. (n ≤ 109) và m câu phát biểu(m ≤ 5000). Mỗi câu phát biểu có dạng a b c. Có ý nghĩa là đoạn từ a đến b có tổng các số 1 là lẻnếu c=1 và chẳn nếu c=0.Hãy xác định xem các phát biểu ấy còn đúng đến câu số mấy (tức là tồn tại ít nhất 1dãy nhị phân n phần tử thoả mãn tất cả các điều kiện tới câu đó). Input: Dòng đầu ghi số N, dòng tiếp theo ghi số M. Trong M dòng tiếp theo ghi 3 sốa b c mô tả 1 phát biểu. Output: Duy nhất 1 số là số lớn nhất mà tới câu phát biểu đó thì mọi phát biểu từ đótrở lên đều đúng. BT.INP 10 5 120 341 560 160 7 10 1 2. BẮC CẦU BT.OUT 3 Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 III V II Chính phủ quốc đảo Oceani quyết định xây dựng m chiếc cầu nối n đảo của mình, tạo một mạng lưới giao thông đường bộ cho phép đi từ dảo bất kỳ tới đảo khác bằng đường bộ (trực I 0 1 tiếp hoặc qua một số đảo trung gian). Mỗi cây cầu sẽ nối 2 đảo khác nhau và cho phép đi lại hai chiều. Các đảo được đánh số từ 0 đến n-1. Bị hạn chế bởi kinh phí và nguồn nhân lực, người ta 2 3 quyết định sẽ xây dựng lần lượt từng chiếc cầu IV một và lên kế hoạch xác định cầu và trình tự xây. Mỗi cây cầu được xác định bởi cặp đảo u, v mà nó nối. Trong quá trình thực hiện kế hoạch có thể đến một lúc nào đó từ một đảo đã có thể đi đến bất kỳ đảo khác bằng đường bộ. Ví dụ, ở Oceani có 4 đảo và người ta quyết định xây dựng 5 cầu theo trình tự lần lượt là 0 – 1, 0 – 2, 1 – 2, 2 – 3, 3 – 0. Tuy vậy, không cần chờ đợi đến khi hoàn thành kế hoạch xây cầu, sau khi cầu thứ 4 được xây xong tất cả các đảo đã được nối liền bằng đường bộ. Yêu cầu: Cho n, m và các cây cầu dự kiến xây. Thông tin về các cây cầu đưa ra theo đúng trình tự xây dựng. Hãy xác định số cầu tối thiểu cần xây theo kế hoạch để từ một đảo đã có thể đi đến bất kỳ đảo khác bằng đường bộ. Dữ liệu: Vào từ file văn bản BRIDGES.INP:  Dòng đầu tiên chứa 2 số nguyên n và m (1 ≤ n ≤ 106, 1 ≤ m ≤ 5106),  Dòng thứ i trong m dòng tiếp theo chứa 2 số nguyên u và v xác định cây cầu thứ i cần xây. Kết quả: Đưa ra file văn bản BRIDGES.OUT kết quả tìm được dưới dạng một số nguyên. Ví dụ: BRIDGES.INP BRIDGES.OUT 45 01 4 Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 02 12 23 30 4. NÚT CHA CHUNG GẦN NHẤT Cây là một cấu trúc dữ liệu quen thuộc trong tin học. Ví dụ ta có cây với 16 nút như hình bên dưới.Các nút được đánh số từ 1 đến 16. Nút 8 là gốc. Nút x được gọi là nút cha của y, nếu tồn tại một đường dẫn từ gốc tới y đi qua x. Ví dụ, nút 4 là nút cha của nút 16, nút 10 cũng là nút cha của 16. Một nút đồng thời là nút cha của chính mình. Như vậy, các nút 8, 4, 10 và 16 là nút cha của 16. Nút x được gọi là nút cha chung của hai nút khác nhau y và z, nếu nó vừa là nút cha của y, vừa là nút cha của z. Ví dụ, các nút 8 và 4 đều là nút cha chung của các nút 7 và 16. Nút x được gọi là nút cha chung gần nhất của y và z, nếu nó là nút cha chung của hai nút này và trên đường dẫn từ x tới y không còn nút cha chung nào khác của y và z. Ở cây đang xét, 4 là nút cha chung gần nhất của 7 và 16. Hãy lập trình tìm nút cha chung gần nhất của hai nút khác nhau của một cây có N nút, các nút được đánh số từ 1 tới N. Dữ liệu: Vào từ file văn bản ANCES.INP:  Dòng đầu tiên chứa số 2 nguyên N K- trong đó N - số nút của cây, 2 ≤ N ≤ 10 000, K – nút gốc,  N-1 dòng còn lại: mỗi dòng chứa 2 số nguyên - 2 nút liên tiếp của cây,  Dòng cuối cùng chứa 2 số nguyên khác nhau – 2 nút cần tìm nút cha chung gần nhất. Kết quả: Đưa ra file văn bản ANCES.OUT một số nguyên – nút cha chung gần nhất. ANCES.INP 16 8 ANCES.OUT 4 Hội thảo các trường chuyên miền Duyên Hải Bắc Bộ 2014 1 14 85 10 16 59 46 84 4 10 1 13 6 15 10 11 67 10 2 16 3 81 16 12 16 7 Cấu trúc dữ liệu trong lập trình nói chung, cấu trúc Heap và Disjoint-set nói riêng là nội dung quan trọng trong việc bồi dưỡng học sinh giỏi. Nắm được những nội dung này, giáo viên và học sinh có thể giải quyết bài toán với độ phức tạp tốt nhất. Thông qua những tài liệu sưu tầm được, người giáo viên cần tổng hợp, chọn lọc và biên tập lại để có được tài liệu phù hợp với đối tượng học sinh của mình. Với cá nhân tôi, khi giao tài liệu này cho học sinh, yêu cầu học sinh nghiên cứu, sau đó thầy trò cùng tháo gỡ những khó khăn mà học sinh gặp phải. Qua hệ thống bài tập bên trên và những bài tập trên www.vn.spoj.comđã giúp cho học sinh rèn luyện kĩ năng cài đặt thuật toán tốt hơn. Tôi hi vọng với chuyên đề nhỏ này có thể giúp cho học sinh của các đội tuyển có thêm nguồn tài liệu bổ ích và cũng mong được sự đóng góp ý kiến, đóng góp bài tập về chủ đề này của thầy cô để chuyên đề được đầy đủ hơn. Tôi xin trân trọng cảm ơn.