Bài toán Chèn Xâu

Thầy giáo dạy lập trình

Bài toán – Chèn Xâu

Cho một xâu S = ’123456789’ hãy tìm cách chèn vào S các dấu ‘+’ hoặc ‘-‘ để thu được số M cho trước (nếu có thể). Số M nguyên được nhập từ bàn phím. Trong file Output  Chenxau.Out ghi tất cả các phương án chèn (nếu có) và ghi “Khong co” nếu như không thể thu được M từ cách làm trên.

Ví dụ: Nhập M = 8, một trong các phương án đó là: ‘-1+2-3+4+5-6+7’;

                    M = -28, một trong các phương án đó là: ‘-1+2-34+5’;

Thuật toán

Để giải bài toán này, ta có thể sử dụng phương pháp đệ quy để thử tất cả các trường hợp có thể chèn dấu ‘+’ hoặc ‘-‘ vào giữa các chữ số của xâu S. Tại mỗi bước đệ quy, ta chọn một dấu ‘+’ hoặc ‘-‘ để chèn vào vị trí tiếp theo của xâu và tính toán giá trị của biểu thức đến hiện tại. Nếu giá trị đó bằng số M thì ta lưu kết quả và kết thúc đệ quy. Nếu không thì ta tiếp tục đệ quy với các trường hợp tiếp theo.

Dưới đây là mã giả để giải bài toán này:

function solve(S, M, expr, idx, sum, result):
    if idx == len(S):  // đã thử hết các vị trí trong xâu
        if sum == M:
            result.append(expr)  // lưu kết quả
        return

    // thử chèn dấu '+' vào vị trí tiếp theo và đệ quy
    solve(S, M, expr + '+' + S[idx], idx + 1, sum + int(S[idx]), result)

    // thử chèn dấu '-' vào vị trí tiếp theo và đệ quy
    solve(S, M, expr + '-' + S[idx], idx + 1, sum - int(S[idx]), result)

// hàm chính
function main():
    S = '123456789'
    M = int(input())
    result = []
    solve(S, M, S[0], 1, int(S[0]), result)  // bắt đầu đệ quy từ vị trí thứ 2 của xâu
    if len(result) == 0:
        print("Khong co")
    else:
        for expr in result:
            print(expr)

Độ phức tạp thời gian của thuật toán này là O(2^(n-1)), trong đó n là độ dài của xâu S. Tuy nhiên, vì giá trị n là rất nhỏ (n = 9), nên thuật toán này có thể chạy nhanh chóng và đúng đắn trong thực tế.

Cài đặt bài toán bằng Python

def solve(S, M, expr, idx, sum, result):
    if idx == len(S):
        if sum == M:
            result.append(expr)
        return

    solve(S, M, expr + '+' + S[idx], idx + 1, sum + int(S[idx]), result)
    solve(S, M, expr + '-' + S[idx], idx + 1, sum - int(S[idx]), result)

def main():
    S = '123456789'
    M = int(input())
    result = []
    solve(S, M, S[0], 1, int(S[0]), result)
    if len(result) == 0:
        print("Khong co")
    else:
        for expr in result:
            print(expr)

if __name__ == '__main__':
    main()

Cài đặt bài toán với C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve(string S, int M, string expr, int idx, int sum, vector<string>& result) {
    if (idx == S.length()) {
        if (sum == M) {
            result.push_back(expr);
        }
        return;
    }

    solve(S, M, expr + "+" + S[idx], idx + 1, sum + stoi(S.substr(idx, 1)), result);
    solve(S, M, expr + "-" + S[idx], idx + 1, sum - stoi(S.substr(idx, 1)), result);
}

int main() {
    string S = "123456789";
    int M;
    cin >> M;
    vector<string> result;
    solve(S, M, S.substr(0, 1), 1, stoi(S.substr(0, 1)), result);
    if (result.empty()) {
        cout << "Khong co" << endl;
    } else {
        for (string expr : result) {
            cout << expr << endl;
        }
    }
    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *