Viblo Algorithm

I. Cấu trúc dữ liệu Heap

Để thuận tiện, mình sẽ nhắc lại những khái niệm cơ bản về Heap và một số thao tác Heap cung cấp. Heap là một cấu trúc dữ liệu dạng cây, trong đó các nút trên cây được sắp xếp theo một thứ tự ràng buộc nhất định giữa khóa của nút cha và khóa của nút con (thường là nút cha nhỏ hơn hoặc lớn hơn nút con). Nút ở gốc của Heap luôn luôn là nút có mức ưu tiên cao nhất, nghĩa l...

Đây là phần 2 của series bài viết về Xử lý số nguyên lớn trong C++. Trước khi đọc bài này, các bạn cần biết cách biểu diễn số nguyên lớn, cũng như các phép toán so sánh, cộng, trừ số lớn. Nếu như chưa nắm vững, các bạn hãy tìm đọc lại tại đây.

Trong bài viết có sử dụng lại một ...

I. Mở đầu về số nguyên lớn trong lập trình

Chúng ta đều biết rằng, việc giải bài toán bằng máy tính nói chung và lập trình thi đấu nói riêng luôn luôn đối mặt với dữ liệu có kích thước rất lớn. Hiển nhiên là vì những dữ liệu quá lớn vượt ra ngoài khả năng tính toán của con người, nên mới cần tới sự trợ giúp của máy tính.

Với sự nâng cấp liên tục của máy tính điện tử, độ lớn dữ liệu mà máy tín...

I. Mở đầu

Chúng ta đã biết về một số thuật toán sắp xếp quen thuộc như Bubble sort (sắp xếp nổi bọt), Quick sort (sắp xếp nhanh), Heap sort (sắp xếp vun đống), Counting sort (sắp xếp đếm phân phối), ... Ngoài những thuộc toán trên, chúng ta có có một vài giải thuật sắp xếp ít "quen thuộc" hơn, có lẽ sẽ có nhiều bạn còn khá lạ lẫm với chúng. Chúng lần lượt là:

• Insertion Sort - sắp xếp chèn -...

I. Kiểu dữ liệu Heap trong C++

1. Biểu diễn dưới dạng cây nhị phân

Để làm quen về kiểu dữ liệu Heap, chúng ta có thể biểu diễn kiểu dữ liệu Heap theo một cây nhị phân. Ta có thể biểu diễn theo hai kiểu như sau:

Kiểu 1 (Max-Heap): Các nút cha luôn có giá trị lớn hơn các nút con

Kiểu 2 (Min-Heap): Các nút cha luôn có giá trị nhỏ hơn các nút con

Xét kiểu biểu diễn thứ hai, quan sát cây nhị phâ...

Nếu đã từng tham gia các cuộc thi lập trình thi đấu như ACM ICPC, Google Code Jam, Facebook Hacker Cup,... hay là trải qua những kì thi chọn học sinh giỏi tin các cấp, kiểu gì thì kiểu, các bạn đều gặp phải ít nhất một bài toán sử dụng kĩ thuật quy hoạch động. Hồi năm nhất mình có tham gia cuộc thi ICPC của trường. Mình và hai "chiến hữu" gặp phải một bài toán chắc chắn rằng solution là chuẩn r...

I. Unordered_map

1. Đặt vấn đề Như chúng ta đã biết, dùng để lưu trữ dữ liệu dưới dạng key - value, và các dữ liệu của chúng ta được tự động sắp xếp theo thứ tự. Về cơ bản thì sử dụng cây nhị phân BST: red-black tree (cây tìm kiếm nhị phân tự cân bằng). Ngoài ra, nếu các bạn tìm hiểu sâu hơn về kiểu dữ liệu này sẽ phát hiện còn có thêm một kiểu dữ liệu với cái tên khá tương đồng: . Qua tên th...

I. Kiểu dữ liệu Set trong C++

1. Khái niệm kiểu dữ liệu set là một dạng cấu trúc dữ liệu dùng để lưu trữ các phần tử không trùng lặp và được sắp xếp theo thứ tự tăng dần hoặc giảm dần. (Mặc định trong là tăng dần và chúng ta có thể viết lại hàm so sánh theo mục đích của chúng ta)

