Image Cover
Avatar

Viblo Algorithm

@algorithm

Report

Pinned Posts

Đây là bài viết số 2 thuộc series bài viết Tham chiếu, Địa chỉ và Con trỏ trong C++ của chuyên đề lập trình C++ cơ bản định hướng thi HSG Tin học.

Để hiểu rõ về bài viết này, các bạn hãy tìm đọc lại các bài viết trước đây trong series này:

  • Địa chỉ ảo, Tham chiếu và Con trỏ.

I. Con trỏ và mảng một chiều

Chúng ta biết rằng chức năng của con trỏ là để lưu trữ một địa chỉ của một vùng nhớ trê...

829
4
2 0

All posts

Thumbnail Image
54
3
0 0
Avatar Viblo Algorithm thg 11 29, 10:42 SA
7 min read

Phương trình Diophantine tuyến tính

I. Giới thiệu chung

Nếu như là một học sinh chuyên Toán, chắc hẳn các bạn đã nghe đến khái niệm Phương trình Diophantine tuyến tính (Linear Diophantine Equation). Đó là phương trình bậc nhất hai ẩn có dạng:

với là các số nguyên cho trước.

Giải phương trình Diophantine tuyến tính là một vấn đề không đơn giản, nó yêu cầu người giải phải có kiến thức khá tốt về Toán học, cũng như một số kiến t...

Thumbnail Image
147
3
1 0
Avatar Viblo Algorithm thg 11 15, 9:45 SA
19 min read

Bài toán cây khung nhỏ nhất

I. Giới thiệu chung

Những giải thuật trên đồ thị luôn luôn là một chủ đề khiến cho chúng ta phải đau đầu, đặc biệt là với những ai đang nghiên cứu về chủ đề Cấu trúc dữ liệu & Giải thuật. Một trong số những bài toán kinh điển của chủ đề Đồ thị là Bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree). Đây là một bài toán có lịch sử lâu đờ...

Thumbnail Image
208
1
0 0
Avatar Viblo Algorithm thg 10 28, 7:00 SA
19 min read

Xác suất (Phần 2)

Đây là bài viết thứ 2 trong series bài viết về Xác suất trong lập trình thi đấu. Trước khi đọc bài viết này, các bạn cần nắm vững các kiến thức cơ bản về Xác suất. Hãy tìm đọc lại bài viết thứ nhất của series tại đây.

Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu một số kiến thức nâng cao của Xác suất có ứng dụng trong Lập trình thi đấu!

III. Một số kiến thức nâng cao

  1. Biến ngẫu nhiên ...
Thumbnail Image
200
3
1 0
Avatar Viblo Algorithm thg 10 21, 3:00 SA
13 min read

Quy hoạch động trên cây

I. Giới thiệu

Quy hoạch động trên cây (), là một dạng bài quy hoạch động đặc biệt, sử dụng để giải các bài toán quy hoạch động trên đồ thị có dạng cây. Ở dạng bài này, thường sẽ phải tìm công thức truy hồi cho các nút trên cây dựa vào các nút con của nó. Khi đặt hàm mục tiêu, thường sẽ xuất hiện 1ii1ii. Dạng bài này giống với quy hoạch động thông thường, khi chúng ta cần xác định cấu trúc con t...

Thumbnail Image
647
2
2 0
Avatar Viblo Algorithm thg 9 27, 7:49 SA
16 min read

Queue và Bài toán loang trên ma trận

I. Giới thiệu chung

Trong các chuyên đề trước, tôi đã giới thiệu tới các bạn về hai cấu trúc dữ liệu ngăn xếp và hàng đợi, cùng với đó là kĩ thuật stack đơn điệu - một kĩ thuật ứng dụng của ngăn xếp. Cũng tương tự, hàng đợi sẽ có những ứng dụng riêng của nó. Trong chuyên đề này, tôi sẽ giới thiệu một bài toán ứng dụng cực kỳ quen thuộc ...

Thumbnail Image
254
1
0 0
Avatar Viblo Algorithm thg 9 20, 9:10 SA
5 min read

Duyệt phân đôi tập hợp (Meet In The Middle)

I. Giới thiệu chung

  1. Phát biểu bài toán

Trong các kì thi lập trình, những bài toán liên quan tới duyệt toàn bộ nghiệm không hề hiếm. Đôi khi, chúng ta sẽ gặp phải những bài toán mà bắt buộc phải duyệt toàn bộ các cấu hình nghiệm để tìm ra các nghiệm thỏa mãn yêu cầu đề bài. Cùng xét một bài toán ví dụ sau:

Cho một tập hợp gồm phần tử . Hãy xác định có bao nhiêu tập hợp con của tập có tổ...

Thumbnail Image
721
5
1 0
Avatar Viblo Algorithm thg 9 6, 8:00 SA
15 min read

Rời rạc hóa (Nén số)

