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.

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

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!

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

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

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.