Đ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--;
}