Viblo Algorithm

I. Cây

1. Định nghĩa cây và các khái niệm quan trọng

Trong chuyên đề này, cấu trúc dữ liệu mà chúng ta quan tâm đến là Cấu trúc cây. Thực tế, các bài toán dùng trực tiếp cây có rất ít, kèm theo sự phát triển của các ngôn ngữ lập trình khiến cho việc cài đặt thủ công những cấu trúc dữ liệu theo mô hình cây không còn cần thiết nữa. Vì vậy,...

I. Mở đầu

Công thức bao hàm - loại trừ là một công thức sử dụng để tính lực lượng (số lượng phần tử) của hợp của nhiều tập hợp. Công thức được phát biểu như sau: "Để tính lực lượng của hợp của nhiều tập hợp, ta tính tổng lực lượng các tập hợp đó, rồi trừ đi lực lượng của giao của các cặp hai tập hợp khác nhau, rồi cộng lực lượng của giao các bộ ba tập hợp khác nhau, rồi trừ đi lực lượng của cá...

I. Bài toán mở đầu

Bài toán chia kẹo Euler là một bài toán tổ hợp xuất hiện từ thời xa xưa, đây là một bài toán rất hay và có nhiều ứng dụng trong Toán học. Xuất phát từ một vấn đề rất đơn giản, nhà bác học Leohard Euler đã phát biểu nó thành một bài toán như sau:

"Có chiếc kẹo giống nhau, cần chia chúng cho em bé. Hỏi có bao nhiêu cách chia kẹo như vậy?"

Bài toán tưởng chừng như đơn giản,...

I. Bài toán Cái túi và những bài toán áp dụng

1. Lời mở đầu

Bài toán Cái túi, Bài toán Xếp ba lô, Bài toán Knapsack,...là những tên gọi khác nhau mà chúng ta thường nghe đến, nhưng tất cả đều dùng để chỉ chung một bài toán tối ưu hóa tổ hợp, trong đó ta cần phải lựa chọn một số đồ vật để nhét vào một chiếc túi với tải trọng biết tr...

I. Bài toán dãy con tăng dài nhất (Longest Increasing Subsequence)

1. Mở đầu

Trong bài viết trước về chủ đề Nhập môn Quy hoạch động, tôi đã giới thiệu tới các bạn những khái niệm cơ bản về Quy hoạch động, đồng thời giới thiệu một số bài toán Quy hoạch động điển hình (xem lại tại đây), trong đó có bài toán Dãy con tăng dài nhất. Tuy nhiên, tôi ...

I. Nhập xuất dữ liệu bằng file trong C++

Từ đầu khóa học, chúng ta luôn luôn nhập dữ liệu vào từ bàn phím, và trả ra kết quả trên cửa sổ console (nói một cách dễ hiểu là kết quả hiển thị trực tiếp lên cửa sổ thực thi chương trình). Tuy nhiên, trong một số kỳ thi lập trình (đặc biệt là ở Việt Nam), và xa hơn là trong công việc lập trình sau này, có những lúc dữ liệu nhập vào rất nhiều và lớn, v...

I. Kết hợp các dữ liệu khác kiểu với nhau

Xét trường hợp chúng ta cần lưu trữ thông tin của nhiều cuốn sách trong thư viện, mỗi cuốn sách có nhiều loại thông tin như: Tiêu đề, tác giả, thể loại và ID. Trong các kiểu dữ liệu nguyên thủy ta đã học, không có kiểu nào có thể lưu trữ cùng lúc nhiều thông tin như thế. Khi đó, lập trình viên sẽ phải tìm cách tạo ra các kiểu dữ liệu mới để lưu trữ tất...

I. Giới thiệu về thư viện chuẩn C++ (STL)

1. Lời mở đầu

Standard Template Library - thư viện Template chuẩn của C++ có lẽ là một trong những thứ mà các bạn học lập trình C++ được nghe tới rất nhiều. STL chính là một thư viện chứa những template (khuôn mẫu) của cấu trúc dữ liệu cũng như thuật toán được xây dựng một cách tổng quát nhất, nhằm hỗ trợ cho người dùng trong quá trình lập trình. Có t...

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. Địa chỉ của biến trong máy tính

1. Điều gì xảy ra khi khai báo một biến?

Như các bạn đã biết từ những bài học đầu tiên về ngôn ngữ lập trình, khi ta muốn sử dụng một biến với kiểu dữ liệu nguyên thủy, thì biến đó cần được khai báo. Sau khi khai báo một biến, thì hệ điều hành sẽ tìm đến một vùng nhớ trống trên các thiết bị lưu trữ t...

Đây là phần 2 của bài học về Cấu trúc (Struct) trong C++. Để hiểu rõ bài viết này, mời bạn đọc hãy xem lại bài viết phần 1 tại đây.

I. Hàm khởi tạo (Constructor)

1. Hàm khởi tạo mặc định (Default constructor)

Khi tạo ra một biến kiểu struct, ta thường đơn giản khai báo...

