Bài tập C: hàm, mảng và chuỗi

Luyện viết hàm, làm việc với mảng và chuỗi ký tự. Nhớ rằng C luôn truyền tham số theo giá trị, muốn sửa biến gốc thì phải truyền con trỏ. Tự viết code trước, bí thì mở Gợi ý.

Bài 1: hàm hoán đổi hai số qua con trỏ

Viết hàm hoan_doi nhận hai số nguyên và tráo giá trị của chúng, sao cho sau khi gọi hàm trong main thì hai biến gốc thực sự đổi chỗ cho nhau.

Gợi ý

Nếu truyền theo giá trị thì hàm chỉ đổi bản sao, biến gốc không đổi. Phải truyền địa chỉ bằng con trỏ, rồi thao tác qua toán tử *.

#include <stdio.h>

// swap two integers through pointers
void hoan_doi(int *a, int *b) {
    int tam = *a;
    *a = *b;
    *b = tam;
}

int main(void) {
    int x = 3, y = 7;
    hoan_doi(&x, &y);
    printf("%d %d\n", x, y); // 7 3
    return 0;
}

Xem lại bài Hàm.

Bài 2: hàm kiểm tra số nguyên tố

Viết hàm la_nguyen_to(int n) trả về 1 nếu n là số nguyên tố, ngược lại trả 0. Trong main nhập một số rồi in "Nguyen to" hoặc "Khong".

Gợi ý

Số nhỏ hơn 2 không phải nguyên tố. Chỉ cần thử ước từ 2 tới căn của n (dùng i * i <= n để tránh dùng thư viện toán). Đây là ví dụ truyền theo giá trị: hàm nhận bản sao của n và trả về kết quả.

#include <stdio.h>