Trong môn Toán lớp $6setset$ còn có tính tự sắp xếp các phần tử (Có thể rút gọn một số công đoạn sắp xếp của bài ...

I. Lời mở đầu

Ngăn xếp (Stack) và Hàng đợi (Queue) là hai trong số những cấu trúc dữ liệu cực kỳ quan trọng, được sử dụng thường xuyên trong thiết kế thuật toán. Chính máy tính cũng sử dụng nhiều ứng dụng của ngăn xếp (chẳng hạn như việc quản lý bộ nhớ trong khi thi hành chương trình, hay lưu trữ các lời gọi đệ quy,...). Về bản chất, ngăn xê...

I. Từ Quy nạp Toán học...

Trước tiên, cùng xem xét bài toán chứng minh sau: Chứng minh đẳng thức dưới đây đúng với mọi 1+3+5+\cdots+(2n - 1) = n^2 \ (1)

Ở bậc trung học cơ sở, ta đã biết về phương pháp quy nạp toán học dùng để chứng minh một đẳng thức hoặc bất đẳng thức đúng. Áp dụng phương pháp này, ta có thể giải quyết bài toán trên một cách dễ dàng:

• Bước $1n = 1$: Ta thấy $1 = 1^2,n = ...

I. Giới thiệu chung

Trong Toán học, hệ cơ số (hay hệ đếm) là một hệ thống các kí hiệu toán học và quy tắc sử dụng tập kí hiệu đó để biểu diễn số đếm. Các kí hiệu toán học có thể là chữ số hoặc các kí tự chữ cái. Cần phân biệt giữa Hệ cơ số và Cơ số (số lượng kí hiệu sử dụng trong một hệ cơ số).

Có rất nhiều hệ cơ số khác nhau, mỗi hệ cơ số có những quy tắc biểu diễn số khác nhau. Những dãy kí...

I. Số nguyên tố và Hợp số

1. Giới thiệu

Số nguyên tố là số nguyên dương lớn hơn $11$ và chính nó.

Hợp số, là các số nguyên dương lớn hơn $1$ và có nhiều hơn hai ước.

Lấy ví dụ: $515101, 2, 510$. Số nguyên tố và các vấn đề xoay quanh nó luôn là một chủ đề được yêu thích trong Toán học nói chung và lập trình thi đấu nói riêng.

2. Kiểm tra tính nguyên tố của một số

2.1. Giải thuật cơ sở

Ý t...

Trong chuyên đề này, chúng ta sẽ cùng nghiên cứu về hai kĩ thuật khá quen thuộc và có tính ứng dụng cao trong các bài toán số học, đó là Phép nhân Ấn Độ và Thuật toán bình phương và nhân - những kĩ thuật sẽ giúp các bạn tính toán và trong thời gian . Mặc dù nghe có vẻ khá vô dụng (bởi vì thực ra phép nhân chỉ cần thực hiện trực tiếp), ...

I. Phép đồng dư thức cơ bản

Đồng dư thức là phép toán lấy số dư của số này khi chia cho số khác, kí hiệu là . Ví dụ: $5 \% 2=15 \equiv 1(mod2)$.

Phép đồng dư thức có tính chất phân phối đối với phép cộng, phép nhân và phép trừ, cụ thể như sau:

•      .
  

•      .
  

•      .
  

Riêng đối với phép chia, chúng ta không có tính chất phân phối, mà phải sử dụng một lí thuyết là Nghịch đảo mo...

I. Tìm các ước của một số nguyên dương

1. Giải thuật ngây thơ

Để tìm tất cả các ước nguyên dương của một số nguyên dương phương pháp dễ nhất là sử dụng một vòng lặp, duyệt qua toàn bộ các giá trị từ $1N,NN$.

Cài đặt

Dưới đây là cài đặt đếm số lượng ước nguyên dương của một số nguyên dương :

Dễ dàng nhận thấy giải thuật có độ phức tạp nếu như có giá trị khoảng $10^81$s. Ta cần một giải t...

I. Thuật toán và những tính chất của thuật toán

1. Khái niệm

Thuật toán - hay còn gọi là giải thuật - là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 2500 TCN. Khái niệm về thuật toán có thể phát biểu như sau:

Thuật toán là một dãy hữu hạn các b...

I. Giới thiệu về STL STL (Standard Template Library) là một thư viện template (lập trình theo mẫu) cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của ngôn ngữ lập trình C. Với khái niệm template, những người lập trình đã đề ra khái niệm lập trình khái lược (generic programming), C++ được cung cấp kèm với bộ thư viện chuẩn ...

I. Ý tưởng thuật toán Chúng ta hãy cùng xem xét tình huống sau: Trong giờ Toán tại lớp $1A$, thầy giáo viết lên bảng một dãy số như sau:

$4, 2, 2, 8, 3, 3, 1, 2$

Thầy giáo yêu cầu cả lớp hãy sắp xếp dãy số trên theo thứ tự không giảm từ trái qua phải. Cả lớp đều đang loay hoay vì trong bài toán lần này mỗi số không phải chỉ xuất hiện $1$ lần duy nhất như bình thường mà có thể lặp lại. An là m...

I. Làm quen với thuật toán So với thuật toán sắp xếp nổi bọt (bubble sort) thì thuật toán sắp xếp nhanh có tốc độ nhanh hơn. Thay vì đi theo sắp xếp từng cặp như bubble sort, chúng ta có thể chia dữ liệu ra thành $2$ danh sách, rồi so sánh từng phần tử của danh sách với một phần tử được chọn (gọi là phần tử chốt) và mục đích của chúng ta là đưa phần tử chốt về đúng vị trí của nó.

II. Miêu tả t...

I. Bài toán sắp xếp

Sắp xếp là một khái niệm mà chúng ta dễ dàng gặp trong cuộc sống cũng như trong công việc. Cùng lấy một vài ví dụ:

• Sắp xếp lại đồ đạc trong phòng, trong nhà.
• Sắp xếp các tài liệu trong tủ sách theo thứ tự.
• Sắp xếp công việc cho anh em trong công ty.

Trong Tin học, việc sắp xếp luôn luôn diễn ra không ngừng mà đôi khi chúng ta không nhận ra. Chẳng hạn, trong mỗi fold...