I. Dữ liệu dạng văn bản

1. Bảng kí tự ASCII

ASCII - tên đầy đủ là American Standard Code for Information Interchange - là một bảng mã chuẩn trao đổi thông tin Hoa Kỳ, bao gồm các kí tự và mã của chúng dựa trên bảng chữ cái Latin được dùng trong tiếng Anh hiện đại. Bảng mã này bao gồm $2560255,0 - 165,122,...$

Trong bảng mã ASCII có những kí tự in được và không in được. Trong chương này, chún...

I. Truyền mảng một chiều

Mảng cũng có thể được truyền vào hàm giống như một tham số để tính toán. Có $3$ cách để truyền mảng vào hàm: Sử dụng tham số mảng có kích cỡ, sử dụng tham số mảng không có kích cỡ và sử dụng con trỏ. Trong bài học này chúng ta sẽ tập trung vào hai cách đầu tiên, còn cách thứ ba với C++ là không cần thiết nên sẽ không đề cập ở đây.

Cú pháp:

• Truyền mảng có kích cỡ: ...

I. Mảng hai chiều trong C++

1. Khai báo và truy xuất

Ngoài kiểu dữ liệu mảng một chiều, C++ hỗ trợ kiểu dữ liệu mảng từ hai chiều tới nhiều chiều. Mảng hai chiều là ví dụ rất trực quan và dễ tưởng tượng, ta có thể xem nó như một bảng hình chữ nhật gồm có hàng và cột. Cú pháp khai báo rất đơn giản:

Khi đó, tổng số phần tử của mảng sẽ là {Sốhàng} {Sốcột}. Chẳng hạn, khai báo một mảng hai ...

I. Khái niệm về mảng

Trong lập trình, đôi khi ta gặp tập dữ liệu gồm rất nhiều đối tượng có kiểu giống nhau. Lấy ví dụ:

• Danh sách điểm tổng kết của các học sinh trong lớp (một danh sách các số thực).
• Danh sách tên của một phòng thi (một danh sách các chuỗi kí tự).

Mọi ngôn ngữ lập trình đều cung cấp những kiểu dữ liệu có cấu trúc để lưu trữ các dạng dữ liệu như mô tả bên trên. Đối với C++...

I. Phân chia chương trình thành từng hàm

1. Kĩ thuật lập trình hướng cấu trúc

Cùng xem xét một ví dụ sau: Cho ba số nguyên dương đều không nhỏ hơn $2,$ hãy kiếm tra xem những số nào là số nguyên tố và đưa ra thông báo số đó là số nguyên tố?

Ta biết rằng một số nguyên tố sẽ không chia hết cho số nào ngoài $1$ và chính nó. Áp dụng những gì đã học từ các bài trước, ta có thể xây dựng một chươn...

I. Lặp với số lần biết trước và lặp với số lần không biết trước

Cùng xem xét hai bài toán sau đây:

• Bài toán $1S,$ biết:

• Bài toán $2S,$ biết:

cho tới khi .

Đối với bài toán $1,S$ có thể được tính bằng cách sau:

• Đầu tiên, được gán giá trị $1 \ (\frac{1}{1})$.
• Tiếp theo, cộng vào tổng S một giá trị với . Việc cộng này được lặp lại lần tới khi thì thu được tổng ban đầu.

Đối với b...

I. Biểu thức logic trong C++

1. Kiểu dữ liệu bool

Trong mọi ngôn ngữ lập trình đều tồn tại hai trạng thái đúng - sai, tương đương với hai giá trị $10$. Để biểu diễn hai trạng thái này, trong C++ sử dụng kiểu dữ liệu nguyên thủy bool. Để khai báo các biến kiểu bool, ta sử dụng cú pháp:

Các biến kiểu bool còn được gọi là các biến logic, chúng chỉ được phép nhận hai giá trị là true hoặc false. ...

I. Kiểu dữ liệu

1. Kiểu dữ liệu nguyên thủy (Primitive Type)

Các bài toán trong thực tế thường sẽ có dữ liệu đầu vào và kết quả ra thuộc những kiểu dữ liệu quen thuộc như số nguyên, số thực,...Việc sử dụng các kiểu dữ liệu có liên quan mật thiết đến các phép toán có thể thao tác trên dữ liệu và bộ nhớ cấp phát cho dữ liệu đó. Mỗi ngôn ngữ lập trình sẽ cung cấp cho người dùng một số kiểu dữ li...

I. Tổng quan về chương trình khối chuyên Tin

1. Mục tiêu đào tạo

Chương trình chuyên Tin học và đào tạo thi HSG Tin học hướng tới các mục tiêu sau:

• Giúp học sinh hiểu rõ môn Tin học trong khối chuyên là gì, và làm thế nào để có phương pháp học tập tốt môn học. Tránh nhầm lẫn việc học trong lớp chuyên Tin là học Toán, là "lớp dễ hơn của chuyên Toán".
• Trang bị cho học sinh các kiến thức về...