// return 1 if n is prime, 0 otherwise
int la_nguyen_to(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main(void) {
    int n;
    scanf("%d", &n);
    printf(la_nguyen_to(n) ? "Nguyen to\n" : "Khong\n");
    return 0;
}

Xem lại bài Hàm.

Bài 3: giai thừa bằng đệ quy

Viết hàm đệ quy giai_thua(int n) tính n!. So sánh với cách viết bằng vòng lặp: nêu một ưu điểm và một nhược điểm của đệ quy.

Gợi ý

Đệ quy cần điều kiện dừng: 0! = 1. Ưu điểm là code ngắn, sát định nghĩa toán học. Nhược điểm là mỗi lần gọi tốn thêm một khung ngăn xếp, n lớn dễ tràn ngăn xếp và thường chậm hơn vòng lặp.

#include <stdio.h>

// n! computed recursively
long long giai_thua(int n) {
    if (n <= 1) return 1; // base case
    return (long long)n * giai_thua(n - 1);
}

int main(void) {
    printf("%lld\n", giai_thua(5)); // 120
    return 0;
}

Xem lại bài Hàm.

Bài 4: Fibonacci

Viết hàm tính số Fibonacci thứ n (với F(0) = 0, F(1) = 1). Có thể viết đệ quy hoặc vòng lặp, hãy chọn vòng lặp và giải thích vì sao đệ quy thuần ở đây rất chậm.

Gợi ý

Đệ quy thuần fib(n-1) + fib(n-2) tính lại cùng một giá trị vô số lần nên chậm theo cấp số nhân. Vòng lặp chỉ giữ hai giá trị liền trước, chạy tuyến tính.

#include <stdio.h>

// nth Fibonacci number using a loop
long long fib(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

int main(void) {
    printf("%lld\n", fib(10)); // 55
    return 0;
}

Xem lại bài Hàm.

Bài 5: tìm phần tử lớn nhất của mảng

Viết hàm tim_max(int a[], int n) trả về phần tử lớn nhất của mảng. Hàm phải chạy đúng cả khi mảng chứa toàn số âm.

Gợi ý

Khi mảng truyền vào hàm, nó suy biến thành con trỏ nên mất thông tin độ dài, vì vậy phải truyền kèm n. Đừng khởi tạo max = 0 vì nếu mọi phần tử đều âm thì kết quả sai. Hãy khởi tạo bằng phần tử đầu tiên a[0].

#include <stdio.h>

// largest element; works for all-negative arrays
int tim_max(int a[], int n) {
    int max = a[0]; // start from first element, not 0
    for (int i = 1; i < n; i++) {
        if (a[i] > max) max = a[i];
    }
    return max;
}

int main(void) {
    int a[] = {-5, -2, -9, -1};
    printf("%d\n", tim_max(a, 4)); // -1
    return 0;
}

Xem lại bài Mảng.

Bài 6: đảo ngược mảng tại chỗ

Viết hàm dao_mang(int a[], int n) đảo thứ tự các phần tử của mảng ngay trên chính mảng đó (không dùng mảng phụ). Ví dụ {1,2,3,4} thành {4,3,2,1}.

Gợi ý

Dùng hai chỉ số chạy từ hai đầu vào giữa, hoán đổi từng cặp cho tới khi gặp nhau. Vì mảng được truyền như con trỏ, thay đổi bên trong hàm tác động thẳng lên mảng gốc.

#include <stdio.h>

// reverse the array in place
void dao_mang(int a[], int n) {
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        int tam = a[i];
        a[i] = a[j];
        a[j] = tam;
    }
}

int main(void) {
    int a[] = {1, 2, 3, 4};
    dao_mang(a, 4);
    for (int i = 0; i < 4; i++) printf("%d ", a[i]); // 4 3 2 1
    printf("\n");
    return 0;
}

Xem lại bài Mảng.

Bài 7: đếm nguyên âm trong chuỗi

Nhập một chuỗi (không chứa khoảng trắng), đếm số nguyên âm a e i o u (chỉ chữ thường) trong chuỗi đó. Dùng strlen để lấy độ dài.

Gợi ý

Chuỗi C kết thúc bằng ký tự null nên mảng phải đủ chỗ cho n + 1 ô. Hàm strlen trả về kiểu size_t (số nguyên không dấu), nên khi chạy vòng lặp hãy dùng size_t cho biến chỉ số để tránh cảnh báo so sánh dấu. Cần #include <string.h>.

#include <stdio.h>
#include <string.h>

int main(void) {
    char s[100];
    scanf("%99s", s);
    int dem = 0;
    size_t n = strlen(s); // strlen returns size_t (unsigned)
    for (size_t i = 0; i < n; i++) {
        char c = s[i];
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
            dem++;
        }
    }
    printf("%d\n", dem);
    return 0;
}

Xem lại bài Chuỗi ký tự.

Bài 8: tìm kiếm nhị phân trên mảng đã sắp xếp

Viết hàm tim_kiem_nhi_phan(int a[], int n, int key) trả về chỉ số của key trong mảng đã sắp tăng dần, hoặc -1 nếu không có. Không được duyệt tuyến tính.

Gợi ý

Giữ hai biên lo và hi, mỗi bước xét phần tử giữa. Tính mid = lo + (hi - lo) / 2 để tránh tràn khi cộng hai chỉ số lớn. Nếu giữa nhỏ hơn key thì tìm nửa phải, ngược lại tìm nửa trái. Mảng phải đã sắp xếp thì thuật toán mới đúng.

#include <stdio.h>

