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.

Dạng 2: Tư duy logic

Mỗi bài tập của dạng này sẽ có một cách làm riêng, chủ yếu liên quan đến công thức toán học.

Bài 1: Kiểm tra số n có phải số nguyên tố.
Hướng làm: Có thể xem bài viết đầy đủ để hiểu thêm về các giải thuật nâng cao: Các vấn đề về số nguyên tố trong lập trình.

bool LaSoNguyenTo(int n)
{
   if (n < 2) return false;
   for(int i = 2; i * i <= n; i++)
      if (n % i == 0)
         return false;
   return true;
}

Bài 2: Tìm ước chung lớn nhất của 2 số nguyên, bội chung nhỏ nhất của 2 số nguyên dương.
Hướng làm: Để tìm ƯCLN, ta so sánh 2 số a và b nếu a > b thì lấy a = a - b ngược lại b = b - a, dừng khi a = b. Để tìm BCNN của a và b ta lấy a * b / UCLN(a,b).

int UCLN(int a, int b)
{
   while (a != b)
   {
      if (a > b)
         a -= b;
      else
         b -= a;
   }
   return a;
}

int BCNN(int a, int b)
{
   int bcnn = a * b;
   while (a != b)
   {
      if (a > b)
         a -= b;
      else
         b -= a;
   }
   return bcnn / a;
}

VẤN ĐỀ? Tìm ƯCLN của 2 số âm? Ta thấy dấu âm không liên quan gì đến việc nó có chia hết cho cùng một số hay không nhưng kết quả sẽ bị lặp vô tận nếu bạn không tính đến trường hợp này. Vì vậy để giải quyết, ta chuyển thành số dương và tính như bình thường. Điều này đặc biệt quan trọng nếu bạn áp dụng ƯCLN vào việc tính toán với phân số âm.

int UCLN(int a, int b)
{
   if (a < 0) a = -a;
   if (b < 0) b = -b;
   while (a != b)
   {
      if (a > b)
         a -= b;
      else
         b -= a;
   }
   return a;
}

Bài 3: Phân tích thừa số nguyên tố của một số dương n. Ví dụ: 20 = 2*2*5
Hướng làm: Kiểm tra từ i = 2, nếu n chia hết cho i thì in ra màn hình, đồng thời chia n cho i để xét tiếp. Tuy nhiên, phải lặp lại để kiểm tra lại một lần nữa với số i để giải quyết hết thừa số nguyên tố trùng.

void PhanTichThuaSoNT(int n)
{
   int i = 2;
   while (n != 0)
   {
      if (n%i == 0)
      {
         n /= i;
         printf("%d", i);
         if (n != 1)
            printf("*");
      }
      else 
         i++;   
   }
}

Bài 4: In ra màn hình giá trị nhị phân của một số nguyên n gồm tối đa 10 chữ số (4 bytes).
Hướng làm: Có nhiều cách làm bài này: dùng chuỗi, mảng, ... Ở mức độ Nhập môn lập trình, mình hướng dẫn cách làm bằng mảng. Cách tìm là chia dư cho 2 gán vào mảng và xuất theo thứ tự ngược lại. Số yêu cầu có 4 bytes nên ta khai báo mảng 32 phần tử lưu 32 bit nhị phân.

void Binary(int a)
{
   int b[32], n = 0;
   for (int i = 0; a > 0; n++, i++, a/=2)
      b[i] = a % 2;
   for (int i = n - 1; i >= 0; i--)
      printf("%d", b[i]);
}

Bài 5: Đếm ước số của số nguyên dương n.
Hướng làm: Một số dương n chỉ có ước trong khoảng 1 đến n/2 và chính nó. Vì vậy ta sẽ kiểm tra sự chia hết trong khoảng này.

int DemUoc(int a)
{
   int dem = 0;
   for (int i = 1; i <= a / 2; i++)
      if (a % i == 0)
         dem++;         
   return dem + 1;
}

Bài 6: Liệt kê các số hoàn thiện nhỏ hơn n. Biết số hoàn thiện là một số có tổng các ước số của nó (không kể nó) bằng chính nó. Ví dụ: 6 là số hoàn thiện vì tổng các ước 1+2+3 = 6.
Hướng làm: Vì 2 và 3 là số nguyên tố chỉ có ước là 1 và chính nó nên ta kiểm tra từ 4 đến n. Tính tổng các ước của từng số, số nào thỏa điều kiện thì in ra.

void SoHoanThien(int n)
{
   
   for (int i = 4; i <= n; i++)
   {
      int sum = 0;
      for (int j = 1; j <= i / 2; j++)
         if (i % j == 0)
            sum += j;
      if (sum == i)
         printf("%d ", i);            
   }
}

Bài 7: In dãy Fibonaci đến n.
Hướng làm: Dãy Fibonaci là một dãy số mà số thứ 3 bằng tổng của 2 số trước. Vì vậy ta dùng 3 biến để luân phiên nhau tính toán.

void Fibonaci(int n)
{
   int x1 = 1, x2 = 1, x3;
   while (x1 <= n)
   {
      printf("%d ", x1);
      x3 = x1 + x2;
      x1 = x2;
      x2 = x3;
   } 
}

Bài 8: In bảng cửu chương từ 2 đến 9.
Hướng làm: Bài này chắc quá dễ rồi ^^. Dùng biến i để chỉ bảng, biến j để chỉ thừa số. Muốn hiển thị bảng 2 đến bảng 9 thì cho i chạy từ 2 đến 9, muốn hiển thị thừa số trong bảng từ 2 đến 9 thì cũng cho j chạy từ 2 đến 9 và in biểu thức ra thôi.

void BangCuuChuong()
{
   for (int i = 2; i <= 9; i++)
   {
      printf("Bang cuu chuong %d\n", i);
      for (int j = 2; j <= 9; j++)
         printf("%d x %d = %d\n", i, j, i*j);
      printf("\n");
   }
}

Mình sẽ cập nhật thêm các bài tập nếu tìm thấy đề bài hay thuộc dạng này.