Ví dụ 1 Thiết kế một thuật toán để chèn các ký hiệu +, -, hoặc không chèn gì giữa các số từ 1 đến 9 sao cho kết quả là 100. Ví dụ: 1+2+34-5+67-8+9=100.

Phương pháp xử lý

1. Định nghĩa mảng ký tự chứa các phép toán.

char phepToan[3] = {'+', '-', ' '};

2. Tạo mảng ký tự lưu trữ biểu thức hoàn chỉnh.

char bieuThuc[20]; // Đủ dài để chứa biểu thức.

3. Sử dụng mảng a để đánh dấu vị trí của từng phép toán.

int a[9]; // Chỉ sử dụng từ a[1] đến a[8]

4. Duyệt qua tất cả các khả năng bằng cách lồng vòng lặp.

for(a[1]=0; a[1]<=2; a[1]++)
    for(a[2]=0; a[2]<=2; a[2]++)
        ...
        for(a[8]=0; a[8]<=2; a[8]++) {
            int j = 0;
            bieuThuc[0] = '+';
            
            for(int i=1; i<=8; i++) {
                if(phepToan[a[i]] == '+' || phepToan[a[i]] == '-') {
                    j++;
                    bieuThuc[j] = '0' + i;
                    j++;
                    bieuThuc[j] = phepToan[a[i]];
                } else {
                    j++;
                    bieuThuc[j] = '0' + i;
                }
            }
            j++;
            bieuThuc[j] = '9';
            j++;
            bieuThuc[j] = '\0';
            
            // Xử lý tính toán và kiểm tra tổng
            int tong = 0, ketQua = 0;
            char dauTruoc = bieuThuc[0];
            ...
            if(tong == 100) {
                bieuThuc[0] = ' ';
                printf("%s=100\n", bieuThuc);
            }
        }

Lưu ý:

Khi xử lý chuỗi, cần thêm ký tự \0 vào cuối chuỗi để kết thúc chuỗi.

Mã nguồn đầy đủ

Mã lực mạnh mẽ

#include<stdio.h>

int main() {
    char phepToan[3] = {'+', '-', ' '};
    char bieuThuc[20];
    int a[9], i, j;

    for(a[1]=0; a[1]<=2; a[1]++)
        for(a[2]=0; a[2]<=2; a[2]++)
            ...
            for(a[8]=0; a[8]<=2; a[8]++) {
                int j = 0;
                bieuThuc[0] = '+';
                
                for(i=1; i<=8; i++) {
                    if(phepToan[a[i]] == '+' || phepToan[a[i]] == '-') {
                        j++;
                        bieuThuc[j] = '0' + i;
                        j++;
                        bieuThuc[j] = phepToan[a[i]];
                    } else {
                        j++;
                        bieuThuc[j] = '0' + i;
                    }
                }
                j++;
                bieuThuc[j] = '9';
                j++;
                bieuThuc[j] = '\0';

                // Tính toán tổng
                int ketQua = 0, tong = 0;
                char dauTruoc = bieuThuc[0];
                ...
                if(ketQua == 100) {
                    bieuThuc[0] = ' ';
                    printf("%s=100\n", bieuThuc);
                }
            }
    return 0;
}

Phát hiện:

Mã này sử dụng phương pháp brute force và có thể cải thiện bằng cách sử dụng đệ quy.

Đệ quy

#include<stdio.h>

void hamDeQuy(char phepToan[], int so[], int tong, int truoc, int viTri) {
    if(viTri == 9) {
        if(tong == 100) {
            printf("%d", so[0]);
            for(int i=1; i<9; i++) {
                if(phepToan[i] == '+' || phepToan[i] == '-')
                    printf("%c%d", phepToan[i], so[i]);
                else 
                    printf("%d", so[i]);
            }
            printf("\n");
        }
    } else {
        int tam;
        phepToan[viTri] = '+';
        tong += so[viTri];
        hamDeQuy(phepToan, so, tong, so[viTri], viTri + 1);
        tong -= so[viTri];

        phepToan[viTri] = '-';
        tong -= so[viTri];
        hamDeQuy(phepToan, so, tong, -so[viTri], viTri + 1);
        tong += so[viTri];

        phepToan[viTri] = ' ';
        tong -= truoc;
        if(truoc > 0) tam = truoc * 10 + so[viTri];
        else tam = truoc * 10 - so[viTri];
        tong += tam;
        hamDeQuy(phepToan, so, tong, tam, viTri + 1);
        tong -= tam;
        tong += truoc;
    }
}

int main() {
    int so[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    char phepToan[9];
    hamDeQuy(phepToan, so, so[0], so[0], 1);
    return 0;
}