I. Giới thiệu chung

Trong lập trình thi đấu hoặc trong môn Toán, có thể các bạn đã được nghe nhiều tới khái niệm Rời rạc hóa. Ở lĩnh vực Toán học ứng dụng và Khoa học máy tính, Rời rạc hóa là quá trình chuyển các hàm, mô hình, biến hay phương trình thành các đối số rời rạc, giúp cho dữ liệu trở nên phù hợp trong việc đánh giá và thao tác trên máy tính. Bản chất của phương pháp có thể hiểu nôm ...

Thumbnail Image
1.1K
6
4 3
Avatar Viblo Algorithm thg 8 17, 8:00 SA
14 min read

Two Pointers

I. Tổng quan về kĩ thuật Two Pointers

Trong lập trình nói chung và lập trình thi đấu nói riêng, kĩ thuật hai con trỏ (two pointers) là một kĩ thuật rất hiệu quả để giải quyết các bài toán trên mảng hoặc chuỗi. Kĩ thuật này giúp tiết kiệm không gian lưu trữ, giảm thời gian chạy của giải thuật rất hiệu quả.

Vậy kĩ thuật hai con trỏ là gì? Đúng như tên gọi của nó, kĩ thuật này sử dụng hai con tr...

Thumbnail Image
227
3
0 0
Avatar Viblo Algorithm thg 8 2, 8:30 SA
15 min read

Kĩ thuật stack đơn điệu

I. Giới thiệu chung

Trong các chuyên đề trước, tôi đã giới thiệu tới các bạn rất chi tiết về ngăn xếp và hàng đợi, cũng như cách cài đặt và sử dụng chúng trong lập trình. Tuy nhiên, các bài tập vẫn chỉ ở mức độ rất cơ bản, chưa có tính đặc trưng của cấu trúc dữ liệu. Trong chuyên đề này, chúng ta sẽ cùng thảo luận về một ứng dụng cực ky...

Thumbnail Image
792
4
1 0
Avatar Viblo Algorithm thg 7 18, 9:30 SA
5 min read

Quy hoạch động 7.6: Top-down và Bottom-up

I. Giới thiệu chung

Ta đã biết rằng, giải pháp chúng ta thường sử dụng để giải một bài toán có bản chất đệ quy mà tồn tại các bài toán con gối nhau và cấu trúc con tối ưu là Quy hoạch động. Thông thường, khi cài đặt các bài toán quy hoạch động, chúng ta hay quen với việc đi từ những bài toán nhỏ, dần dần tiến lên tính toán các bài toán lớn hơn dựa vào công thức truy hồi. Cách cài đặt đó được g...

Thumbnail Image
361
3
2 1
Avatar Viblo Algorithm thg 6 28, 7:03 SA
16 min read

Xác suất (Phần 1)

I. Mở đầu

Xác suất và Thống kê là một nhánh của Toán học, có rất nhiều ứng dụng trong thực tế, đặc biệt là trong việc phân tích dữ liệu. Xác suất và Thống kê xuất hiện trong mọi lĩnh vực, nhờ vào đó mà giúp các doanh nghiệp đưa ra chiến lược kinh doanh, giúp con người dự báo thời tiết,...Chính vì vậy, những bài toán liên quan tới xác suất ít nhiều đều được lấy từ những ví dụ thực tế. Nếu các b...

Thumbnail Image
583
3
1 0
Avatar Viblo Algorithm thg 6 13, 8:00 SA
6 min read

Sắp xếp với thời gian tuyến tính

Mở đầu

Ta đã làm quen với rất nhiều thuật toán sắp xếp. Độ phức tạp trung bình nhanh nhất trong các thuật toán sắp xếp là . Bạn có bao giờ tự hỏi rằng, ta có thể sắp xếp một mảng với độ phức tạp thời gian tuyến tính không 😄

Giải pháp

Counting sort

Nếu một mảng bao gồm số nguyên với phạm vi nhỏ (Ví dụ như tuổi thọ của một người chẳng hạn 😄). Ta có thể sử dụng thuật toán Counting Sort. ...

Thumbnail Image
1.5K
4
1 0
Avatar Viblo Algorithm thg 5 31, 9:48 SA
13 min read

Quy hoạch động 7.4: Palindromes và Các bài toán QHĐ liên quan

I. Những bài toán cơ sở

Trong Lập trình thi đấu, xâu palindrome (xâu đối xứng) là một loại xâu kí tự đặc biệt. Đó là những xâu mà viết xuôi hay viết ngược đều giống nhau, chẳng hạn như ABBA hay TOEICCIEOT,...Nhờ tính chất đặc biệt này, người ta phát triển ra rất nhiều bài toán liên quan tới xâu palindrome, không chỉ ở trong xâu kí tự mà còn có th...

Thumbnail Image
633
3
3 0
Avatar Viblo Algorithm thg 5 17, 10:08 SA
17 min read

