Bài tập 09/05/2016


Luyện tập trên NTU Coder. Tham khảo lý thuyết: cuốn Kỹ thuật thiết kế thuật toán của Lê Minh Hoàng.

Bài tập:
  1. Hiệu số
  2. Dãy con tăng dài nhất


Comments

Post a Comment

Popular posts from this blog

Hướng dẫn cách Debug trong Free Pascal

Image
Trong quá trình lập trình, chắc hẳn trong chúng ta ai cũng sẽ không tránh được các lỗi trong chương trình của mình (lỗi cú pháp, lỗi thuật toán, . . . ). Nhưng máy tính thì thực hiện những đoạn chương trình của chúng ta rất nhanh có thể là trong vài giây thậm chí vài mili giây. Vậy thì làm sao chúng ta có thể phát hiện ra những dòng code lỗi trong hàng trăm, hàng nghìn dòng code mà ta đã viết ??? Rất may mắn là trong hầu hết các IDE của các ngôn ngữ lập trình đều hỗ trợ một chức năng rất hay được gọi là Debug, bạn có thể gọi là “bắt bọ” hay chạy từng bước đều được  :)  . Trong bài viết này, tôi sẽ hướng dẫn các bạn làm thế nào để Debug trong IDE Free Pascal. Để Debug được thì bạn cần nắm một số thuật ngữ cơ bản sau : Debug : bắt lỗi, “dò bọ”, “bắt bọ”. Watch : nơi bạn xem sự thay đổi giá trị của các biến. BreakPoint : điểm (dòng) mà bạn sẽ bắt IDE dừng ở đó để bạn xem trạng thái hiện tại của chương trình hay giá trị của các biến. Để bắt đầu quá trình Debug thì...
Read more

Bài toán dãy tìm con liên tiếp

Image
Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể. Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể. Bài toán tổng quát : ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó. Cách giải quyết : Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất. Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuậ...
Read more

Heap Sort

Image
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 ...
Read more