Untitled

mail@pastecode.io avatar
unknown
plain_text
22 days ago
1.9 kB
1
Indexable
Never
Biểu thức zero
#include <iostream>

using namespace std;

const int MAX_N = 9; // n tối đa là 9
char operators[MAX_N]; // lưu trữ các toán tử (+, -, ' ')
int n;

// Hàm tính giá trị của biểu thức được xây dựng từ các toán tử trong mảng operators
int evaluateExpression() {
    int total = 0;
    int current_num = 0;
    int sign = 1;  // 1 là dương (+), -1 là âm (-)

    for (int i = 1; i <= n; i++) {
        current_num = current_num * 10 + i; // Ghép số khi gặp ' '

        // Khi gặp dấu + hoặc -, thực hiện phép tính với số hiện tại
        if (i == n || operators[i] != ' ') {
            total += sign * current_num;
            current_num = 0;  // Reset current_num

            // Xác định dấu tiếp theo
            if (i < n) {
                if (operators[i] == '+') {
                    sign = 1;
                } else if (operators[i] == '-') {
                    sign = -1;
                }
            }
        }
    }

    return total;
}

// Đệ quy để thử tất cả các phép toán
void backtrack(int index) {
    if (index == n) { // Nếu đã hết các vị trí thì đánh giá biểu thức
        if (evaluateExpression() == 0) {
            // In ra biểu thức hợp lệ
            cout << "1";
            for (int i = 2; i <= n; i++) {
                cout << operators[i - 1] << i;
            }
            cout << endl;
        }
        return;
    }

    // Thử các toán tử +, -, ' ' tại vị trí hiện tại
    operators[index] = ' ';
    backtrack(index + 1);

    operators[index] = '+';
    backtrack(index + 1);

    operators[index] = '-';
    backtrack(index + 1);
}

int main() {
    cin >> n;

    // Gọi đệ quy từ vị trí 1 với biểu thức bắt đầu là 1
    backtrack(1);

    return 0;
}
Leave a Comment