Bài viết này khám phá một loạt các bài tập lập trình cơ bản bằng ngôn ngữ C, bao gồm các thuật toán xử lý dữ liệu số, tính toán số học, và các kỹ thuật lập trình đệ quy. Mỗi phần trình bày một vấn đề, giải pháp bằng mã C, và phân tích các khía cạnh quan trọng của việc triển khai.
Bài tập 1: Chuyển đổi điểm số thành xếp loại
Chức năng chính là chuyển đổi một điểm số nguyên thành một ký tự xếp loại (ví dụ: 'A', 'B', 'C', 'D', 'E').
Mô tả chức năng
Hàm nhận vào một số nguyên (điểm số) và trả về một ký tự (xếp loại). Quy tắc xếp loại thông thường là:
- 90-100: A
- 80-89: B
- 70-79: C
- 60-69: D
- Dưới 60: E
Mã nguồn ví dụ
#include <stdio.h>
// Khai báo nguyên mẫu hàm chuyển đổi điểm số thành xếp loại
char xacDinhXepLoai(int diemThi);
int main() {
int diemNhap;
char loaiKetQua;
// Đọc điểm số cho đến khi gặp EOF (End Of File)
while (scanf("%d", &diemNhap) != EOF) {
loaiKetQua = xacDinhXepLoai(diemNhap);
printf("Diem so: %d, Xep loai: %c\n\n", diemNhap, loaiKetQua);
}
return 0;
}
// Định nghĩa hàm xác định xếp loại từ điểm số
char xacDinhXepLoai(int diemThi) {
// Sử dụng cấu trúc switch để xác định xếp loại dựa trên điểm số
// Chia cho 10 để nhóm các khoảng điểm
switch (diemThi / 10) {
case 10:
case 9:
return 'A'; // Điểm từ 90 trở lên
case 8:
return 'B'; // Điểm từ 80 đến 89
case 7:
return 'C'; // Điểm từ 70 đến 79
case 6:
return 'D'; // Điểm từ 60 đến 69
default:
return 'E'; // Điểm dưới 60
}
}
Phân tích và lưu ý
Trong hàm xacDinhXepLoai, chúng ta sử dụng toán tử chia nguyên diemThi / 10 để lấy chữ số hàng chục của điểm số, giúp nhóm các khoảng điểm lại với nhau. Cấu trúc switch sau đó so khớp giá trị này với các trường hợp cụ thể. Khi một case khớp và hàm return ngay lập tức, không cần lệnh break vì hàm đã thoát.
Một điểm quan trọng khác là việc sử dụng dấu nháy đơn ' ' cho các ký tự đơn lẻ (kiểu char), ví dụ: 'A'. Dấu nháy kép " " được sử dụng cho chuỗi ký tự (kiểu char* hoặc const char*).
Bài tập 2: Tính tổng các chữ số của một số nguyên
Bài tập này yêu cầu tính tổng các chữ số của một số nguyên dương.
Mô tả chức năng
Hàm tongCacChuSo nhận một số nguyên soNguyen và trả về tổng các chữ số của nó. Ví dụ, nếu soNguyen = 456, hàm sẽ trả về 4 + 5 + 6 = 15.
Mã nguồn ví dụ (Phiên bản lặp)
#include <stdio.h>
// Khai báo nguyên mẫu hàm
int tinhTongChuSoLap(int soNguyen);
int main() {
int giaTriDauVao;
int ketQuaTong;
printf("Nhap so nguyen (Ctrl+D de thoat):\n");
while (scanf("%d", &giaTriDauVao) != EOF) {
ketQuaTong = tinhTongChuSoLap(giaTriDauVao);
printf("Tong cac chu so cua %d la: %d\n\n", giaTriDauVao, ketQuaTong);
printf("Nhap so nguyen (Ctrl+D de thoat):\n");
}
return 0;
}
// Định nghĩa hàm tính tổng chữ số bằng phương pháp lặp
int tinhTongChuSoLap(int soNguyen) {
int tongChuSo = 0;
int bienTam = soNguyen; // Sử dụng biến tạm để không làm thay đổi giá trị gốc
// Lặp cho đến khi số bằng 0
while (bienTam != 0) {
tongChuSo += bienTam % 10; // Lấy chữ số cuối cùng và cộng vào tổng
bienTam /= 10; // Loại bỏ chữ số cuối cùng
}
return tongChuSo;
}
Mã nguồn ví dụ (Phiên bản đệ quy)
Một cách tiếp cận khác cho vấn đề này là sử dụng đệ quy, phân tách vấn đề thành các bài toán con nhỏ hơn.
#include <stdio.h>
// Khai báo nguyên mẫu hàm đệ quy
int tinhTongChuSoDeQuy(int soNguyen);
// Hàm main tương tự như trên, chỉ cần thay đổi lời gọi hàm
// int main() { ... }
// Định nghĩa hàm tính tổng chữ số bằng phương pháp đệ quy
int tinhTongChuSoDeQuy(int soNguyen) {
if (soNguyen == 0) {
return 0; // Điều kiện dừng: nếu số là 0, tổng là 0
} else {
// Cộng chữ số cuối cùng với tổng các chữ số của phần còn lại của số
return (soNguyen % 10) + tinhTongChuSoDeQuy(soNguyen / 10);
}
}
Phân tích và so sánh
Cả hai phương pháp lặp và đệ quy đều có thể giải quyết bài toán tính tổng các chữ số. Phương pháp lặp (sử dụng vòng lặp while) thực hiện các bước tuần tự cho đến khi điều kiện dừng được thỏa mãn. Phương pháp đệ quy giải quyết vấn đề bằng cách gọi chính nó với một phiên bản nhỏ hơn của vấn đề ban đầu, cho đến khi đạt được điều kiện cơ sở (base case).
Về mặt hiệu quả, trong C, phương pháp lặp thường có hiệu suất tốt hơn một chút do tránh được chi phí gọi hàm của đệ quy. Tuy nhiên, phương pháp đệ quy đôi khi có thể dẫn đến mã nguồn ngắn gọn và dễ hiểu hơn cho một số vấn đề nhất định.
Bài tập 3: Hàm tính lũy thừa (x^n)
Bài tập này triển khai hàm tính x mũ n (xn) một cách hiệu quả bằng đệ quy.
Mô tả chức năng
Hàm tinhLuyThuaNhanh nhận hai số nguyên base (x) và exponent (n), và trả về kết quả baseexponent.
Mã nguồn ví dụ
#include <stdio.h>
// Khai báo nguyên mẫu hàm tính lũy thừa
int tinhLuyThuaNhanh(int base, int exponent);
int main() {
int giaTriCoSo, giaTriSoMu;
int ketQuaTinhToan;
printf("Nhap gia tri co so va so mu (Ctrl+D de thoat):\n");
while (scanf("%d%d", &giaTriCoSo, &giaTriSoMu) != EOF) {
ketQuaTinhToan = tinhLuyThuaNhanh(giaTriCoSo, giaTriSoMu);
printf("%d mu %d la: %d\n\n", giaTriCoSo, giaTriSoMu, ketQuaTinhToan);
printf("Nhap gia tri co so va so mu (Ctrl+D de thoat):\n");
}
return 0;
}
// Định nghĩa hàm tính lũy thừa bằng đệ quy hiệu quả
int tinhLuyThuaNhanh(int base, int exponent) {
// Điều kiện cơ sở: bất kỳ số nào mũ 0 đều bằng 1
if (exponent == 0) {
return 1;
}
// Nếu số mũ là số lẻ
else if (exponent % 2 == 1) {
return base * tinhLuyThuaNhanh(base, exponent - 1);
}
// Nếu số mũ là số chẵn
else {
// Tối ưu hóa: tính (base^(exponent/2)) chỉ một lần
int ketQuaPhu = tinhLuyThuaNhanh(base, exponent / 2);
return ketQuaPhu * ketQuaPhu;
}
}
Phân tích
Hàm tinhLuyThuaNhanh sử dụng đệ quy để tính toán. Nó có ba trường hợp:
- Nếu
exponentbằng 0, kết quả là 1 (điều kiện dừng). - Nếu
exponentlà số lẻ, thì xn = x * x(n-1). - Nếu
exponentlà số chẵn, thì xn = (xn/2) * (xn/2). Cách này giúp giảm số lượng phép nhân, đặc biệt hiệu quả với các số mũ lớn, bằng cách tínhxn/2chỉ một lần và nhân nó với chính nó.
Đây là một ví dụ điển hình về việc sử dụng đệ quy để tối ưu hóa tính toán.
Bài tập 4: Tìm cặp số nguyên tố sinh đôi
Bài tập này yêu cầu tìm các cặp số nguyên tố sinh đôi trong một phạm vi nhất định.
Mô tả chức năng
Một cặp số nguyên tố sinh đôi là hai số nguyên tố có hiệu bằng 2 (ví dụ: (3, 5), (5, 7)). Chúng ta cần viết một hàm để kiểm tra xem một số có phải là số nguyên tố hay không, và sau đó sử dụng hàm đó để tìm các cặp số nguyên tố sinh đôi trong phạm vi 1 đến 100.
Mã nguồn ví dụ
#include <stdio.h>
#include <math.h> // Cần cho hàm sqrt()
// Khai báo nguyên mẫu hàm kiểm tra số nguyên tố
int kiemTraNguyenTo(int number);
int main() {
int demSoCap = 0;
printf("Cac cap so nguyen to sinh doi trong pham vi 100:\n");
// Lặp qua các số từ 2 đến 98 để tìm cặp (i, i+2)
for (int num = 2; num <= 98; num++) {
if (kiemTraNguyenTo(num) && kiemTraNguyenTo(num + 2)) {
printf("(%d, %d)\n", num, num + 2);
demSoCap++;
}
}
printf("Tong cong co %d cap so nguyen to sinh doi trong pham vi 100.\n", demSoCap);
return 0;
}
// Định nghĩa hàm kiểm tra số nguyên tố
// Trả về 1 nếu là số nguyên tố, 0 nếu không
int kiemTraNguyenTo(int number) {
if (number <= 1) { // Số nhỏ hơn hoặc bằng 1 không phải số nguyên tố
return 0;
}
// Chỉ cần kiểm tra các ước số đến căn bậc hai của số đó
for (int divisor = 2; divisor <= sqrt(number); divisor++) {
if (number % divisor == 0) {
return 0; // Nếu có ước số, không phải số nguyên tố
}
}
return 1; // Không tìm thấy ước số nào, là số nguyên tố
}
Phân tích
Hàm kiemTraNguyenTo là trọng tâm của bài tập này. Nó kiểm tra một số n có phải là số nguyên tố hay không bằng cách lặp từ 2 đến căn bậc hai của n. Nếu tìm thấy bất kỳ ước số nào trong phạm vi này, số đó không phải là số nguyên tố. Việc kiểm tra chỉ đến căn bậc hai là một tối ưu hóa quan trọng vì các ước số luôn xuất hiện theo cặp, và một trong số chúng sẽ nhỏ hơn hoặc bằng căn bậc hai của số đó.
Trong hàm main, chúng ta lặp qua các số từ 2 đến 98. Với mỗi số num, chúng ta kiểm tra xem cả num và num+2 có phải là số nguyên tố hay không. Nếu cả hai đều đúng, chúng ta đã tìm thấy một cặp số nguyên tố sinh đôi.
Bài tập 5: Tháp Hà Nội
Tháp Hà Nội là một bài toán cổ điển trong khoa học máy tính, thường được dùng để minh họa khái niệm đệ quy.
Mô tả bài toán
Bài toán bao gồm ba cọc và một số đĩa có kích thước khác nhau, có thể trượt qua bất kỳ cọc nào. Mục tiêu là di chuyển toàn bộ chồng đĩa từ cọc nguồn sang cọc đích, tuân thủ các quy tắc sau:
- Chỉ có thể di chuyển một đĩa tại một thời điểm.
- Mỗi lần di chuyển bao gồm việc lấy đĩa trên cùng từ một cọc và đặt nó lên một cọc khác.
- Không được đặt đĩa lớn hơn lên trên đĩa nhỏ hơn.
Mã nguồn ví dụ
#include <stdio.h>
// #include <stdlib.h> // Cho system("pause") nếu cần trên Windows
// Khai báo nguyên mẫu hàm
void chuyenMotDia(unsigned int maDia, char cotBatDau, char cotKetThuc);
void giaiThapHaNoi(unsigned int soLuongDia, char cotBatDau, char cotTrungGian, char cotKetThuc);
// Biến toàn cục để đếm tổng số bước di chuyển
unsigned long long demBuocDiChuyen = 0;
int main() {
unsigned int soDiaMuonGiai;
printf("Nhap so luong dia: ");
scanf("%u", &soDiaMuonGiai);
printf("Cac buoc di chuyen:\n");
giaiThapHaNoi(soDiaMuonGiai, 'A', 'B', 'C'); // A là nguồn, B là trung gian, C là đích
printf("Tong cong da di chuyen %llu lan.\n", demBuocDiChuyen);
// system("pause"); // Dùng cho Windows để giữ cửa sổ console
return 0;
}
// Hàm in ra bước di chuyển của một đĩa
void chuyenMotDia(unsigned int maDia, char cotBatDau, char cotKetThuc) {
printf("Chuyen dia %u tu cot %c den cot %c\n", maDia, cotBatDau, cotKetThuc);
demBuocDiChuyen++; // Tăng biến đếm mỗi khi một đĩa được di chuyển
}
// Hàm giải bài toán Tháp Hà Nội bằng đệ quy
void giaiThapHaNoi(unsigned int soLuongDia, char cotBatDau, char cotTrungGian, char cotKetThuc) {
if (soLuongDia == 1) {
// Nếu chỉ có một đĩa, di chuyển trực tiếp từ nguồn đến đích
chuyenMotDia(soLuongDia, cotBatDau, cotKetThuc);
} else {
// 1. Di chuyển (n-1) đĩa từ cọc bắt đầu sang cọc trung gian, sử dụng cọc kết thúc làm cọc tạm
giaiThapHaNoi(soLuongDia - 1, cotBatDau, cotKetThuc, cotTrungGian);
// 2. Di chuyển đĩa lớn nhất (thứ n) từ cọc bắt đầu sang cọc kết thúc
chuyenMotDia(soLuongDia, cotBatDau, cotKetThuc);
// 3. Di chuyển (n-1) đĩa từ cọc trung gian sang cọc kết thúc, sử dụng cọc bắt đầu làm cọc tạm
giaiThapHaNoi(soLuongDia - 1, cotTrungGian, cotBatDau, cotKetThuc);
}
}
Phân tích giải pháp đệ quy
Giải pháp cho Tháp Hà Nội là đệ quy một cách tự nhiên. Để di chuyển n đĩa từ cọc nguồn sang cọc đích:
- Di chuyển
n-1đĩa từ cọc nguồn sang cọc trung gian. - Di chuyển đĩa thứ
n(đĩa lớn nhất) từ cọc nguồn sang cọc đích. - Di chuyển
n-1đĩa từ cọc trung gian sang cọc đích.
Điều kiện dừng của đệ quy là khi chỉ có một đĩa, đĩa đó có thể di chuyển trực tiếp từ cọc nguồn sang cọc đích. Số bước di chuyển tối thiểu cho n đĩa là 2n - 1.
Bài tập 6: Tính số tổ hợp chập k của n (C(n, k))
Bài tập này giới thiệu hai phương pháp để tính số tổ hợp chập k của n (ký hiệu C(n, k) hoặc "n chọn k").
Mô tả bài toán
Số tổ hợp C(n, k) đại diện cho số cách chọn k phần tử từ một tập hợp gồm n phần tử phân biệt, không xét thứ tự. Công thức toán học cho C(n, k) là n! / (k! * (n-k)!).
Phương pháp 1: Tính toán bằng giai thừa (Lặp)
Phương pháp này trực tiếp áp dụng công thức giai thừa.
#include <stdio.h>
// Hàm tính giai thừa
long long tinhGiaiThua(int so) {
long long ketQua = 1;
for (int i = 1; i <= so; i++) {
ketQua *= i;
}
return ketQua;
}
// Hàm tính tổ hợp chập k của n
long long tinhToHopVoiGiaiThua(int n, int k) {
if (k < 0 || k > n) {
return 0; // Trường hợp không hợp lệ
}
// Sử dụng công thức C(n, k) = n! / (k! * (n-k)!)
return tinhGiaiThua(n) / (tinhGiaiThua(k) * tinhGiaiThua(n - k));
}
int main() {
int giaTriN, giaTriK;
long long ketQuaToHop;
printf("Nhap n va k (Ctrl+D de thoat):\n");
while (scanf("%d%d", &giaTriN, &giaTriK) != EOF) {
ketQuaToHop = tinhToHopVoiGiaiThua(giaTriN, giaTriK);
printf("C(%d, %d) = %lld (phuong phap giai thua)\n\n", giaTriN, giaTriK, ketQuaToHop);
printf("Nhap n va k (Ctrl+D de thoat):\n");
}
return 0;
}
Phương pháp 2: Sử dụng công thức đệ quy Pascal
Công thức đệ quy dựa trên tam giác Pascal: C(n, k) = C(n-1, k) + C(n-1, k-1).
#include <stdio.h>
// Hàm tính tổ hợp chập k của n bằng đệ quy
int tinhToHopDeQuy(int n, int k) {
// Các điều kiện cơ sở
if (k == 0 || k == n) {
return 1; // C(n, 0) = 1, C(n, n) = 1
}
if (k > n) {
return 0; // Trường hợp không hợp lệ, không thể chọn nhiều hơn số phần tử có sẵn
}
// Công thức đệ quy Pascal
return tinhToHopDeQuy(n - 1, k) + tinhToHopDeQuy(n - 1, k - 1);
}
int main() {
int giaTriN, giaTriK;
int ketQuaToHop;
printf("Nhap n va k (Ctrl+D de thoat):\n");
while (scanf("%d%d", &giaTriN, &giaTriK) != EOF) {
ketQuaToHop = tinhToHopDeQuy(giaTriN, giaTriK);
printf("C(%d, %d) = %d (phuong phap de quy Pascal)\n\n", giaTriN, giaTriK, ketQuaToHop);
printf("Nhap n va k (Ctrl+D de thoat):\n");
}
return 0;
}
So sánh hai phương pháp
Phương pháp giai thừa (lặp) dễ hiểu hơn vì nó trực tiếp ánh xạ với công thức toán học. Tuy nhiên, nó có thể gặp vấn đề tràn số (overflow) nhanh chóng khi n lớn, vì giai thừa của các số lớn tăng rất nhanh. Kiểu dữ liệu long long giúp mở rộng phạm vi nhưng vẫn có giới hạn.
Phương pháp đệ quy Pascal tránh được vấn đề tràn số giai thừa nhưng có thể kém hiệu quả hơn về mặt thời gian tính toán cho các giá trị n và k lớn do tính toán lặp lại các giá trị con (overlapping subproblems). Nó thường được minh họa trong việc xây dựng tam giác Pascal.
Bài tập 7: Vẽ hình mẫu ký tự
Bài tập này sử dụng các vòng lặp lồng nhau để in ra một hình mẫu ký tự dạng kim tự tháp ngược với các ký tự " O ", "<H>", "I I".
Mô tả hình mẫu
Hình mẫu được tạo thành từ ba dòng ký tự cho mỗi "tầng", tạo thành một cấu trúc giống người tuyết hoặc hình nhân đơn giản, và lặp lại theo kiểu kim tự tháp ngược, nghĩa là số lượng hình nhân giảm dần theo mỗi tầng.
Mã nguồn ví dụ
#include <stdio.h>
// Hàm in hình mẫu
void inHinhKimTuThapNguoc(int soHang);
int main() {
int soCotLuaChon;
printf("Nhap so hang cho hinh mau: ");
scanf("%d", &soCotLuaChon);
inHinhKimTuThapNguoc(soCotLuaChon);
return 0;
}
void inHinhKimTuThapNguoc(int soHang) {
int hangHienTai, cotHienTai;
// Vòng lặp ngoài duyệt qua từng hàng của hình kim tự tháp ngược
for (hangHienTai = 0; hangHienTai < soHang; hangHienTai++) {
// In khoảng trắng để căn lề (tạo hiệu ứng lùi vào)
for (cotHienTai = 0; cotHienTai < hangHienTai; cotHienTai++) {
printf("\t");
}
// Dòng thứ nhất: "O" (đầu)
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai; cotHienTai++) {
printf(" O \t");
}
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai - 1; cotHienTai++) {
printf(" O \t");
}
printf("\n");
// In khoảng trắng để căn lề
for (cotHienTai = 0; cotHienTai < hangHienTai; cotHienTai++) {
printf("\t");
}
// Dòng thứ hai: "<H>" (thân)
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai; cotHienTai++) {
printf("<H>\t");
}
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai - 1; cotHienTai++) {
printf("<H>\t");
}
printf("\n");
// In khoảng trắng để căn lề
for (cotHienTai = 0; cotHienTai < hangHienTai; cotHienTai++) {
printf("\t");
}
// Dòng thứ ba: "I I" (chân)
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai; cotHienTai++) {
printf("I I\t");
}
for (cotHienTai = 0; cotHienTai < soHang - hangHienTai - 1; cotHienTai++) {
printf("I I\t");
}
printf("\n\n"); // Hai dòng xuống để tạo khoảng cách giữa các tầng
}
}
Phân tích
Hàm inHinhKimTuThapNguoc sử dụng các vòng lặp lồng nhau để tạo ra hình mẫu. Vòng lặp ngoài (for (hangHienTai = 0; hangHienTai < soHang; hangHienTai++)) kiểm soát số lượng hàng (tầng) được in.
Bên trong vòng lặp này, có ba nhóm vòng lặp con, mỗi nhóm chịu trách nhiệm in một dòng của hình nhân:
- Vòng lặp đầu tiên in các ký tự khoảng trắng (
\t) để tạo hiệu ứng thụt lề, số lượng khoảng trắng tăng dần theo mỗi hàng (hangHienTai). - Các vòng lặp tiếp theo in các phần của hình nhân (" O ", "<H>", "I I"). Số lượng ký tự này giảm dần theo mỗi hàng, tạo ra hình dạng kim tự tháp ngược.
Dòng printf("\n\n") ở cuối mỗi tầng giúp tạo khoảng cách rõ ràng giữa các nhóm hình nhân, làm cho mẫu dễ đọc hơn.