Bài tập cơ bản về vòng lặp (Phần 2)

Tiếp nối Phần 1, ở Phần 2 mình sẽ giới thiệu các dạng bài tiếp theo trong chuỗi bài tập cơ bản về vòng lặp.

Bài tập cơ bản về vòng lặp (Phần 1)

Với các bạn đang học Nhập môn lập trình thì bài tập vòng lặp ngoài giúp làm quen với cách dùng vòng lặp còn giúp phát triển tư duy lập trình, giải thuật. Mình sẽ giới thiệu một số dạng bài tập vòng lặp cơ bản, một số ví dụ cùng với hướng giải quyết. Tất cả code tham khảo đều được viết dưới dạng hàm trong ngôn ngữ C/C++.

Ở Phần 1 mình sẽ hướng dẫn cách làm dạng bài vẽ hình. Các dạng bài khác sẽ được trình bày ở các phần tiếp theo.

Hướng dẫn sử dụng tính năng Debug trong Visual Studio 2015

Debug là một công việc mà hầu hết người lập trình đều phải thực hiện để tìm lỗi trong phần mềm của mình. Visual Studio đã hỗ trợ khá mạnh tính năng này để giúp đơn giản hơn trong việc tìm lỗi sản phẩm. Trong bài viết này mình sẽ hướng dẫn các bạn sử dụng tính năng Debug trên phiên bản mới nhất của Visual Studio, hiện tại là bản 2015. Các thao tác sẽ được thực hiện trên Visual Studio Enterprise 2015.

Sơ lược về Debug của Visual Studio

Debug trong Visual Studio cho phép bạn chạy chương trình từng bước để xem sự thay đổi giá trị của biến, trả về của hàm,... qua đó phát hiện những lỗi logic trong chương trình.

Một số thành phần cơ bản
Breakpoints: Là điểm mà chương trình sẽ dừng lại để cho phép bạn chạy từng bước các dòng code. Có thể đặt nhiều breakpoint trong chương trình.

Các cửa sổ theo dõi biến: Giúp bạn theo dõi sự thay đổi của biến hoặc hàm cho mỗi bước chạy. Nếu một biến có sự thay đổi giá trị thì sẽ có màu đỏ để phân biệt. Có 3 loại:

• Autos: Hiển thị tự động các biến, hoặc hàm trả về trong các dòng code trước.
• Locals: Tương tự Autos nhưng chỉ hiển thị các biến liên quan trong nội bộ hàm hoặc khối lệnh.
• Watch: cửa sổ tùy chỉnh cho phép bạn xem chỉ các biến mà bạn yêu cầu hoặc giá trị tùy chỉnh bất kỳ. Visual Studio cho phép bạn mở tối đa 4 cửa sổ Watch.

Thanh công cụ Debug: cung cấp các nút lệnh để bạn thực hiện Debug chương trình.

Cửa sổ Call Stack: Chứa lời gọi hàm trong ngăn xếp. Nếu chỉ debug ở mức độ cơ bản thì cũng không cần quan tâm cửa sổ này lắm.

Cửa sổ Diagnostic Tool: Chứa các công cụ chẩn đoán nâng cao. Cung cấp biểu đồ thời gian thực bộ nhớ, CPU,... mà chương trình sử dụng. Ngoài ra nó còn hiển thị các sự kiện được bắt và thời gian bắt.

Cài đặt và sử dụng bộ gõ tiếng Nhật trên Windows 10

Cũng giống như trên Windows 8.1 hay Windows 7, bộ gõ tiếng Nhật Microsoft IME được tích hợp sẵn trong hệ điều hành và bạn có thể bật lên để dùng một cách dễ dàng. Trong bài viết này mình sẽ hướng dẫn các bạn cài đặt bộ gõ này và một vài cách thức sử dụng nó.

Cài đặt
Chọn Start Menu -> Settings -> Time & language -> Region & language. Trong mục Languages bạn chọn Add a language như hình dưới:

Một danh sách các ngôn ngữ hiện ra, chọn Japanese.

Vậy là phần cài đặt đã xong.

Sử dụng bộ gõ tiếng Nhật
Để bật chế độ gõ tiếng Nhật bạn có thể chọn vào Language bar ở Taskbar và chọn Japanese.

Cách thứ hai bạn có thể dùng phím tắt Windows + Space và nhấn Space liên tiếp để chọn đến bộ gõ tiếng Nhật.

Danh sách liên kết vòng và một số thao tác

Chúng ta cùng tìm hiểu một cấu trúc dữ liệu cũng khá hữu ích là Danh sách liên kết vòng (Circular Linked List). Nó biểu diễn một cách tự nhiên các cấu trúc dạng tròn như các góc của đa giác, v.v... DSLK vòng có hai dạng thường thấy là dạng vòng đơn và vòng kép.

Dạng vòng đơn thực chất là một danh sách liên kết đơn có phần tử cuối trỏ về phần tử đầu tiên. Nó cũng có nhược điểm là chỉ duyệt từ một chiều. Dạng vòng kép cũng là một danh sách liên kết kép có phần tử cuối trỏ về đầu và đầu trỏ ngược về cuối.

Với DSLK vòng ta cần biết một vài thao tác cơ bản đủ dùng và các thao tác này sẽ được minh họa bằng C++. Bài này chỉ nói về danh sách liên kết vòng kép và bạn cũng nên sử dụng vòng kép để việc code lại đơn giản hơn.

Tổ chức dữ liệu
Một danh sách gồm có các phần tử gọi là node, mỗi node gồm 1 biến chứa dữ liệu và một hoặc nhiều biến con trỏ để liên kết với các node khác. Dưới đây là khai báo cấu trúc node:

struct DoublyNode
{
   <datatype> info;
   DoublyNode* prev, *next;
};

Do cấu trúc này ở dạng vòng nên một danh sách ta chỉ cần chọn một phần tử đầu thôi.

struct DoublyList
{
   DoublyNode* head;
};

Danh sách liên kết kép và các thao tác cơ bản

Nếu bạn đã đọc bài viết về Danh sách liên kết đơn thì có thể thấy việc tổ chức dạng danh sách tiện lợi hơn rất nhiều so với dùng mảng. Tuy nhiên, danh sách liên kết đơn vẫn có nhược điểm là chỉ có thể duyệt từ đầu đến cuối. Vì vậy, một số thao tác sẽ rất khó cài đặt trên nó. Danh sách liên kết kép có thể khắc phục nhược điểm này. Hầu hết các thao tác điều giống với danh sách liên kết đơn nhưng mình cũng khuyên các bạn nên đọc bài: Danh sách liên kết đơn và các thao tác cơ bản trước khi đọc bài viết này. Các thao tác được minh họa bằng C++.

Tổ chức dữ liệu
Với danh sách liên kết kép, mỗi phần tử sẽ liên kết với phần tử đứng trước và sau nó trong danh sách.
Mỗi phần tử trong danh sách (node) gồm biến lưu dữ liệu và 2 con trỏ liên kết tới phần tử trước và sau nó.

Khai báo phần tử của danh sách:

struct Node
{
   <datatype> info;
   Node  *prev, *next;
};

Một danh sách thì gồm nhiều phần tử, các phần tử đã liên kết nhau, mà đây là cấu trúc dữ liệu động nên ta cần biết phần tử đầu và phần tử cuối của danh sách.

Khai báo cấu trúc danh sách:

struct List
{
   Node *head, *tail;
}

Có thể minh họa danh sách liên kết kép như sau:

Các thao tác cơ bản
Tạo danh sách rỗng
Khi bạn tạo một biến kiểu List như trên thì 2 con trỏ thành viên được tạo ra, tuy nhiên chúng chưa được khởi tạo giá trị. Thao tác với con trỏ rỗng thì nguy hiểm nên cần thiết phải gán NULL cho 2 con trỏ này.

void CreateList(List &list)
{
   list.head = list.tail = NULL;
}

Kiểu dữ liệu trong C

Trong C có 5 kiểu dữ liệu cơ bản: int, float, double, char, void. Ngoài ra khi kết hợp với các từ khóa signed, unsigned, long, short ta còn có thêm các kiểu dẫn xuất. Kiểu cấu trúc struct trong C cho phép ta định nghĩa các kiểu dữ liệu mới dựa trên các kiểu dữ liệu cơ bản. Kiểu con trỏ là kiểu dữ liệu đặc biệt dùng lưu địa chỉ của biến khác.

Kiểu số nguyên
Kiểu số nguyên trong C là int, được dùng để lưu trữ số nguyên. Đây là kiểu dữ liệu cơ bản nhất trong các ngôn ngữ lập trình. Giá trị của kiểu int không cố định mà phụ thuộc vào trình biên dịch, thông thường là 4 bytes.

Ví dụ:

int a;
int a = 5;
int a, b;

Kiểu số thực
Trong C có 2 kiểu số thực là float và double, cho phép lưu trữ cả phần thập phân của một số.
Kiểu float có giá trị 4 bytes và có độ chính xác tới 6 chữ số thập phân. Kiểu double có giá trị 8 bytes và chính xác tới 10 chữ số. Tuy nhiên độ chính xác này là tương đối và còn phụ thuộc vào hệ điều hành.

Tùy nhu cầu mà người ta sử dụng float hay double, nếu tính toán không yêu cầu độ chính xác cao nên dùng kiểu float để tiết kiệm bộ nhớ.
Lưu ý: tính toán với các kiểu dữ liệu thực luôn có sai số.

Ví dụ:

float a = 5.7;
double b = 6; //=> 6.0

Các phạm vi truy xuất trong một lớp đối tượng C++

Khi xây dựng một class, chắc chắn bạn sẽ phải xác định phạm vi truy cập cho các thuộc tính và phương thức trong class đó. Mục đích của việc này nhằm quy định các thành phần nào có thể được truy cập, thay đổi từ bên ngoài, thành phần nào là riêng tư.

Có thể hiểu phạm vi truy xuất này cũng giống như biến toàn cục và biến cục bộ. Biến toàn cục có thể được truy cập từ tất cả các hàm sau khai báo nó, còn biến cục bộ chỉ có thể được truy cập nội bộ trong hàm.

Trong C++, phạm vi truy cập được xác định qua 3 từ khóa: public, private và protected.

