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
28.3K
13
5 4
Avatar Viblo Algorithm Dec 20th, 2021 6:13 a.m.
11 min read

Đếm ước của một số trong O(N^1/3)

I. Đặt vấn đề

Chắc hẳn, ai trong chúng ta cũng đã quá quen thuộc với bài toán đếm số ước nguyên dương của . Giải thuật thông thường nhất mà mọi người thường sử dụng là giải thuật dựa trên một nhận định rằng nếu như số có một ước là thì nó cũng sẽ có một ước nữa là . Bằng phương pháp này, chúng ta có thể giải quyết mọi bài toán với giới hạn khoảng 101510^{15} trở xuống (Các bạn xem lại trong ...

Thumbnail Image
36.3K
4
2 0
Avatar Viblo Algorithm Dec 13th, 2021 7:39 a.m.
8 min read

Lũy thừa ma trận

Trong bài viết này, chúng ta cùng thảo luận về một dạng đặc biệt của ma trận đó là ma trận vuông, cùng với đó là một thao tác tính toán cơ bản nhưng rất quan trọng trên ma trận đó là lũy thừa ma trận.

Một số định nghĩa và ví dụ

Trước khi bắt đầu thảo luận về lũy thừa của ma trận, ta cần làm rõ một số khái niệm sau:

  • Ma trận vuông là ma trận có số hàng bằng số cột.
  • Với ma trận vuông , ta c...
Thumbnail Image
2.5K
5
0 0
Avatar Viblo Algorithm Dec 8th, 2021 7:50 a.m.
7 min read

Tối ưu cách tính tích của chuỗi ma trận

Ma trận là một khái niệm rất cơ bản trong toán học nhưng nó lại có vai trò to lớn trong nhiều lĩnh vực và đóng góp nhiều ứng dụng thực tế. Trong lập trình thi đấu, việc thao tác tính toán trên ma trận với các bài toán hay và khó là điều không thể tránh khỏi. Đôi khi chỉ là những thao tác rất cơ bản như nhân ma trận cũng cần phải tối ưu một cách triệt để. Trong bài viết này, mình sẽ trình bày mộ...

Thumbnail Image
596
3
1 0
Avatar Viblo Algorithm Dec 6th, 2021 7:47 a.m.
11 min read

Giới thiệu về lý thuyết trò chơi (phần 4)

Trong bài viết này mình sẽ giới thiệu về trò chơi liên quan tới sự hợp tác (Cooperative games) Khác với 3 loại trò chơi mà mình giới thiệu trong các bài viết trước cần có sự cạnh tranh giữa các người chơi để tối ưu phần thưởng cho từng cá nhân. Trong trò chơi có sự hợp tác, trọng tâm ở đây là cần kết hợp lại với nhau để thu được phần thưởng lớn nhất cho các bên. Cụ thể hãy xem các ví dụ bên dướ...

Thumbnail Image
765
8
3 1
Avatar Viblo Algorithm Dec 1st, 2021 9:17 a.m.
12 min read

Giới thiệu về lý thuyết trò chơi (phần 3)

Trong hai phần đầu của chuỗi bài viết giới thiệu lý thuyết trò chơi, mình đã trình bày ví dụ về 2 loại trò chơi đó là Zero-Sum Games và Nonzero-Sum Games. Đây là những trò chơi mà người chơi chỉ được chọn duy nhất 1 lần, độc lập và cùng lúc với người chơi còn lại. Trong các trò chơi bắt nguồn từ các tình huống kinh tế hoặc chính trị ngoài đời thực, điều này thường không xảy ra. Người chơi có th...

Thumbnail Image
732
4
2 0
Avatar Viblo Algorithm Nov 29th, 2021 6:58 a.m.
8 min read

Giới thiệu về lý thuyết trò chơi (phần 2)

Trong bài viết trước, mình đã giới thiệu cho các bạn về lý thuyết trò chơi và hai ví dụ kinh điển trong Zero-Sum Games. Trong bài viết này, mình sẽ tiếp tục trình bày các ví dụ về loại trò chơi khác đó là Nonzero-Sum Games.

Nonzero-Sum Games

Bài toán hai tù nhân

Bài toán như sau, hai tù nhân (người chơi 1 và 2) phạm tội cùng nhau và bị thẩm vấn riêng. Mỗi tù nhân chỉ có hai lựa chọn: Anh ta ...

Thumbnail Image
2.2K
4
2 0
Avatar Viblo Algorithm Nov 26th, 2021 7:52 a.m.
11 min read

Giới thiệu về lý thuyết trò chơi (phần 1)

Thời gian gần đây nổi lên một bộ phim rất nổi tiếng của Hàn Quốc là Squid Game. Bộ phim đang là cơn sốt trên toàn thế giới, ắt hẳn bạn cũng là người đã xem bộ phim đó chứ 😃 Đã chơi game thì ai cũng muốn dành chiến thắng 😄 Tất nhiên, trong bất cứ game nào cũng vậy, luôn có những tips và tricks để bạn gia tăng khả năng thắng trò chơi. Trong lập trình thi đấu, vấn đề về các trò chơi được khai th...

Thumbnail Image
3.3K
2
2 0
Avatar Viblo Algorithm Nov 24th, 2021 8:15 a.m.
13 min read

Một số ứng dụng nâng cao của cây DFS (phần 2)

III. Bài toán tìm thành phần liên thông mạnh - giải thuật Tarjan

  1. Định nghĩa thành phần liên thông mạnh

Đối với đồ thị có hướng, ta có ba định nghĩa về tính liên thông:

  • được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt , ta có đến được và đến được .
  • được gọi là liên thông yếu (weakly connected) nếu như đồ thị vô hướng nền của nó là liên thông (tức là ...
Thumbnail Image
3.0K
6
4 0
Avatar Viblo Algorithm Nov 22nd, 2021 6:00 a.m.
9 min read

Một số ứng dụng nâng cao của cây DFS (phần 1)

I. Cây DFS và bài toán định chiều đồ thị

  1. Phân loại các cung trên cây

Trong quá trình duyệt đồ thị, với mỗi đỉnh ta có được đỉnh là đỉnh cha của đỉnh trên đường đi. Nếu xây dựng đồ thị con gồm các cạnh có dạng ta sẽ thu được một cây, gọi là cây . Hình vẽ dưới đây biểu diễn một cây với 9DFSDFS9\text{DFS}\text{DFS}.

Trên đồ thị có hướng, xét mọi...

Thumbnail Image
2.3K
8
3 0
Avatar Viblo Algorithm Nov 15th, 2021 8:06 a.m.
14 min read

Cây tìm kiếm nhị phân

Như mình đã trình bày trong bài viết trước, tìm kiếm nhị phân trên một mảng thể hiện sự hiệu quả. Tuy nhiên, hiệu suất của việc tìm kiếm trên mảng bị giảm đi rất nhiều khi dữ liệu trong tập dữ liệu thay đổi thường xuyên. Với tập dữ liệu động, ta phải áp dụng cấu trúc dữ liệu khác để duy trì hiệu suất tìm kiếm ở mức chấp nhận được.

Cây tìm kiếm là cấu trúc dữ liệu phổ biến nhất được sử dụng để ...

Thumbnail Image
4.9K
8
2 0
Avatar Viblo Algorithm Nov 12th, 2021 7:27 a.m.
9 min read

Giới thiệu thuật toán tìm kiếm nhị phân

Tìm kiếm nhị phân là một thuật toán cơ bản trong khoa học máy tính. Thay vì tìm kiếm một phần tử trong mảng một cách tuyến tính duyệt từng phần tử, tìm kiếm nhị phân cho ta cách tìm kiếm tối ưu hơn bằng cách sắp xếp các phần tử trước khi truy vấn. Cụ thể như nào các bạn hãy theo dõi bài viết nhé 😄

Phân tích thuật toán

Đặt vấn đề

Hãy thử tưởng tượng bạn đang cần tìm một từ trong cuốn sách từ...

Thumbnail Image
5.9K
9
1 0
Avatar Viblo Algorithm Nov 10th, 2021 8:48 a.m.
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
8.1K
6
3 1
Avatar Viblo Algorithm Nov 8th, 2021 8:27 a.m.
7 min read

Một số dãy số đặc biệt (Fibonacci, Catalan, Euler)

I. Dãy Fibonaci

Dãy số Fibonaci được xác định bởi công thức sau:

Một số phần tử đầu tiên của dãy Fibonaci là: 0,1,1,2,3,5,8N0, 1, 1, 2, 3, 5, 8N còn có thể tính bằng công thức tổng quát:

Dãy Fibonaci là đáp án của một số bài toán dưới đây:

  1. Bài toán cổ về các cặp thỏ

Phát biểu bài toán:

  • Ban đầu chỉ có một cặp thỏ được sinh ra.
  • Hai tháng sau khi ra đời, mỗi cặp thỏ sẽ sinh ra một cặp thỏ con mới....
Thumbnail Image
24.4K
7
3 2
Avatar Viblo Algorithm Nov 5th, 2021 7:09 a.m.
8 min read

Thuật toán Floyd-Warshall

Giới thiệu

Khi nhắc đến thuật toán để tìm đường đi ngắn nhất trong đồ thị, người ta sẽ thường nghĩ tới những thuật toán dễ tiếp cận và có thể chạy trong giới hạn cho phép như Breadth First Search, Dijkstra hay Bellman-Ford. Tuy nhiên, ba thuật toán trên đều chỉ có thể tìm được đường đi ngắn nhất từ một đỉnh nguồn nhất định đến các đỉnh khác và do đó, trong một số trường hợp cụ thể cần chỉ ra đ...

Thumbnail Image
31.5K
12
7 1
Avatar Viblo Algorithm Nov 3rd, 2021 7:31 a.m.
11 min read

Thuật toán Dijkstra và ứng dụng

Tổng quan

Các bài toán về tìm đường đi ngắn nhất và biến tướng của nó luôn xuất hiện rất nhiều trong các cuộc thi lập trình thi đấu bởi sự đa dạng trong cách đưa ra đề bài và sử dụng. Một trong những thuật toán tìm đường đi ngắn nhất được sử dụng phổ biến đó là thuật toán Dijkstra.

Theo Wikipedia, thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm $19...

Thumbnail Image
5.8K
17
5 0
Avatar Viblo Algorithm Nov 1st, 2021 7:49 a.m.
21 min read

Nhập môn Quy hoạch động

I. Mở đầu

Trong những bài viết trước, các bạn đã được giới thiệu tuần tự những chiến lược giải thuật từ đơn giản tới nâng cao, như đệ quy, quay lui, nhánh cận, tham lam,...Những chiến lược nói trên thực ra sẽ không xuất hiện quá nhiều trong những cuộc thi lập trình, và cũng không phải là cách hay để giải quyết bài toán, vì nhiều lí do:

  • Tro...
Thumbnail Image
2.0K
4
2 0
Avatar Viblo Algorithm Oct 29th, 2021 3:39 a.m.
12 min read

Công thức Toán học và Tính chất số học đặc biệt (phần 2)

Đây là bài viết thứ hai trong series bài viết về Công thức Toán học và Tính chất số học đặc biệt trong Lập trình thi đấu. Để xem lại bài viết trước, các bạn có thể nhấn vào đây.

V. Một số đẳng thức đáng lưu ý

Qua quá trình nghiên cứu và đúc kết từ các kỳ thi HSG Tin học các cấp và kinh nghiệm...

Thumbnail Image
4.4K
7
1 0
Avatar Viblo Algorithm Oct 27th, 2021 1:46 a.m.
14 min read

Lý thuyết Tập hợp

I. Mở đầu về Toán học tổ hợp

Toán tổ hợp là một chuyên đề lớn và có tính ứng dụng cao trong lập trình thi đấu, đặc biệt trong các bài toán đếm. Chuyên đề Toán học tổ hợp trong Tin học sẽ đề cập tới những vấn đề cơ bản và quan trọng nhất của Toán tổ hợp gắn liền với những bài toán của nó trong lập trình thi đấu. Nắm vững Toán học tổ hợp sẽ giúp cho các bạn có năng lực giải được nhiều bài toán k...

Thumbnail Image
7.5K
9
4 0
Avatar Viblo Algorithm Oct 25th, 2021 8:05 a.m.
12 min read

Chia để trị (Divide and Conquer)

I. Sơ lược về giải thuật Chia để trị

Chia để trị (Divide and Conquer) là một trong các thiết kế giải thuật rất phổ biến thường được sử dụng trong những bài toán có kích thước lớn. Trong lập trình thi đấu, chúng ta thường nghe đến chiến lược này gắn liền cùng với những thuật toán như Sắp xếp nhanh (Quicksort), Sắp xếp trộn (Mergesort),..., hay thuật toán lũy thừa . Tuy nhiên, đó chỉ là bề nổi c...

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