Ha Hoang's Blog

bài viết này tôi nói về cách thức hoạt động của thuật toán Heap Sort. I. Khái niệm 1. Định nghĩa Heap – Định nghĩa Heap sơ khởi: Heap là 1 cây nhị phân đầy đủ. + vd1: – Mỗi node trong Heap chứa 1 giá trị có thể so sánh với giá trị của node khác 2. Tính chất Heap + Max Heap: Giá trị của mỗi node >= giá trị của các node con nó => Node lớn nhất là node gốc + Min Heap: Giá trị của mỗi node <= giá trị của các node con nó => Node nhỏ nhất là node gốc + vd3: 3. Biểu diễn Heap bằng mảng – Thứ tự lưu trữ trên mảng được thực hiện từ trái => phải – Nếu ta biết được chỉ số của 1 phần tử trên mảng, ta sẽ dễ dàng xác định được chỉ số của node cha và các node con của nó. – Node gốc ở chỉ số 0 – Node cha của node i có chỉ số (i – 1)/2 – Các node con của node i (nếu có) có chỉ số [2i + 1] và [2i + 2] – Node cuối cùng có con trong 1 Heap có n phần tử là: [n/2 – 1] 4. Thao tác điều chỉnh 1 phần tử (Heapify) 4.1/ Chạy từng bước (Debug) – Tôi sẽ tiến hành Heapify ...

Bài toán tìm kiếm một đối tượng trong dãy đối tượng mà có khóa bằng một khóa cho trước. Binary Search Thuật toán tìm kiếm nhị phân dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó. Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuyến tính nhưng cũng có một số nhược điểm. Tìm kiếm nhị phân có thể chậm hơn bảng băm. Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân. Thao tác này thường tốn nhiều thời gian. Tham khảo thêm tại blog's KienNTT Một số bài tập luyện tập VN.SPOJ.VN http://vn.spoj.com/problems/MOVE12/ http://vn.spoj.com/problems/LEM1/ http://vn.spoj.com/problems/CRUELL2/ http://vn.spoj.com/problems/NDCCARD/ http://vn.spoj.com/problems/TOTALODD/ http://vn.spoj.com/problems/VOPIG/ http://vn.spoj.com/problems/NKSGAME/ http://vn.spoj.com/problems/QBROBOT/ http://vn.s...

Sorting Bài toán: Sắp xếp các phần tử Dạng đơn giản: sắp xếp dãy số theo thứ tự tăng hoặc giảm dần Dạng phức tạp: sx dãy các phần tử theo một tính chất/ thuộc tính nào đó tăng hoặc giảm dần Yêu cầu: Thành thạo 2 phương pháp sắp xếp phổ biến và hiệu quả: SX nổi bọt (Bubble Sort) và SX nhanh (Quicksort).  Đối với các bài toán có kích thước đầu vào <5000 nên dùng pp sx nổi bọt; khi kích thước lớn >=5000 nên dùng Quicksort. Luyện tập trên VN.SPOJ.COM http://vn.spoj.com/problems/BWPOINTS/ http://vn.spoj.com/problems/C11ID/ http://vn.spoj.com/problems/CAR/ http://vn.spoj.com/problems/CBUYING/ http://vn.spoj.com/problems/DHEXP/ http://vn.spoj.com/problems/INSUL/ Luyện tập trên NTU Coders: 1.3.4.6.7.9.11.14.15 1 TILE Chồng gạch 2 CASO Cặp số bằng nhau 3 NHGA Nhà gần nhất 4 VASU Vắt sữa bò 5 SXCHON Sắp xếp chọn 6 CDIE Cắm điện 7 DOANP2 Chiều dài phủ 8 SXNHANH Sắp xếp nhanh 9 KIVU Khiêu ...

Mảng 1 chiều là tập hợp các phần tử có cùng kiểu dữ liệu.   Cú pháp khai báo kiểu type    ten-kieu-mang = array [ ten-kieu-chi-so ] of ten-kieu-phan-tu ; Với:   Ten-kieu-mang: là tên kiểu mảng (đặt theo quy tắc tên trong Pascal)   Ten-kieu-chi-so: phải là kiểu đơn giản, có thứ tự: liệt kê, đoạn con, char, boolean… Ten-kieu-phan-tu: là kiểu của các phẩn tử trong mảng Lưu ý: Lượng bộ nhớ chiếm dụng của một biến mảng trong Free Pascal 32 bit tối đa là 2GB. Ví dụ khai báo mảng: Type       T=Array[1..10000] of Integer; Var       A:T;       B: array[‘A’..’Z’] of Boolean; Một số khai báo đúng: A: array[1..10000] of Integer; B: array[byte] of real; Một số khai báo sai A: array[1.2..3.4] of Char; à Lỗi kiểu chỉ số B: array[Longint] of Longint; à Vượt quá giới hạn 2GB Ví dụ: Ta cần lưu trữ nhiệ...

Kiểu đoạn con (Sub-range Variables) Cú pháp khai báo: var kieu-doan-con : chi-so-duoi ... chi-so-tren ; Ví dụ: var diem : 1 ... 10 ; xeploai : 'A' ... 'D' ; tuoi : 1 ... 100 ; Chương trình ví dụ: program exSubrange ; var diem : 1 .. 10 ; xeploai : 'A' .. 'D' ;   begin    writeln ( ‘Nhap diem (1 - 10): ' );    readln ( diem );       writeln ( 'Nhap xep loai (A - D): ' );    readln ( xeploai );       writeln ( 'Điểm: ' , diem , ' Xếp loại: ' , xeploai ); end . Kiểu liệt kê (Enumerated Variables) Cú pháp khai báo: var var1 , var2 , ...   : kieu-liet-ke ; Ví dụ: type months = ( January , February , March , April , May , June , July , August , September , October , November , December ); Var m : months ; Chương trình ví dụ: program exEnumeration ; type mongiaikhat = ( coffee , tea , milk , water ,...