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ê...

506
4
1 0

All posts

Thumbnail Image
5.6K
6
2 1
Avatar Viblo Algorithm thg 11 8, 2021 8:27 SA
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
20.0K
7
3 2
Avatar Viblo Algorithm thg 11 5, 2021 7:09 SA
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
20.1K
13
5 1
Avatar Viblo Algorithm thg 11 3, 2021 7:31 SA
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
4.5K
13
3 0
Avatar Viblo Algorithm thg 11 1, 2021 7:49 SA
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
1.7K
4
1 0
Avatar Viblo Algorithm thg 10 29, 2021 3:39 SA
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
2.6K
7
1 0
Avatar Viblo Algorithm thg 10 27, 2021 1:46 SA
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
6.2K
9
4 0
Avatar Viblo Algorithm thg 10 25, 2021 8:05 SA
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...

Thumbnail Image
6.1K
12
3 1
Avatar Viblo Algorithm thg 10 18, 2021 8:44 SA
21 min read

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

I. Lời mở đầu

Xét bài toán sau đây: Tính giá trị biểu thức:

Đối với những ai đã tiếp cận với ngôn ngữ lập trình, hẳn ban đầu sẽ thấy bài toán này rất đơn giản. Chỉ cần chạy một vòng lặp biến với từ 1N,N109,1N1N,N10^9,1N sẽ khiến cho thời gian thực thi chương trình không đảm bảo.

Vậy giải pháp là gì? Lúc này những bạn học sinh nào có nền tảng toán chắc chắn sẽ biết ngay công thức tổng quát của là ...

Thumbnail Image
2.9K
7
2 0
Avatar Viblo Algorithm thg 10 15, 2021 7:53 SA
7 min read

Sắp xếp vun đống

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...

Thumbnail Image
16.9K
8
2 4
Avatar Viblo Algorithm thg 10 13, 2021 8:39 SA
7 min read

Xử lý số nguyên lớn (phần 2) - Các phép toán Nhân

Đâ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 ...

Thumbnail Image
30.3K
17
4 7
Avatar Viblo Algorithm thg 10 8, 2021 8:03 SA
16 min read

Xử lý số nguyên lớn (phần 1) - Nhập/Xuất, Phép so sánh, Phép cộng và Phép trừ

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...

Thumbnail Image
19.0K
4
3 0
Avatar Viblo Algorithm thg 10 6, 2021 8:56 SA
19 min read

Sắp xếp chèn, Sắp xếp chọn và Sắp xếp trộ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 -...
Thumbnail Image
10.4K
12
5 0
Avatar Viblo Algorithm thg 10 4, 2021 7:55 SA
12 min read

Heap và priority_queue của C++

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â...

Thumbnail Image
2.2K
19
9 0
Avatar Viblo Algorithm thg 10 1, 2021 8:10 SA
9 min read

Tất cả những gì bạn cần là quy hoạch động

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...

Thumbnail Image
7.3K
5
1 0
Avatar Viblo Algorithm thg 9 29, 2021 7:53 SA
7 min read

Unordered_map và unordered_set

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...
Thumbnail Image
38.3K
8
3 0
Avatar Viblo Algorithm thg 9 27, 2021 7:55 SA
4 min read

Set và Map trong C++

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 6setset6setset 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 ...

Thumbnail Image
12.7K
5
2 0
Avatar Viblo Algorithm thg 9 24, 2021 7:58 SA
13 min read

Ngăn xếp và Hàng đợi (Stack & Queue)

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ê...

Thumbnail Image
56.5K
21
7 3
Avatar Viblo Algorithm thg 9 22, 2021 7:57 SA
20 min read

Đệ quy và giải thuật đệ quy

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=11n = 1: Ta thấy $1 = 1^2,n = ...
Thumbnail Image
9.6K
7
1 0
Avatar Viblo Algorithm thg 9 20, 2021 7:55 SA
14 min read

Hệ cơ số (Hệ đếm)

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í...

Thumbnail Image
10.2K
12
4 1
Avatar Viblo Algorithm thg 9 17, 2021 7:38 SA
15 min read

Số nguyên tố và Các vấn đề liên quan

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 1111 và chính nó.

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

Lấy ví dụ: 515101,2,510515101, 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.

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

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

Ý t...

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