• public: Các thành phần mang thuộc tinh này đều có thể được truy cập từ bất kỳ hàm nào, dù ở trong hay ngoài lớp.
• private: Các thành phần mang thuộc tinh này chỉ có thể được truy cập bên trong phạm vi lớp. Vì trong C++ cho phép định nghĩa phương thức ngoài khai báo lớp nên phạm vi lớp được hiểu là bên trong khai báo lớp và bên trong các định nghĩa thuộc lớp. 
• protected: Các thành phần mang thuộc tinh này chỉ có thể được truy cập bên trong phạm vi lớp và các lớp con kế thừa nó. Như vậy, nếu một lớp không có lớp con kế thừa nó thì phạm vi protected cũng giống như private.

Một ngoại lệ chỉ có trong C++ đó là định nghĩa friend. Một hàm hoặc lớp friend có thể truy cập vào các thành phần private và protected của lớp với hàm đó (hàm friend) hoặc với các đối tượng khác (lớp friend) với điều kiện phải được khai báo trước trong lớp.

Một số lưu ý về phạm vi truy xuất trong C++:

• Phạm vi truy xuất trong C++ được xác định trong qua các nhãn trong khai báo lớp. Nhãn bao gồm từ khóa và dấu hai chấm.
• Mỗi nhãn có phạm vi ảnh hưởng từ lúc khai báo đến khi gặp nhãn khác hoặc hết khai báo lớp.
• Nếu không chỉ rõ nhãn đầu tiên thì ngầm định nó có phạm vi truy cập là private.

Từ vựng về lập trình tiếng Nhật

Bài viết nhằm giúp các bạn yêu thích tiếng Nhật có thể tiếp cận được các tài liệu CNTT tiếng Nhật dễ dàng hơn. Dưới đây là danh sách các thuật ngữ, từ vựng về lập trình trong tiếng Nhật. Để đọc được, các bạn cần phải nắm thật vững 2 bảng chữ cái tiếng Nhật là Hiragana và Katakana. Các từ bằng Kanji sẽ được phiên âm ra Hiragana.

Tổng quan về đối tượng fstream trong C++

Đối tượng fstream cung cấp nhiều phương thức để đọc ghi file nhưng tiện lợi và an toàn hơn con trỏ FILE nhiều. Để sử dụng được fstream bạn cần khai báo #include<fstream>. Ngoài ra, C++ còn cung cấp thêm 2 đối tượng khác là ifstream và ofstream chỉ chuyên biệt cho việc đọc file và ghi file trong khi fstream có thể thực hiện được cả 2 việc này. Chính vì vậy, bài viết này sẽ hướng dẫn các bạn một cách vắn tắt các thao tác cơ bản với fstream trong C++.

1. Tạo đối tượng fstream để đọc/ghi file. Việc đọc/ghi file sẽ được thực hiện thông qua đối tượng này.
Khai báo: fstream <tênbiến>;

2. Dùng phương thức open() để mở một file.
Cú pháp:

<tênbiến>.open(<đường dẫn>,<chế độ mở>);

Hoặc có thể vừa khai báo biến vừa mở file luôn.

fstream <tênbiến>(<đường dẫn>,<chế độ mở>);

Đường dẫn có thể là tương đối (tính từ file exe khi được build ra) hoặc tuyệt đối (tính từ ổ đĩa gốc).
Chế độ mở có nhiều loại:

Chế độ mở	Ý nghĩa
ios::in	Mở file ở chế độ đọc
ios::out	Mở file ở chế độ ghi
ios::app	Mở file chế độ ghi thêm vào
ios::ate	Mở file để đọc/ghi từ cuối file
ios::trunc	Tạo đè file mới hoàn toàn
ios::nocreate	Mở một file phải tồn tại
ios::noreplace	Tạo file mới chưa tồn tại
ios::binary	Mở file chế độ nhị phân
ios::text	Mở file chế độ văn bản

Có thể kết hợp nhiều chế độ bằng toán tử |.
Ví dụ:

fstream file("data/text.txt", ios::in | ios::out);

Danh sách liên kết đơn và các thao tác cơ bản

Danh sách liên kết là một cấu trúc dữ liệu mà mỗi phần tử cần phải lưu thông tin của nó và địa chỉ của phần tử kế tiếp hoặc trước nó. Danh sách liên kết linh động hơn mảng rất nhiều do có thể thêm, xóa phần tử. Có nhiều dạng danh sách liên kết khác nhau và ở phần này mình sẽ nói về danh sách liên kết đơn cùng các thao tác với nó (minh họa bằng C++).

Tổ chức dữ liệu
Mỗi phần tử trong DSLK đơn (gọi là node hay nút) sẽ gồm một biến lưu dữ liệu của bạn và một biến con trỏ lưu địa chỉ của phần tử kế tiếp. Các phần tử được liên kết với nhau dựa vào con trỏ này.

struct Node
{
   <kiểu dữ liệu> info;
   Node *next;
};

Như vậy, khi biết được phần tử đầu danh sách thì dựa vào con trỏ next, ta có thể truy cập được tất cả các phần tử trong danh sách. Vậy một danh sách chỉ gồm 1 con trỏ trỏ đến phần tử đầu danh sách. Tuy nhiên, để một vài thao tác trở nên dễ dàng, ta có thể thêm một con trỏ đến cuối danh sách.

struct List
{
   Node *head, *tail;
};

Nếu chưa hiểu cấu trúc của nó, bạn có thể xem hình minh họa sau.

Các thao tác cơ bản
Tạo danh sách rỗng
Tại sao đây lại là một thao tác quan trọng. Một danh sách được tạo ra chứa 2 con trỏ rỗng chưa trỏ đến đâu cả. Vì vậy sẽ rất nguy hiểm nếu thao tác với 2 con trỏ này. Cần thiết phải gán cho nó giá trị NULL trước khi thao tác trên nó. Nếu bạn cài đặt danh sách theo phương pháp hướng đối tượng thì có thể khai báo phần này trong constructor nên không cần gọi hàm này bên ngoài.

void CreateList(List &list)
{
   list.head = list.tail = NULL;
}

Cách vẽ lại cây nhị phân tìm kiếm từ kết quả duyệt

Thường có 3 cách duyệt cơ bản là tiền thứ tự (NLR), trung thứ tự (LNR) và hậu thứ tự (LRN). Với kết quả duyệt kiểu NLR và LRN ta có thể vẽ lại cây ban đầu dễ dàng. Còn với LNR, ta không tìm được Node gốc nên không thể vẽ lại cây.

Nguyên tắc chung để vẽ lại cây
1. Tìm Node gốc.
2. Tìm đoạn lớn hơn Node gốc sẽ là nhánh phải, đoạn nhỏ hơn Node gốc sẽ là nhánh trái.
(Vì nguyên tắc của cây nhị phân tìm kiếm, Node gốc sẽ có khóa lớn hơn tất cả Node con nhánh bên trái và nhỏ hơn tất cả các Node ở nhánh phải)
3. Với mỗi đoạn vừa tìm được, tìm Node gốc của từng đoạn và tiếp tục tìm đoạn lớn hơn và nhỏ hơn Node gốc.

Đó là nguyên tắc chung để vẽ lại cây. Với cách duyệt NLR, ta luôn có Node gốc là Node đầu tiên của dãy kết quả, còn cách duyệt LRN là Node cuối cùng.

VD: Cho kết quả duyệt LRN: 5 3 7 9 8 11 6 20 19 37 25 21 15 12
Nhìn vào kết quả duyệt ta dễ dàng thấy 12 sẽ là Node gốc. Đoạn 5 đến 6 sẽ là nhánh trái và 20 đến 15 sẽ là nhánh phải.

Tiếp tục xét đoạn trái, ta thấy số 6 sẽ là Node gốc tiếp theo, tìm đoạn nhỏ hơn số 6 là [5,3] sẽ là nhánh trái, đoạn [7,11] sẽ là nhánh phải.
Cứ tiếp tục xét như thế đến hết ta sẽ vẽ được nhánh trái của cây.

Giờ ta xét nhánh phải với nguyên tắc tương tự. 15 sẽ là Node gốc tiếp theo, vì không có số nào nhỏ hơn 15 ở đoạn phải nên những số còn lại hoàn toàn nằm ở nhánh phải của 15. Xét tiếp đoạn đó tương tự ta sẽ vẽ được nhánh phải.

Các bạn hãy thử sức với các bài tập sau nhé.
Vẽ lại cây nhị phân tìm kiếm từ kết quả duyệt:
NLR: 7 6 4 15 13 9 14 30 31

Tại sao cần xóa bộ đệm bàn phím trước khi nhập chuỗi?

Thông thường, khi nhập một chuỗi trong màn hình console, ta phải có thao tác xóa bộ nhớ đệm bàn phím. Nếu không có thể thấy rằng kết quả nhập chuỗi bị sai hoặc trôi đi mất.

Trong quá trình chạy chương trình ta sẽ phải nhập bằng bàn phím, mọi ký tự bạn gõ vào bàn phím (kể cả ký tự Enter \n) đều được đẩy vào bộ nhớ đệm trước khi được gán vào biến. Nếu trước đó bạn có nhập số bằng scanf hoặc cin, chúng chỉ nhận số chứ không nhận được ký tự Enter, và ký tự Enter vẫn còn trong bộ nhớ đệm. Đến khi nhập chuỗi, các hàm nhập chuỗi nhận được ký tự Enter thì dừng nhập luôn và chương trình vẫn chạy tiếp. Điều này khiến kết quả bị sai.

Bạn có thể sử dụng các hàm sau để thực hiện xóa bộ nhớ đệm.

flushall()
Hàm này được định nghĩa trong stdio.h. Nó có tác dụng xóa bộ nhớ đệm tất cả các dòng nhập, xuất chuẩn và nhập xuất file.

fflush(stdin)
Hàm fflush() trong thư viện stdio.h cũng có tác dụng tương tự flushall(). Tuy nhiên nó cho phép lựa chọn xóa bộ nhớ đệm cho stream nào. Ở đây ta truyền vào stdin để xóa bộ đệm cho dòng nhập chuẩn, tức là bàn phím.