// return index of key in a sorted array, or -1
int tim_kiem_nhi_phan(int a[], int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoid lo + hi overflow
        if (a[mid] == key) return mid;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main(void) {
    int a[] = {1, 3, 5, 7, 9, 11};
    printf("%d\n", tim_kiem_nhi_phan(a, 6, 7)); // 3
    return 0;
}

Xem lại bài Mảng.

Bài 9: sắp xếp nổi bọt

Viết hàm noi_bot(int a[], int n) sắp xếp mảng tăng dần bằng thuật toán nổi bọt (đổi chỗ các cặp kề nhau nếu sai thứ tự).

Gợi ý

Sau mỗi lượt của vòng ngoài, phần tử lớn nhất còn lại nổi về cuối, nên vòng trong có thể rút ngắn dần. Mảng truyền vào hàm suy biến thành con trỏ nên hoán đổi bên trong tác động thẳng lên mảng gốc.

#include <stdio.h>

// sort ascending with bubble sort
void noi_bot(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

int main(void) {
    int a[] = {5, 2, 4, 1, 3};
    noi_bot(a, 5);
    for (int i = 0; i < 5; i++) printf("%d ", a[i]); // 1 2 3 4 5
    printf("\n");
    return 0;
}

Xem lại bài Mảng.

Bài 10: kiểm tra chuỗi đối xứng

Nhập một chuỗi (không chứa khoảng trắng), kiểm tra nó có phải chuỗi đối xứng hay không (đọc xuôi và đọc ngược giống nhau, ví dụ abcba).

Gợi ý

So sánh ký tự đầu với ký tự cuối, tiến dần vào giữa. Chỉ cần lặp tới nửa độ dài. strlen trả về size_t, nên dùng size_t cho chỉ số. Cần #include <string.h>.

#include <stdio.h>
#include <string.h>

// return 1 if the string reads the same both ways
int doi_xung(const char *s) {
    size_t n = strlen(s);
    for (size_t i = 0; i < n / 2; i++) {
        if (s[i] != s[n - 1 - i]) return 0;
    }
    return 1;
}

int main(void) {
    char s[100];
    scanf("%99s", s);
    printf(doi_xung(s) ? "Doi xung\n" : "Khong\n");
    return 0;
}

Xem lại bài Chuỗi ký tự.

Bài 11: nhân hai ma trận vuông nhỏ

Cho hai ma trận vuông 2 x 2 số nguyên. Tính tích của chúng và in ma trận kết quả.

Gợi ý

Phần tử c[i][j] bằng tổng tích a[i][k] * b[k][j] với k chạy qua cột của a. Nhớ khởi tạo mảng kết quả bằng 0 trước khi cộng dồn.

#include <stdio.h>

int main(void) {
    int a[2][2] = {{1, 2}, {3, 4}};
    int b[2][2] = {{5, 6}, {7, 8}};
    int c[2][2] = {{0, 0}, {0, 0}};    // accumulator starts at 0
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c[i][j] += a[i][k] * b[k][j];  // row by column
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) printf("%d ", c[i][j]);
        printf("\n");
    }
    return 0;
}

Xem lại bài Mảng.

Bài 12: đếm số từ trong một dòng

Nhập một dòng văn bản có thể chứa nhiều khoảng trắng, đếm số từ trong dòng đó. Một từ là một dãy ký tự khác khoảng trắng liền nhau.

Gợi ý

Đọc cả dòng bằng fgets (vì scanf("%s") dừng ở khoảng trắng). Duyệt từng ký tự, đếm mỗi lần chuyển từ khoảng trắng sang ký tự chữ, dùng một cờ trong_tu để biết đang ở trong một từ hay chưa.

#include <stdio.h>

int main(void) {
    char s[200];
    if (fgets(s, sizeof(s), stdin) == NULL) return 0;  // read a whole line
    int dem = 0, trong_tu = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c != ' ' && c != '\n' && c != '\t') {
            if (!trong_tu) {     // a new word begins here
                trong_tu = 1;
                dem++;
            }
        } else {
            trong_tu = 0;
        }
    }
    printf("%d\n", dem);
    return 0;
}

Xem lại bài Chuỗi ký tự.

Câu hỏi tự kiểm

Kiểm tra nhanh0/4 đúngchưa trả lời

1. 1Vì sao hàm hoán đổi hai số phải nhận tham số kiểu con trỏ (int *) thay vì int?
2. 2Khi truyền một mảng vào hàm trong C thì điều gì xảy ra?
3. 3Hàm strlen trả về giá trị thuộc kiểu nào?
4. 4Muốn lưu một chuỗi có 5 ký tự thì mảng char cần tối thiểu bao nhiêu ô?