Giải thuật Tìm kiếm nhị phân nâng cao

I. Bài toán Tìm kiếm nhị phân tổng quát

Ở bài viết trước, mình đã giới thiệu tới các bạn những khái niệm cơ bản nhất về bài toán tìm kiếm trong Tin học, cũng như giới thiệu về hai giải thuật Tìm kiếm tuần tự và Tìm kiếm nhị phân. Trong bài viết này, mình sẽ tập trung nói về giải thuật Tìm kiếm nhị phân, nhưng sẽ là áp dụng trong một lớp ...

Thumbnail Image
2.0K
3
0 0
Avatar Viblo Algorithm thg 5 3, 8:00 SA
13 min read

Thuật toán Đường quét (Sweep line algorithm)

I. Giới thiệu

Trong hình học tính toán, việc xét các điểm trên một mặt phẳng là bài toán thường xuyên xảy ra. Tuy nhiên, với dữ liệu lớn trong các bài toán Lập trình thi đấu, việc quét qua tất cả mọi điểm trên mặt phẳng dường như là bất khả thi, chính vì thế ta sẽ chỉ xét tới một số điểm cần thiết mà thôi.

Thuật toán đường quét (Sweep line algorithm) được xây dựng dựa trên tư tưởng nói trên. ...

Thumbnail Image
2.0K
4
0 0
Avatar Viblo Algorithm thg 4 16, 9:00 SA
17 min read

Các thuật toán tìm Bao lồi (Convex hull)

Để hiểu được nội dung trong bài viết này, các bạn cần nắm vững các kiến thức về Hình học tính toán cơ bản. Các bạn có thể xem lại hai bài viết này tại các link dưới đây:

  • Những vấn đề cơ bản về Vector.
  • Sự giao nhau của các đường thẳng và Tính toán diện tích.

I. Định nghĩa Bao lồi

Bao lồi là một vấn đề rất thường xuyên xuất hiện trong các bài tập hình học tính toán của lập trình thi đấu. ...

Thumbnail Image
628
2
1 0
Avatar Viblo Algorithm thg 3 27, 10:17 SA
8 min read

Trie Tree (phần 2) - Trie nhị phân

Đây là bài viết số 2121 liên quan tới Trie Tree cơ bản tại đây: Trie Tree phần 1.

I. Giới thiệu chung

Ta đã biết rằng Trie là một cấu trúc dữ liệu dạng cây, sử dụng rất hiệu quả trong các bài toán liên quan tới quản lý danh sách xâu kí tự. Tuy nhiên, ít ai biết rằng Trie Tree còn có một ứng dụng nữa, đó là quản lý một tập số nguyên.

Bằng cách coi mỗi số là một xâu kí tự gồm toàn kí tự 0 và 1...

Thumbnail Image
2.9K
3
0 0
Avatar Viblo Algorithm thg 3 22, 9:00 SA
14 min read

Trie Tree (phần 1) - Xử lý xâu kí tự

I. Giới thiệu chung

Trie là một cấu trúc dữ liệu dạng cây, hay còn gọi là Cây tiền tố (Suffix tree). Đây là một cấu trúc dữ liệu hữu ích sử dụng để quản lý một tập hợp các xâu kí tự, và có thể mở rộng ra các bài toán liên quan tới quản lý tập số nguyên (xem phần 2 của bài viết tại đây).

Cấu trúc của Trie rất đơn giản, nó là một cây kiểm soát các kí tự của một xâu trên từng cạnh, cho phép lưu ...

Thumbnail Image
1.4K
10
3 1
Avatar Viblo Algorithm thg 2 21, 8:00 SA
26 min read

Bài toán đường đi ngắn nhất (phần 2) - Thuật toán Dijkstra và Ford Bellman

Đây là bài viết số 2 trong series bài viết về Bài toán đường đi ngắn nhất trên đồ thị. Để theo dõi lại phần 1 của series, các bạn hãy nhấn vào đây.

I. Tổng quan

  1. Phát biểu bài toán

Ta đã biết về thuật toán Floyd - Warshall trong bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trước...

Thumbnail Image
929
4
0 0
Avatar Viblo Algorithm thg 1 30, 8:00 SA
5 min read

Số học đồng dư (Phần 2): Phương trình đồng dư tuyến tính

Trong bài viết này, chúng ta sẽ cùng thảo luận về phương pháp giải của phương trình đồng dư tuyến tính - một dạng phương trình khá quen thuộc trong số học đồng dư nhưng lại không được đề cập trong chương trình Toán cấp THCS - THPT. Đó là phương trình có dạng:

Mặc dù chỉ phổ biến trong các chuyên đề HSG Toán, nhưng trong Tin học thì phương trình này lại khá thú vị và có thể áp dụng để giải quyế...

Viblo
Let's register a Viblo Account to get more interesting posts.