cin.ignore()
Đây là một phương thức của đối tượng cin trong C++. Phương thức này còn có những tham số khác nghĩa là bỏ qua hay loại bỏ một số lượng ký tự trong bộ đệm hoặc bỏ qua đến khi gặp ký tự nào đó. Nếu không có tham số thì mặc định là bỏ 1 ký tự trong bộ đệm. Dùng cách này hữu ích khi nhập dữ liệu chuyển từ số sang chữ.

Vậy nên dùng hàm nào? Hàm nào cũng được, flushall và fflush(stdin) có vẻ đơn giản hơn trong khi dùng cin.ignore() bạn phải cẩn thận, không lạm dụng để tránh sai ý muốn.

Cách viết một hàm đọc file cơ bản trong C/C++

Có nhiều cách viết hàm đọc file khác nhau, tùy theo yêu cầu bài toán và ý đồ người lập trình. Tuy nhiên, mình sẽ giới thiệu cách viết đơn giản nhất mà đa số trường hợp người ta hay dùng trong đọc file văn bản dạng text.

Bạn có thể sử dụng con trỏ FILE* hoặc trong C++ bạn còn có thể sử dụng đối tượng fstream để đọc ghi file (nhớ #include<fstream> trước khi khai báo đối tượng fstream). Các ví dụ bên dưới mình sử dụng fstream trong C++, về con trỏ FILE* thì tương tự.

Nguyên tắc chính là kiểm tra xem file đã được mở chưa. Sau đó tiến hành đọc file để ghi vào mảng, danh sách liên kết hoặc in ra màn hình, v.v... Cuối cùng là đóng file để kết thúc việc đọc file.

Tùy vào cấu trúc file văn bản mà ta xử lý khác nhau trong phần đọc file.

Dưới đây là ví dụ:
Mình có file D:\Test.txt có nội dung:
1 2 5 7 3 5 7 8 9
Yêu cầu đọc và xuất các số trên ra màn hình.

#include<fstream>
#include<iostream>
using namespace std;
void ReadFile(char* path)
{
   int n;
   fstream file(path, ios::in); //vừa khai báo vừa mở file
   if (!file.is_open()) //kiểm tra file đã được mở chưa
      cout<<"Could not open file!"<<endl;
   else
   {
      //xử lý đọc file ở đây
      while(!file.eof())
      {
         file>>n; //đọc file vào biến n
         cout<<n<<" ";
      }
      file.close(); //đóng file khi hoàn tất
   }
}

Ví dụ khác:
File D:\Test.txt có dòng đầu tiên là số lượng phần tử mảng, dòng thứ 2 là các phần tử
5
1 2 3 4 5
Yêu cầu đọc và lưu vào mảng.

#include<fstream>
#include<iostream>
using namespace std;
void ReadFile(char* path, int *a, int &n)
{
   fstream file(path, ios::in); //vừa khai báo vừa mở file
   if (!file.is_open()) //kiểm tra file đã được mở chưa
      cout<<"Could not open file!"<<endl;
   else
   {
      //xử lý đọc file ở đây
      file>>n; //đọc số đầu tiên
      for(int i = 0; i< n;i++)
         file>>a[i]; //đọc các số kế tiếp
      file.close(); //đóng file khi hoàn tất
   }
}

Vấn đề cấp phát động trong hàm

Ý tưởng của việc này là bạn có 1 con trỏ, bạn muốn cấp phát tài nguyên cho nó thông qua một hàm.

Ở đây ta có ví dụ:

int *a;

Ta đã có con trỏ a, làm sao để giữ được giá trị của con trỏ sau khi cấp phát?
Có thể thấy ta không thể truyền tham trị vào hàm, vì sau khi kết thúc hàm giá trị con trỏ không được lưu giữ.

Có 2 cách giải quyết cho trường hợp này

Dùng tham chiếu
Ta sẽ truyền một biến tham chiếu của con trỏ vào hàm. Sau khi cấp phát, giá trị con trỏ vẫn được lưu giữ. Lưu ý biến tham chiếu đến con trỏ cấp 1 là *&a, con trỏ cấp 2 là **&a, tức dấu & luôn ở gần tên biến.

Ví dụ:

void Alloc(int *&a, int n)
{
   a = new int[n];
}

Dùng con trỏ cấp cao hơn
Trong ví dụ này ta sẽ truyền vào con trỏ cấp 2. Con trỏ cấp 2 trỏ đến con trỏ cấp 1. Vì vậy, nếu bạn muốn có mảng n chiều thì có thể truyền vào con trỏ cấp n+1.

Ví dụ:

void Alloc(int **a, int n)
{
   *a = new int[n];
}

Ở đây *a là dữ liệu mà con trỏ cấp 2 đang trỏ tới, giá trị của *a bị thay đổi vẫn được lưu lại.

Những nguyên tắc cơ bản khi thiết kế class

Khi xây dựng một class chúng ta cũng cần có những nguyên tắc để class hoàn chỉnh hơn, đảm bảo các tính chất của lập trình hướng đối tượng.

Khi nào thì xây dựng class để biểu diễn đối tượng? Khi chúng ta nghĩ đến vấn đề như một khái niệm riêng lẻ thì lúc này nên xây dựng lớp để biểu diễn khái niệm đó. Lớp là biểu diễn của một khái niệm nào đó, nên tên lớp luôn là danh từ.

Các thuộc tính của lớp là các thành phần dữ liệu mô tả lớp nên chúng cũng là danh từ. Các hàm thành phần đặc trưng cho các hành vi của lớp, vì thế tên hàm là động từ.

Ví dụ:

class Point
{
private:
   float x, y;
public:
   void SetX(int);
   void SetY(int);

   ///...

};

Đa số các trường hợp nên đặt phạm vi của các biến thành viên là private để đảm bảo tính đóng gói.

Các thuộc tính có thể suy diễn từ những thuộc tính khác thì nên dùng hàm thành phần để thực hiện tính toán. Tuy nhiên, nếu các thuộc tính suy diễn dòi hỏi nhiều tài nguyên hoặc thời gian để thực hiện tính toán, ta có thể khai báo là dữ liệu thành phần.

Nếu các dữ liệu thành phần có thể được trừu tượng hóa thành lớp khác thì nên định nghĩa lớp đó để kết hợp chúng lại.

Ví dụ: Với lớp TamGiac nên dùng 3 biến thuộc lớp Diem để biểu diễn 3 điểm A, B, C thay vì dùng 6 biến biểu diễn xA, yA, xB, yB, xC, yC.

Trong mọi trường hợp, nên có phương thức thiết lập để khởi động đối tượng.  Nên có phương thức thiết lập có khả năng tự khởi động mà không cần tham số. Nếu đối tượng có nhu cầu cấp phát tài nguyên thì phải có phương thức thiết lập, copy constructor để khởi động đối tượng bằng đối tượng cùng kiểu và có destructor để dọn dẹp. Ngoài ra còn phải định nghĩa lại phép gán (tương tự như copy constructor). Nếu đối tượng đơn giản không cần tài nguyên riêng thì không cần copy constructor và destructor.

Có thể xem thêm bài viết này: Khi nào cần định nghĩa constructor, copy constructor và destructor?

Quy tắc chuyển sang thể Te của động từ tiếng Nhật

Thể Te của động từ rất hay gặp trong tiếng Nhật, vì vậy nó rất quan trọng nên các bạn cần phải nắm vững. Động từ chia ở thể Te có đuôi là  て hoặc で, dùng để sai bảo hoặc liên kết. Ở đây mình sẽ cung cấp cách chuyển sang thể Te của động từ dạng nguyên gốc （～う段） và dạng masu （～ます）.

Với động từ nguyên gốc, ta có cách chia của 3 nhóm nhỏ là khác nhau:
Động từ nhóm 1: Với động từ kết thúc bằng các đuôi khác nhau sẽ chia khác nhau.

•  ～う、～る、～つ  → ～って
• ～す → ～して
• ～く → ～いて
• ～ぐ → ～いで
• ～む、～ぬ、～ぶ → ～んで

Ví dụ:

会う → 会って「あう」

帰る → 帰って「かえる」

立つ → 立って「たつ」

出す → 出して「だす」

続く → 続いて「つづく」

泳ぐ → 泳いで「およぐ」

飲む → 飲んで「のむ」

死ぬ → 死んで「しぬ」

遊ぶ → 遊んで「あそぶ」

Động từ nhóm 2: Chỉ đơn giản bỏ đuôi る và thêm て

Ví dụ:

見る → 見て

食べる → 食べて

Động từ bất quy tắc: Có 3 động từ là iku (đi), kuru (đến) và suru (làm)

• 行く「いく」 → 行って「いって」
• 来る「くる」 → 来て「きて」
• する → して

Ghi chú: Với dạng động từ ghép bằng danh từ với する thì ta chỉ chia する như động từ bất quy tắc.

Với dạng masu, hầu như tương tự như trên, mình chỉ ghi cụ thể cho các bạn rõ hơn:

Động từ nhóm 1:

• ～います、～ります、～ちます → ～って
• ～します → ～して
• ～きます → ～いて
• ～ぎます → ～いで
• ～みます、～にます、～びます → ～んで

Ví dụ:

言います → 言って「いいます」

走ります → 走って「はしります」

立ちます → 立って「たちます」

書きます → 書いて「かきます」

泳ぎます → 泳いで「およぎます」

休みます → 休んで「やすみます」

死にます → 死んで「しにます」

飛びます → 飛んで「とびます」

Động từ nhóm 2: Bỏ ます và thêm て

Ví dụ:

変えます → 変えて

寝ます → 寝て

Động từ bất quy tắc: Không xét する và 来る vì chia giống như động từ nhóm 2

• 行きます → 行って

Khi nào cần định nghĩa constructor, copy constructor và destructor?

Hàm dựng (constructor) và hàm hủy (destructor) là 2 yếu tố quan trọng luôn có trong một lớp (class) trong lập trình hướng đối tượng. Nếu người dùng không định nghĩa thì trình biên dịch sẽ tự động thêm vào hàm dựng và hàm hủy mặc định. Tuy nhiên, đôi khi chúng ta cần phải định nghĩa lại hàm dựng và hàm hủy để đảm bảo an toàn và hợp logic hơn.

Hàm dựng (constructor)
Hàm dựng là hàm được tự động gọi khi đối tượng được tạo lập. Có 3 loại: mặc định (không tham số), có tham số và hàm dựng sao chép (copy constructor).

Trong hầu hết các trường hợp, bạn nên định nghĩa hàm dựng để khởi tạo giá trị ban đầu cho các biến thành viên.

Nếu khai báo đối tượng mà không cung cấp đối số thì hàm dựng mặc định sẽ được gọi, nếu có đối số thì hàm dựng có tham số sẽ được gọi. Vì vậy, hàm dựng có tham số thường được dùng để khởi động đối tượng với giá trị tùy người dùng thay vì giá trị được định nghĩa trong hàm dựng mặc định. Ngoài ra, còn được dùng để chuyển kiểu ngầm định khi gọi với toán tử.

Hàm dựng sao chép dùng để tạo nên đối tượng mới giống hệt đối tượng cũ và thường được dùng trong phép gán. Tất nhiên trình biên dịch sẽ tự thêm copy constructor mặc định khi không khai báo. Nguyên tắc của copy constructor là copy giá trị theo từng cặp biến thành viên.

Vấn đề chỉ xuất hiện khi lớp có thành viên là con trỏ và có cấp phát tài nguyên động như mảng. Trong trường hợp này, nếu không định nghĩa lại copy constructor thì mặc định chỉ sao chép giá trị của các biến thành viên mà không sao chép mảng động. Cụ thể hơn, với biến thành viên là con trỏ, giá trị (tức địa chỉ của mảng động) sẽ được bê nguyên xi qua con trỏ của đối tượng kia và hiển nhiên 2 con trỏ đang trỏ đến cùng một vùng nhớ. Khi hủy 2 đối tượng thì vùng nhớ sẽ bị thu hồi 2 lần và điều này gây ra lỗi. Hơn nữa, việc 2 đối tượng khác nhau cùng dùng chung vùng nhớ cũng sẽ không hợp logic. Vậy, bạn nên định nghĩa lại copy constructor khi lớp có thành viên là con trỏ và có cấp phát tài nguyên động.

 Nguyên tắc định nghĩa lại:
1. Gán các biến thành viên tĩnh cho nhau.
2. Cấp phát lại vùng nhớ động cho con trỏ.
3. Sao chép lại mảng động.

Làm quen với ngôn ngữ C từ Pascal (Phần 2)

Trong phần này mình sẽ nói về các cú pháp vòng lặp, rẽ nhánh, điểm khác nhau của chúng trong C và Pascal.

Lệnh rẽ nhánh if
Đây là một lệnh rất quen thuộc. Trong C, biểu thức điều kiện được đặt trong cặp dấu ngoặc tròn thay vì giữa 2 từ khóa if .. then như Pascal. Tiếp theo là một lệnh hoặc khối lệnh. Khối lệnh trong C đặt giữa cặp dấu ngoặc nhọn {} còn trong Pascal đặt giữa begin .. end;

Ở dạng có thêm else trong Pascal được tính là một lệnh. Vì vậy nên khối lệnh trước else sẽ không có dấu chấm phẩy. Còn trong C tính là 2 lệnh nên cần dấu chấm phẩy trước else.

Ví dụ:

if a > b then writeln(a)
else writeln(b);

if (a > b) printf("%d\n", a);
else printf("%d\n", b);

Lệnh rẽ nhánh switch .. case
Tương đương với case .. of của Pascal. Nhưng switch .. case có vẻ khó sử dụng hơn, nó đòi hỏi phải có lệnh nhảy break sau mỗi case, nếu không nó sẽ thực hiện tất cả các case. Dưới đây là ví dụ:

case month of
   4, 6, 9, 11 : writeln('30 days');
   2: writeln('28 days');
   else writeln('31 days');
end;

switch (month)
{
case 4: case 6: case 9: case 11:
   printf("30 days\n");
   break;
case 2:
   printf("28 days\n");
   break;
default:
   printf("31 days");
}

Vòng lặp for
Cách vòng lặp for trong C hoạt động khác hoàn toàn với Pascal. Trong C, vòng lặp for có cú pháp:

for(<khởi tạo>;<điều kiện>;<tăng biến chạy>)

Trong đó phần <khởi tạo> dùng để tạo giá trị ban đầu cho biến chạy và chỉ được thực hiện 1 lần duy nhất. Phần <điều kiện> chứa điều kiện để vòng lặp thực hiện và phần <tăng biến chạy> mô tả cách thức tăng/giảm của biến chạy. Vòng for của C có thể thay thế tất cả các vòng lặp còn lại.

Tuy nhiên, vòng for của Pascal chỉ có thể tăng/giảm biến chạy 1 đơn vị.
Dưới đây là ví dụ: Tính S = 2 + 4 + 6 + 8 + ...+ 2n trong Pascal không thể thực hiện bằng for nhưng C thì có thể:

int s = 0;
for (int i = 2; i <= 2*n; i += 2)
   s += i;

Vòng lặp while và do .. while
Vòng lặp while trong C hầu như tương tự Pascal và mình không có gì để bàn. Trong C còn có vòng lặp do .. while, chỉ khác while ở chỗ thực hiện lệnh 1 lần rồi mới kiểm tra điều kiện lặp, nếu đúng mới lặp lại tiếp. Khác với repeat .. until của Pascal, điều kiện trong until là ngược với điều kiện trong while của do .. while.
Ví dụ: Nhập N trong khoảng từ 1 đến 100, nếu ngoài khoảng đó yêu cầu nhập lại.

repeat
   write('Nhap N: ');
   readln(n);
until n >= 1 and n <= 100;

do
{
   printf("Nhap N: ");
   scanf("%d", &n);
} while (n < 1 || n > 100);

Làm quen với ngôn ngữ C từ Pascal (Phần 1)

Bài viết này hướng đến các bạn học sinh muốn tìm hiểu thêm về ngôn ngữ C khi các bạn chỉ biết về Pascal. Ở phần này mình chỉ phân tích chủ yếu về các khái niệm, sự giống và khác nhau trong cú pháp giữa 2 ngôn ngữ và các vấn đề rắc rối thường gặp trong ngôn ngữ C chứ không đi sâu vào cụ thể.

C là một ngôn ngữ hướng cấu trúc và được tổ chức theo đơn vị cơ bản là các hàm. Vì vậy, chương trình chính của C cũng là một hàm. Một lệnh của C cũng được kết thúc bằng dấu chấm phẩy (;), tương tự như Pascal.

Bây giờ chúng ta cùng xem một chương trình đơn giản trong Pascal và C khác nhau như thế nào.

//Đoạn chương trình Pascal
program vi_du;
uses crt;
var
   a: integer;
begin
   writeln('Nhap A: ');
   readln(a);
   writeln('A = ', a);
end.

//Đoạn chương trình C
#include<stdio.h>
int main()
{
   int a;
   printf("Nhap A: ");
   scanf("%d", &a);
   printf("A = %d", a);
   return 0;
}

Lệnh program trong Pascal chỉ tên chương trình, trong C không có lệnh này và nó cũng không cần thiết. Ngay cả khi lập trình trong Pascal không có lệnh này chương trình vẫn chạy bình thường mà phải không? Cho nên đây không phải là một lệnh quan trọng.

Lệnh uses để khai báo thư viện trong Pascal. Thư viện quan trọng là crt (có các hàm như clrscr() chẳng hạn). Lệnh này trong C khai báo là #include<stdio.h> (nhớ là không có dấu chấm phẩy nhé).
Thư viện nhập xuất chuẩn của C là stdio.h, thư viện này chứa các hàm để bạn xuất ra màn hình hay nhập dữ liệu từ bàn phím vào biến, v.v...

Biến trong Pascal được khai báo bằng từ khóa var và phải được đặt trước khối lệnh begin .. end. Trong C biến được khai báo bất kỳ đâu bên trong hàm và nó có phạm vi sử dụng từ lúc khai báo đến hết hàm.

Bonus: Kiểu mảng trong Pascal khai báo khá phức tạp, cho phép đặt kiểu chỉ số (thông thường bắt đầu từ 1). Còn trong C kiểu mảng khai báo như khai báo biến nhưng có thêm cặp ngoặc vuông chỉ số lượng phần tử. Các phần tử được đánh chỉ số từ 0 đến n-1.

Ví dụ:

//Khai báo mảng a có 10 phần tử được đánh chỉ số từ 0 đến 9
int a[10];

Cặp lệnh begin .. end là một đặc trưng của Pascal, nó đánh dấu bắt đầu chương trình và kết thúc chương trình, đồng thời nó cũng chỉ một khối các lệnh (trong if .. then chẳng hạn, khi mà bạn muốn thực hiện nhiều lệnh trong cùng 1 điều kiện).

Như ban đầu mình đã nói, chương trình trong C được tổ chức theo các hàm. Chương trình chính cũng là một hàm và hàm này mang tên là main(). Cặp dấu chỉ khối lệnh trong C là cặp dấu ngoặc nhọn { }. Nếu tìm hiểu về C bạn sẽ thấy những rắc rối như tại sao hàm main() không nên trả về kiểu void, v.v...

Thêm một tí: Trong C, khai báo hàm cũng đặt kiểu trả về trước tên hàm như khai báo biến. Thủ tục (procedure) cũng là hàm nhưng có kiểu trả về là void. Dùng lệnh return để trả về thay vì gán tên hàm với giá trị trả về như Pascal.

C có các hàm nhập xuất chuẩn printf(), scanf() cũng giống như write, writeln, read, readln của Pascal. Tuy nhiên, cú pháp cũng khá rắc rối và không tiện dụng như Pascal, bạn sẽ phải tìm hiểu về mã đặc tả, địa chỉ, v.v...

Có thể thấy Pascal hướng đến sự trong sáng rõ ràng nên thích hợp dạy trong nhà trường, còn C yêu cầu phải tìm hiểu thêm về yếu tố kỹ thuật. Tuy nhiên, nếu nắm được ngôn ngữ C và rèn luyện tư duy lập trình thì các bạn sẽ tìm hiểu các ngôn ngữ khác rất dễ dàng.

Với phần 1 các bạn đã thấy được những điểm giống và khác biệt giữa C và Pascal. Phần tiếp theo mình sẽ nói về cú pháp một số cấu trúc rẽ nhánh, lặp thông dụng giữa 2 ngôn ngữ.

Đo trực tiếp thời gian chạy của thuật toán

Đo thời gian chạy là một trong những cách để đánh giá hiệu quả của một thuật toán. Công việc nghe có vẻ khó khăn nhưng thực tế, với các hàm, kiểu dữ liệu được định nghĩa trong thư viện time.h của C (trong C++ có thể dùng cả time.h hoặc ctime), ta có thể đo thời gian chạy của một đoạn chương trình bất kỳ một cách dễ dàng.

Trước hết cần tìm hiểu những thành phần cần thiết:

• clock_t : là một kiểu dữ liệu được dùng để đếm clock tick. Clock tick là đơn vị thời gian đặc biệt có mối quan hệ với hằng số CLOCKS_PER_SEC (thông thường là 1/1000 giây).
• clock() : là một hàm trả về thời gian xử lý của chương trình. Kiểu dữ liệu trả về là clock_t
• CLOCKS_PER_SEC: là một hằng số macro đại diện cho số clock tick mỗi giây (thường là 1000).

Vậy để đo thời gian chạy của một đoạn chương trình, ta dùng các biến clock_t ghi lại thời gian thực hiện rồi chia cho hằng số CLOCKS_PER_SEC để ra được số giây thực hiện.

Có thể xem ví dụ mẫu sau:

int main()
{
   clock_t begin = clock(); //ghi lại thời gian đầu

   //Đoạn chương trình cần đo

   clock_t end = clock(); //ghi lại thời gian lúc sau
   cout<<"Time run: "<<(float)(end-begin)/CLOCKS_PER_SEC<<" s"<<endl;
   return 0;
}

Biến tham chiếu khác biến con trỏ như thế nào?

Cả tham chiếu (reference) và con trỏ (pointer) đều thuộc kiểu địa chỉ trong C++ và thường được dùng để truy cập gián tiếp đến các đối tượng khác. Tuy nhiên chúng cũng có sự khác nhau cơ bản các bạn có thể tham khảo dưới đây:

1. Khai báo biến con trỏ: <kiểu dữ liệu> *<tên biến>;
Khai báo biến tham chiếu: <kiểu dữ liệu> &<tên biến> = <tên đối tượng>;

2. Dấu & trong khai báo tham chiếu khác với toán tử lấy địa chỉ &. Cũng như dấu * khai báo con trỏ khác với toán tử lấy giá trị *. Chúng chỉ báo hiệu đây là biến tham chiếu hay là biến con trỏ thôi.

3. Con trỏ có thể khởi tạo mà không cần gán địa chỉ, ta có một con trỏ không xác định. Tham chiếu bắt buộc phải gán bằng một đối tượng khác, có thể là một biến. Vì vậy dùng con trỏ có thể dễ gây nhầm lẫn và nguy hiểm hơn tham chiếu.

int *p; //hợp lệ
int a = 5; //hợp lệ
int &b; //không hợp lệ
int &c = a; //OK, lúc này c và a là một.

4. Con trỏ là một biến riêng biệt lưu giữ địa chỉ của đối tượng khác nên truy cập gián tiếp thông qua địa chỉ. Tham chiếu được xem như một cái tên khác của đối tượng vì nó dùng chung địa chỉ với đối tượng được tham chiếu.

5. Kích thước một biến con trỏ là cố định. Kích thước biến tham chiếu phụ thuộc kiểu dữ liệu của đối tượng.

sizeof(double) // 8 bytes
sizeof(double*) // 4 bytes
sizeof(double&) // 8 bytes

6. Con trỏ có thể được chỉ định để truy cập đến các đối tượng khác nhau bằng cách thay đổi giá trị địa chỉ mà con trỏ lưu giữ. Tuy nhiên, tham chiếu chỉ truy cập được duy nhất một đối tượng đã được khởi tạo cho nó. Vì vậy con trỏ linh hoạt hơn tham chiếu.

7. Có thể khai báo mảng các con trỏ nhưng không được khai báo mảng các tham chiếu.

8. Tham chiếu thường được dùng làm các tham số truyền vào hàm khi muốn giá trị của tham số thay đổi sau khi ra khỏi hàm.

Tham chiếu cũng được dùng để tiết kiệm bộ nhớ khi truyền đối tượng vào hàm. Hệ thống sẽ tạo biến tham chiếu thay vì tạo bản copy đối tượng. Tuy nhiên, đối tượng có thể bị thay đổi. Có thể dùng hằng tham chiếu để ngăn điều này.

int sum(int a); // a sẽ không thay đổi khi ra khỏi hàm
int swap(int &a, int &b); // thay đổi trong hàm vẫn lưu lại với a, b
int addition(const int& a); //a sẽ không thay đổi

Tất nhiên cũng có thể dùng con trỏ cho những trường hợp này.

9. Con trỏ dùng để cấp phát động nhưng không thể thực hiện việc này với tham chiếu.

10. Biến tham chiếu không thể tham chiếu đến con trỏ nhưng con trỏ có thể trỏ đến biến tham chiếu.

Hướng dẫn làm menu đơn giản trong màn hình Console

Đúng như tiêu đề, menu này rất đơn giản cho phép người dùng lựa chọn tính năng của chương trình trong màn hình Console và có thể áp dụng vào những game cơ bản. Bạn chỉ cần có kiến thức về vòng lặp do...while, cấu trúc điều kiện switch..case để làm menu này. Cách làm sẽ được minh họa bằng C++.

Đầu tiên, để menu hiện ra cho bạn lựa chọn khi chạy chương trình hoặc khi chạy hết một tính năng, ta sẽ sử dụng vòng lặp do..while, tất nhiên cũng phải có lựa chọn thoát chương trình nên dùng một biến kiểu bool làm điều kiện thoát vòng lặp (trong C bạn có thể dùng biến kiểu int cũng được).

bool isExit = false; //thiết lập ban đầu là không thoát
do
{

} while (!isExit);

Cần phải in ra màn hình để hướng dẫn người dùng biết, đồng thời cũng phải có một biến lưu lại sự lựa chọn của người dùng.

bool isExit = false;
int option; //biến lưu lại lựa chọn người dùng
do
{
   cout <<"Please select:" <<endl
        <<"1. Input students" <<endl
        <<"2. Output students" <<endl
        <<"3. Sort and output students" <<endl
        <<"4. Exit" <<endl
        <<"----------------------------"<<endl
        <<"Your choice: ";
   cin >> option; //lưu lựa chọn người dùng

} while (!isExit);

Tiếp theo là xử lý yêu cầu của người dùng. Để làm việc này ta dùng cấu trúc switch..case để rẽ nhánh thực hiện các lệnh phù hợp. Lệnh switch..case này vẫn nằm trong vòng lặp do..while. Trong ví dụ này, với lựa chọn 4, ta gán biến isExit thành true để thoát khỏi vòng lặp do..while cũng như thoát chương trình.

switch (option)
{
case 1:
   //lệnh
   break;
case 2:
   //lệnh
   break;
case 3:
   //lệnh
   break;
case 4:
   isExit = true;
   break;
default:
   cout << "Your choice is not valid!" << endl;
}

Công việc cuối cùng là hoàn tất các lệnh xử lý cho mỗi trường hợp trong menu thôi. Rất đơn giản phải không nào!

Thuật toán sắp xếp: Selection Sort (chọn trực tiếp)

Selection Sort là một thuật toán sắp xếp tương đối dễ hiểu. Ý tưởng chính vẫn là đổi chỗ những cặp nghịch thế, tuy nhiên cái hay là ở chỗ Selection Sort tìm vị trí chứa phần tử nhỏ nhất để đổi chỗ với phần tử đang xét chứ không đổi tất cả các cặp nghịch thế như Bubble Sort hay Interchange Sort.

Ý tưởng
Xét phần tử đầu tiên của dãy. Tìm phần tử nhỏ nhất trong các phần tử còn lại. Hoán đổi phần tử đầu tiên với phần tử nhỏ nhất này, ta được phần tử đầu tiên có vị trí đúng. Bỏ qua phần tử vừa được xét, tiếp tục xét đến phần tử kế tiếp và thực hiện đến hết dãy.

Cài đặt trong C++

int min, i, j; //min là chỉ số phần tử nhỏ nhất
for(i = 0; i < n-1; i++)
{
   min = i;
   for(j = i+1; j < n; j++)
      if(a[j] < a[min])
         min = j; //tìm min trong các phần tử còn lại
   if(min != i)
     swap(a[i], a[min]); //đổi chỗ nếu tìm thấy min
}

Minh họa
Nguồn: Wikipedia

Đánh giá
Về số phép so sánh, ở lượt xét thứ i luôn có (n-i) phép so sánh để tìm min và không phụ thuộc tình trạng ban đầu của dãy nên số phép so sánh ước lượng là: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số lần hoán vị ở trường hợp tốt nhất là 0.
Trường hợp xấu nhất là: 3n(n-1)/2.

Độ phức tạp là: O(n²)

Thuật toán sắp xếp: Bubble Sort (sắp xếp nổi bọt)

Bubble Sort là một thuật toán sắp xếp kiểu so sánh rất đơn giản và dễ hiểu. Ý tưởng chính của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Ý tưởng
Đối với Bubble Sort, ta chọn cặp bằng cách xét hai phần tử kế cận nhau.
Có 2 dạng sắp xếp của Bubble Sort

Dạng 1: Sắp từ đầu đến cuối
Xuất phát từ đầu dãy, ta so sánh và đổi chỗ các cặp nghịch thế đến cuối dãy để đưa phần tử lớn nhất về cuối dãy. Khi đó chỉ việc xét các phần tử còn lại trong dãy và lặp lại các bước để sắp xếp.

Dạng 2: Sắp từ cuối lên đầu
Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử nghịch thế để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

Cài đặt theo ngôn ngữ C++
Dạng 1: Sắp từ đầu đến cuối

int i, j;
for (i = n-1 ; i > 0; i--)
   for (j = 0; j < i; j++)
      if (a[j] > a[j+1]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chổ

Dạng 2: Sắp từ cuối lên đầu

int i, j;
for (i = 0; i < n-1; i++)
   for (j = n-1; j > i; j--)
      if (a[j-1] > a[j]) //nghịch thế
         swap(a[j],a[j-1]); //đổi chỗ

Minh họa
Dưới đây là minh hoạ cho thuật toán Bubble Sort theo dạng 1 (nguồn: Wikipedia)

Đánh giá
Số phép so sánh không phụ thuộc vào tình trạng ban đầu của dãy. Có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Số phép hoán vị (3 phép gán) phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)

Thuật toán sắp xếp: Interchange Sort (đổi chỗ trực tiếp)

Để sắp xếp một dãy, có nhiều cách làm khác nhau. Trong bài viết này mình sẽ nói về Interchange Sort, hay còn gọi là thuật toán sắp xếp đổi chỗ trực tiếp.

Ý tưởng
Ý tưởng của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng nghịch thế (không thỏa điều kiện thứ tự).

Để bắt cặp tất cả các phần tử trong dãy, ta dùng 2 vòng lặp. Vòng lặp ngoài sẽ chạy từ đầu dãy đến phần tử kế cuối. Vòng lặp trong sẽ chạy từ phần tử tiếp theo của vị trí đang xét ở vòng lặp ngoài. Mỗi lần xét ta sẽ so sánh 2 phần tử trong cặp. Nếu chúng nghịch thế thì sẽ hoán đổi vị trí của chúng.

Ta thấy sau mỗi lần duyệt ở vòng lặp ngoài ta sẽ được phần tử đầu tiên đứng đúng thứ tự yêu cầu. Cứ thực hiện đến hết dãy ta sẽ được một dãy đã sắp xếp

Cài đặt
Mã dưới đây được cài đặt theo ngôn ngữ C/C++ với yêu cầu sắp xếp dãy tăng dần

void InterchangeSort(int *a, int n)
{
   for (int i = 0; i < n-1; i++)
      for (int j = i+1; j < n; j++)
         if (a[i] > a[j])
         {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
         }
}

Đánh giá
Số phép so sánh của thuật toán này không đổi, không phụ thuộc tình trạng ban đầu của dãy. Phần tử thứ i được so sánh với n-i phần tử còn lại nên có thể ước lượng số phép so sánh bằng: (n-1) + (n-2) + ... + 1 = n(n - 1)/2.

Tuy nhiên số phép hoán vị (3 phép gán) lại phụ thuộc tình trạng ban đầu. Trong trường hợp tốt nhất, tức dãy đã được sắp xếp hoàn toàn thì không cần phải hoán vị, nên số phép hoán vị là: 0.
Trường hợp xấu nhất, tức dãy có thứ tự ngược với yêu cầu. Mỗi lần so sánh ta lại phải hoán vị nên số phép hoán vị là: n(n - 1)/2.

Độ phức tạp của thuật toán này là: O(n²)

Tổng quan về kiểu string trong C++

1. string là kiểu dữ liệu mới được định nghĩa sẵn trong C++, nó có nhiều ưu điểm vượt trội và giúp tránh được những phiền phức so với chuỗi kiểu char* của C.

2. Trong C++, bạn vẫn có thể dùng kiểu char* nếu muốn. Có thể chuyển từ kiểu string sang chuỗi char* bằng phương thức c_str()

3. Cần khai báo #include<string> để có thể sử dụng đầy đủ tiện ích của string.

4. string có các phép +, += để nối chuỗi thay vì dùng hàm trong thư viện string.h như kiểu char*

5. Các hàm trong thư viện string.h (strlen, strcmp, strlwr,... ) sẽ không sử dụng được với string.

6. Có thể so sánh trực tiếp 2 chuỗi string: ==, !=, >, >=, <, <=. Nguyên tắc so sánh giống hệt như khi dùng hàm strcmp().

7. Dùng phương thức length() để lấy độ dài chuỗi, dùng phép lấy chỉ số [] để lấy từng phần tử của chuỗi.
Ví dụ:

string a = "ABCDE";
cout<< a.length();
cout<< a[2];

Những kiến thức căn bản về con trỏ

1. Con trỏ khác với biến bình thường ở chỗ nó lưu giữ địa chỉ của một biến khác thay vì lưu trữ giá trị (hay còn gọi là trỏ đến biến khác), để dễ hình dung bạn có thể coi con trỏ là một mặt nạ tượng trưng cho biến mà nó trỏ đến.

2. Vì nó chỉ lưu giữ địa chỉ thay vì nội dung nên kích thước mọi biến con trỏ trong Windows là 4 bytes, trong Linux là 2 bytes.

3. Cách khai báo: <kiểu dữ liệu> *<tên biến>
Ví dụ:

int *p; //p là con trỏ
int* p; //p là con trỏ
int* p, q; //p là con trỏ, q không phải là con trỏ
int *p, *q; //cả p và q là con trỏ

4. Con trỏ cũng có 1 địa chỉ riêng. Toán tử * lấy nội dung tại vùng nhớ mà con trỏ trỏ đến. Toán tử & lấy địa chỉ của một biến (kể cả con trỏ).

Với khai báo: int *p; thì

• p là con trỏ
• *p là giá trị tại vùng nhớ mà p trỏ đến
• &p là địa chỉ của con trỏ p

5. Con trỏ trỏ đến địa chỉ của 1 biến: <tên con trỏ> = &<tên biến>
Con trỏ trỏ đến con trỏ khác: <con trỏ 1> = <con trỏ 2>

6. Mã đặc tả của con trỏ và địa chỉ là %p, dùng để in địa chỉ lên màn hình.
Ví dụ:

int x = 5;
int *p = &x;
printf("%p", &x); //xuất địa chỉ của x
printf("%p", p); //xuất giá trị của con trỏ p, tức là địa chỉ của x
printf("%p", &p); //xuất địa chỉ của con trỏ p

Làm quen với MessageBox trong C#

Chắc hẳn MessageBox đã quá quen thuộc với chúng ta khi sử dụng hệ điều hành Windows. Ngôn ngữ C# và nền tảng .NET Framework đã hỗ trợ rất nhiều trong việc sử dụng MessageBox. Bài viết này sẽ hướng dẫn các bạn làm quen với MessageBox trong Windows Form.

MessageBox là một lớp (class) nằm trong System.Windows.Forms có một phương thức Show để hiển thị thông báo. Có rất nhiều kiểu thông báo, bạn có thể điều chỉnh nội dung thông báo, tiêu đề, các nút OK-Cancel, biểu tượng, v.v...

MessageBox.Show("Xin chào! Tôi là C#");

Đây là kiểu thông báo đơn giản nhất, chỉ có nội dung và nút OK, chưa bao gồm biểu tượng, tiêu đề, v.v..

Để có tiêu đề ta thêm 1 tham số chuỗi truyền vào phương thức như sau:

MessageBox.Show("Xin chào! Tôi là C#","Thông báo");

Hàm xóa một hàng và một cột bất kỳ trong ma trận

Có thể viết hàm xóa một hàng riêng và xóa một cột riêng và gọi chúng để xóa một hàng và một cột trong ma trận. Tuy nhiên, như vậy sẽ duyệt ma trận đến 2 lần. Để tối ưu hóa, ta có thể thực hiện xóa cùng lúc 1 hàng và một cột bằng cách sau đây.

Để dễ hiểu có thể xem hình minh họa:

Giả sử gọi cột cần xóa là iColumn và hàng cần xóa là iRow thì cả 2 sẽ tạo nên 4 vùng. Chỉ có vùng phía trên bên trái giữ nguyên còn các vùng khác di chuyển theo hướng như trên hình. Vùng phía trên bên phải sẽ dịch sang trái 1 cột, vùng phía dưới bên trái sẽ dịch lên 1 hàng và vùng phía dưới bên phải sẽ dịch xéo lên phía trái.

Như vậy ta sẽ minh họa cách làm bằng C/C++ như sau:

void DeleteRowColumn(int a[][20], 
                        int &m, int &n, int iRow, int iColumn)
{
   for(int i=0;i<m;i++)
      for(int j=0;j<n;j++)
      {
         if(i < iRow && j >= iColumn) //Vùng phía trên bên phải
            a[i][j]=a[i][j+1];
         else if(i >= iRow && j < iColumn) //Vùng phía dưới bên trái
            a[i][j]=a[i+1][j];
         else if(i >= iRow && j >= iColumn) //Vùng phía dưới bên phải
            a[i][j]=a[i+1][j+1];
      }
   m--;
   n--;
}

Một số thao tác cơ bản với cấu trúc Số phức

Cấu trúc Phân số và Số phức là 2 cấu trúc đơn giản nhất thường được dùng để minh họa kiểu cấu trúc trong C/C++. Thực hành viết các hàm thao tác với các cấu trúc này sẽ giúp quen dần với kiểu cấu trúc và là bước đệm để học lập trình hướng đối tượng. Các ví dụ sẽ được minh họa bằng ngôn ngữ C++.

Trước khi viết các hàm thao tác trên các cấu trúc Số phức, ta cần khai báo cấu trúc như sau:

struct Complex
{
   float Re; //phần thực - real
   float Im; //phần ảo - imaginary
};

Các hàm thao tác với Complex:

Hiển thị số phức

void OutputComplex(Complex a)
{
   if (a.Re != 0) cout << a.Re;
   if (a.Im != 0)
   {
      if (a.Im == -1) cout << "-i";
      else if (a.Im == 1)
      {
         if (a.Re == 0) cout<<"i";
         else cout<<"+i";
      }
      else
      {
         if (a.Re != 0 && a.Im > 0)
            cout<<"+"<<a.Im<<"i"<<endl;
         else
            cout<<a.Im<<"i"<<endl;
      }
   }
   if (a.Re==0 & a.Im==0)
      cout<<"0"<<endl;
}

Một số thao tác cơ bản với cấu trúc Phân số

Cấu trúc Phân số và Số phức là 2 cấu trúc đơn giản nhất thường được dùng để minh họa kiểu cấu trúc trong C/C++. Thực hành viết các hàm thao tác với các cấu trúc này sẽ giúp quen dần với kiểu cấu trúc và là bước đệm để học lập trình hướng đối tượng. Các ví dụ sẽ được minh họa bằng ngôn ngữ C++.

Trước khi viết các hàm thao tác trên các cấu trúc Phân số, ta cần khai báo cấu trúc như sau:

struct Fraction
{
   int tu;
   int mau;
};

Các thao tác chủ yếu với Fraction:

Xuất một phân số

void OutputFraction(Fraction a)
{
   cout << a.tu <<"/"<<a.mau<<endl;
}

Lấy giá trị phân số

float ValueFraction(Fraction a)
{
   return (float) a.tu / a.mau;
}

Rút gọn phân số
Ta tìm ước chung lớn nhất của tử và mẫu, sau đó lần lượt lấy tử, mẫu chia cho ước chung lớn nhất đó

int UCLN(int a, int b)
{
   if (a < 0) a = -a; //Trường hợp phân số âm
   if (b < 0) b = -b;
   while (a != b)
      a > b ? a -= b : b -= a;
   return a;
}

Fraction ReduceFraction(Fraction a)
{
   int b = UCLN(a.tu, a.mau);
   a.tu /= b;
   a.mau /= b;
   return a;
}

Bảng mã ASCII là gì?

ASCII (American Standard Code for Information Interchange - Chuẩn mã trao đổi thông tin Hoa Kì) là bộ kí tự và bộ mã kí tự dựa trên bảng chữ cái La Tinh được dùng trong tiếng Anh hiện đại và các ngôn ngữ Tây Âu khác. Nó thường được dùng để hiển thị văn bản trong máy tính và các thiết bị thông tin khác. Nó cũng được dùng bởi các thiết bị điều khiển làm việc với văn bản.

Bảng mã ASCII chuẩn có 128 kí tự, gồm các kí tự điều khiển (0 - 31 và 127), các ký tự in được như bảng chữ cái, các dấu (32 - 126). Bảng mã ASCII mở rộng có 255 kí tự gồm 128 ký tự của bảng mã ASCII chuẩn và các chữ có dấu, ký tự trang trí, v.v...

Ở đây giới thiệu bảng mã ASCII mở rộng. Các bảng ASCII mở rộng có thể khác nhau ở các chuẩn khác nhau. Bảng dưới đây tuân theo chuẩn ISO 8859-1, còn gọi là ISO Latin-1, các mã từ 129 - 159 các ký tự mở rộng Microsoft Windows Latin-1 (nguồn: www.ascii-code.com)

Điểm mới của C++ so với C

C++ là một ngôn ngữ được phát triển từ C nên nó thừa hưởng tất cả những đặc tính của ngôn ngữ C. Tuy vậy, C++ cũng có những điểm mới giúp tiện dụng hơn cho người lập trình. Điểm mới quan trọng nhất là C++ đã hỗ trợ hướng đối tượng với các khái niệm class, method,... Bài viết này chủ yếu tập trung vào những điểm khác biệt của C++ so với C.

Chú thích trong C++
C++ cũng dùng 2 kiểu chú thích như C, đó là dấu // cho một dòng và cặp dấu /* .. */ cho một đoạn nhiều dòng. Các cặp dấu /* .. */ không được lồng nhau.
Tuy nhiên, chú thích sau dấu // trong C phải được đặt trên một dòng riêng biệt nhưng trong C++ bạn có thể đặt trên cùng dòng với các câu lệnh.

//Trong C

//Khởi tạo bốn biến.
int a, b, c, d;

//Trong C++

int a, b, c, d; //Khởi tạo bốn biến.

Kiểu dữ liệu và ép kiểu trong C++
C++ có thêm các kiểu dữ liệu mới được dựng sẵn như bool và string.
Ngoài cách ép kiểu số như trong C, người lập trình còn có thể dùng kiểu dữ liệu để ép kiểu như một hàm.

//Trong C

int a = 5;
printf("%f", (float)a);

//Trong C++

int a = 5;
cout << float(a) << endl;

Cách truy cập vào blogspot.com khi bị nhà mạng chặn

Hiện tại có tình trạng tất cả các blog của Blogger (Blogspot) ở tên miền blogspot.com bị một số nhà mạng ở Việt Nam chặn và không thể truy cập được. Nguyên nhân do đâu mình không biết nhưng nó ảnh hưởng không nhỏ đến người dùng mạng Việt Nam bởi họ đã bị chặn truy cập đến một kênh tài nguyên thông tin hữu ích.

Trong bài viết này mình sẽ hướng dẫn các bạn đổi DNS để có thể truy cập vào các blog này.

Đầu tiên, nhấn chuột phải vào biểu tượng mạng dưới Taskbar và chọn Open Network and Sharing Center.

Kế tiếp, chọn Change adapter settings trong cửa sổ Network and Sharing Center.

Trong cửa sổ Network Connections, chuột phải vào kết nối đang sử dụng và chọn Properties.

Một số bài tập cơ bản về ma trận, mảng hai chiều

Dưới đây là một số bài tập về ma trận dành cho các bạn học Nhập môn lập trình tham khảo.
Các ví dụ mình chỉ thao tác với ma trận nguyên bằng ngôn ngữ C, với ma trận thực cũng tương tự

1. Viết hàm nhập một ma trận

//Cách 1: Nhập m, n trong hàm
void InputMatrix(int a[][20], int &m, int &n)
{
   printf("Nhập số hàng m: ");
   scanf("%d", &m);
   printf("Nhập số cột n: ");
   scanf("%d", &n);
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
      {
         printf("A[%d][%d] = ", i, j);
         scanf("%d", &a[i][j]);
      }
}

//Cách 2: Nhập m, n ngoài hàm
void InputMatrix(int a[][20], int m, int n)
{
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
      {
         printf("A[%d][%d] = ", i, j);
         scanf("%d", &a[i][j]);
      }
}

2. Viết hàm xuất một ma trận

void OutputMatrix(int a[][20], int m, int n)
{
   for(int i = 0; i < m; i++)
   {
      for(int j = 0; j < n; j++)
         printf("%d\t", a[i][j]);
      printf("\n");
   }
}

3. Viết hàm tìm giá trị lớn nhất trong ma trận

int MaxOfMatrix(int a[][20], int m, int n)
{
   int max = a[0][0];
   for(int i = 0; i < m; i++)
      for(int j = 0; j < n; j++)
         if(a[i][j]>max)
            max = a[i][j];
   return max;
}

Cấp phát động cho mảng hai chiều trong C++

Mảng 2 chiều khá quen thuộc với chúng ta. Mình sẽ giới thiệu một vài cách cấp phát động mảng 2 chiều để các bạn lựa chọn cho phù hợp. Ở đây mình minh họa bằng C++, đối với các ngôn ngữ khác thì ý tưởng cũng tương tự vậy thôi. Lưu ý là C++ sẽ không tự động thu hồi tài nguyên động đã cấp phát cho dù có thoát khỏi chương trình, vì thế bắt buộc phải có thao tác giải phóng mảng 2 chiều.

Cách 1: Dùng con trỏ cấp 2
Ý tưởng: Để cấp phát động cho mảng 2 chiều, ta cấp phát bộ nhớ của từng chiều theo cú pháp của mảng một chiều. Tức là tạo m mảng 1 chiều, mỗi mảng có n phần tử.

Để làm điều này ta dùng 1 con trỏ cấp 2, cấp phát cho nó m con trỏ cấp 1, mỗi con trỏ cấp 1 ta lại cấp phát n phần tử.

Ví dụ:

int **a = new int*[m];
for(int i = 0; i<m; i++)
   a[i] = new int[n];

Với ví dụ trên, ta được một mảng động hai chiều các số nguyên có kích thước m x n.
Lưu ý là ta dùng một con trỏ cấp 2 cấp phát cho một mảng các phần tử có kiểu int* chứ không phải kiểu int thông thường. Kiểu int* chính là con trỏ cấp 1.

Để giải phóng bộ nhớ động, ta cũng phải giải phóng theo từng cột và từng hàng.

Ví dụ:

for(int i = 0; i<m; i++)
   delete []a[i];
delete []a;

Cách này phức tạp nhưng bạn sẽ có 1 mảng 2 chiều đúng nghĩa và có thể lấy phần tử bằng cách gọi a[i][j] thông thường như mảng tĩnh.

Cách 2: Dùng mảng 1 chiều để biểu diễn mảng 2 chiều
Ý tưởng: Cấp phát mảng 1 chiều có kích thước m x n và truy cập nó như một mảng 2 chiều với các chỉ số thông qua công thức liên hệ.

Phần tử a[i][j] tương ứng với phần tử a[i*n + j] trong mảng.
Ví dụ:

int *a = new int[m*n]; //cấp phát xong
//khởi tạo bằng 0
for(int i = 0; i < m; i++)
   for(int j = 0; j < n; j++)
      a[i*n+j] = 0; 

Việc giải phóng vô cùng đơn giản, chỉ cần 1 lệnh delete.

delete []a;

Với cách này bạn sẽ phải truy cập mảng 2 chiều thông qua công thức liên hệ, tuy nhiên, cách này sẽ hữu ích với những trường hợp như cộng 2 ma trận cùng loại, v.v...

Từ vựng về Windows trong tiếng Nhật

Để đọc được các từ vựng, các bạn phải nắm vững bảng chữ Hiragana và Katakana. Các từ bằng Kanji mình sẽ phiên âm ra Hiragana.

Tiếng Nhật	Hiragana	Tiếng Anh/Nghĩa
デスクトップ		Desktop
コントロールパネル		Control Panel
スタート		Start
フォルダー		Folder
ファイル		File
ごみ箱	ごみばこ	Recycle Bin
タスクバー		Taskbar
最近表示した場所	さいきんひょうじしたばしょ	Recent Places
スリープ		Sleep
シャットダウン		Shutdown
リスタート/再起動	さいきどう	Restart
設定	せってい	Settings

Tên một số ứng dụng:

Nhập xuất cơ bản trong C và C++

C và C++ có sự khác nhau trong nhập xuất dữ liệu lên màn hình. Trong khi C cung cấp hàm printf() và scanf() dùng xuất và nhập có định dạng thì C++ cung cấp các luồng nhập, xuất là cin, cout.

Để sử dụng được printf() và scanf() trong C, bạn phải khai báo thư viện stdio.h. Hai hàm này có thể in và đọc dữ liệu nhập từ màn hình theo các định dạng khác nhau được điều khiển bởi người dùng nên được gọi là các hàm nhập xuất có định dạng.

Hàm printf
Cú pháp: printf("chuỗi điều khiển", danh sách tham số);
Hàm printf() được dùng để hiển thị dữ liệu trên thiết bị xuất chuẩn - console. Danh sách tham số có thể là hằng, biến, biểu thức hay lời gọi hàm và được phân cách bởi dấu phẩy. Mỗi tham số cần có một mã định dạng tương ứng kiểu dữ liệu trong chuỗi điều khiển. Mã định dạng này còn gọi là đặc tả. Một đặc tả gồm dấu % và theo sau là các ký tự c, d, f, lf, ... tương ứng kiểu dữ liệu của tham số.

Ngoài ra trong chuỗi điều khiển còn có thể chứa các lệnh điều khiển theo sau dấu \ hoặc %. Ví dụ: \n để xuống dòng, \\ để in ký tự \, \t để in tab, %% để in dấu %, ...

Ví dụ:

int a = 1, b = 2;
printf("Kết quả: %d\n", a+b);
printf("Cách ");
printf("khác:\n");
printf("%d + %d = %d\n", a, b, a+b);

Kết quả:
Kết quả: 3
Cách khác: 
1 + 2 = 3

Từ vựng về Tin học tiếng Nhật

Để đọc được các từ vựng này các bạn phải nắm thật vững bảng chữ Hiragana và Katakana (yêu cầu tối thiểu khi học tiếng Nhật). Đa số các từ vựng về Tin học được mượn từ nước ngoài nên được viết bằng Katakana. Tuy vậy một số từ được viết bằng Kanji và mình sẽ phiên âm ra Hiragana.

Tiếng Nhật	Hiragana	Tiếng Anh/Nghĩa
パソコン		Personal Computer/Máy tính cá nhân
コンピューター		Computer/Máy tính
タブレット		Tablet/Máy tính bảng
マウス		Mouse/Chuột
キーボード		Keyboard/Bàn phím
ラップトップ		Laptop
ソフトウェア		Software/Phần mềm
ハードウェア		Hardware/Phần cứng
デバイス		Device/Thiết bị
ゲーム		Game
サウンド		Sound/Âm thanh
システム		System/Hệ thống
オペレーティング・システム		Operating system/Hệ điều hành
バッテリ		Battery/Pin
モニター画面	がめん	Monitor screen/Màn hình
センサー		Sensor/Cảm biến
スキャン		Scan/Máy quét
カメラ		Camera

Cấp phát động trong C/C++

Bộ nhớ động có lợi hơn bộ nhớ tĩnh rất nhiều, có thể cấp phát thêm hoặc thu hồi lại bộ nhớ. Do đó, bộ nhớ động rất linh hoạt và tiết kiệm hơn so với sử dụng bộ nhớ tĩnh. Một mảng động chứa các phần tử được cấp phát bộ nhớ động, do đó có thể thêm phần tử, xoá phần tử,... nên quản lý bộ nhớ hiệu quả hơn.

Ngôn ngữ C cung cấp cho chúng ta 4 hàm: malloc, calloc , realloc để cấp phát và free để thu hồi. C++ cung cấp 2 toán tử: new để cấp phát và delete để thu hồi. Do C/C++ không có chế độ thu hồi tự động nên khi ta cấp phát động thì ta phải có thu hồi bộ nhớ động.

Trong C, bốn hàm malloc, calloc, realloc và free nằm trong thư viện stdlib.h hoặc alloc.h, trước khi sử dụng các bạn phải khai báo thư viện này.

Hàm malloc
Cú pháp: void* malloc(size_t size);
Ý nghĩa: Cấp phát vùng nhớ động có kích thức size byte.

Để đảm bảo cấp phát đủ bộ nhớ cho một mảng, ta thường sử dụng malloc(n*sizeof(data_type)) với n là số phần tử. Toán tử sizeof(kiểu_dữ_liệu) trả về kích thước của kiểu dữ liệu (do kích cỡ một kiểu dữ liệu không cố định ở những kiến trúc máy tính khác nhau).
Với một mảng có kiểu dữ liệu xác định nên ta phải ép kiểu để phù hợp với kiểu dữ liệu của mảng.
Hàm malloc chỉ cấp phát mà không khởi tạo giá trị ban đầu cho các biến.

Ví dụ:
Code C:

//cấp phát mảng động kiểu int với 5 phần tử
int *p = (int*)malloc(5*sizeof(int));

//cấp phát chuỗi động có 11 phần tử
char *str = (char*)malloc(11*sizeof(char));

Cách khởi tạo số ngẫu nhiên trong C/C++

Khởi tạo số ngẫu nhiên thường được dùng để giảm bớt công đoạn nhập số cho mảng một chiều, ma trận,... Để khởi tạo số ngẫu nhiên ta cần biết đến hàm srand() và rand() trong stdlib.h. Trong C++ 2 hàm này có sẵn trong iostream.

Hàm srand
Cú pháp: void srand (unsigned int seed);
Dùng để khởi tạo một số ngẫu nhiên theo một số seed. Số ngẫu nhiên được tạo là pseudo-random, tức là số ngẫu nhiên giả, có thể đoán được số kế tiếp. Mỗi một số seed sẽ cho ra một bộ số random khác nhau.
Để cho mỗi số seed khác nhau người ta thường dùng kèm với unsigned int time(NULL) trong thư viện time.h, hàm time(NULL) trả về số giây đã trôi qua kể từ ngày 1/1/1970.
Hàm srand() thường được gọi trước khi gọi hàm rand().

Hàm rand
Cú pháp: int rand(void);
Trả về một số nguyên random giả trong khoảng từ 0 đến RAND_MAX. Hằng RAND_MAX được định nghĩa trong stdlib.h đảm bảo ít nhất bằng 32767.
Nếu chỉ dùng hàm rand() thì sẽ cho ra những số random giống nhau mỗi lần chạy, vì vậy người ta thường khai báo srand(time(NULL)) trước để kết quả random mỗi lần mỗi khác nhau.

Một số bài tập cơ bản về mảng một chiều

Hầu hết những bài tập dưới đây là rất cơ bản dành cho các bạn mới học Nhập môn lập trình tham khảo.

1. Viết hàm nhập mảng một chiều các số nguyên
Phải luôn luôn định trước số phần tử cần dùng cho mảng. Trong C/C++, mảng được đánh chỉ số từ 0.
Nếu là mảng các số thực chỉ việc thay int a[] thành float a[] và đổi mã đặc tả của hàm scanf trong vòng lặp thành %f.
Code C:

//Cách 1: Nhập n trong hàm nhập mảng
void InputArray1(int a[], int &n)
{
   printf("Nhập số phần tử: ");
   scanf("%d", &n);
   for(int i = 0; i < n; i++);
   {
      printf("A[%d] = ", i);
      scanf("%d", &a[i]);
   }
}

//Cách 2: Nhập n ngoài hàm nhập mảng
void InputArray2(int a[], int n)
{
   for(int i = 0; i < n; i++)
   {
      printf("A[%d] = ", i);
      scanf("%d", &a[i]);
   }
}

2. Viết hàm xuất mảng một chiều các số nguyên
Code C:

void OutputArray(int a[], int n)
{
   for(int i = 0; i < n; i++)
      printf("%d\t", a[i]);
}

Các vấn đề cơ bản về số nguyên tố trong lập trình

Số nguyên tố là số chỉ có 2 ước, đó là 1 và chính nó, tức là nó chỉ chia hết cho số 1 và chính nó. Số 1 và 0 không được coi là số nguyên tố. Các bài toán cơ bản về số nguyên tố gồm kiểm tra một số nguyên n có phải là số nguyên tố và tìm các số nguyên tố nhỏ hơn hoặc bằng một số nguyên cho trước.

Kiểm tra một số nguyên có là số nguyên tố
Ý tưởng: Kiểm tra xem số n có chia hết cho từng số nhỏ hơn nó hay không. Nếu có thì không là số nguyên tố, nếu tất cả đều không có thì là số nguyên tố.

Cài đặt bằng C: Nếu số n là 1 hoặc 0 thì không là số nguyên tố. Dùng một vòng for chạy từ 2 đến n-1 để kiểm tra xem n có chia hết cho bất kỳ số nào trong đó không, nếu có thỉ không là số nguyên tố, nếu tất cả đều không thì là số nguyên tố. Trong một hàm nếu gặp lệnh return, hàm sẽ trả về giá trị và kết thúc hàm nên có thể viết gọn như sau:

int IsPrime(int n)
{
   if (n < 2) return 0;
   for(int i = 2; i < n; i++)
      if(n%i==0) return 0; 
   return 1; 
}

Tuy nhiên có thể nhận thấy việc kiểm tra đến n-1 là không cần thiết. Vì nếu n có các ước thì các ước của nó chắc chắn không vượt qua căn bậc 2 của n. Như vậy điều kiện trong vòng for sẽ được đổi thành i <= sqrt(n), nhưng để gọi hàm sqrt() cần phải khai báo thư viện math.h, ép kiểu n sang kiểu thực,... khá rườm rà nên ta có thể đổi thành i*i <= n để tiện hơn.

Các hàm xử lý chuỗi trong C

C cung cấp rất nhiều hàm xử lý chuỗi và tất cả đều nằm trong thư viện string.h nên trước khi dùng cần phải khai báo bằng từ khoá #include.
Các hàm thường được dùng phổ biến:

strlen
Cú pháp: unsigned int strlen(const char *str);
Chức năng: Trả về độ dài của chuỗi. Độ dài chuỗi được xác định bởi ký tự null nên không bị nhầm lẫn với chiều dài mảng ký tự.
Ví dụ: char str[100]="abcd";
Hàm strlen(str) sẽ trả về 4, trong khi toán tử sizeof(str) trả về 100.

Code C:

//Ví dụ về hàm strlen
#include<stdio.h>
#include<string.h>

void main()
{
   char str[100];
   printf("Nhập chuỗi: ");
   gets(str);
   printf("Độ dài chuỗi: %d", strlen(str));
}

strcpy
Cú pháp: char* strcpy(char *destination, const char *source);
Chức năng: Sao chép chuỗi source vào chuỗi destination và trả về chuỗi destination. Lưu ý chuỗi destination phải có kích thước bằng hoặc lớn hơn chuỗi source và chưa có giá trị nào.