Bài 3: Biểu thức zero

 Bài 3: Biểu thức zero
Cho một số tự nhiên N ≤ 9. Giữa các số từ 1 đến N hãy thêm vào các dấu + và - sao cho kết quả thu được bằng 0. Hãy viết chương trình tìm tất cả các khả năng có thể.
Dữ liệu vào: Lấy từ file văn bản ZERO.INP với một dòng ghi số N.
Dữ liệu ra: Ghi vào file văn bản có tên ZERO.OUT có cấu trúc như sau:
- Dòng đầu ghi số lượng kết quả tìm được.
- Các dòng sau mỗi dòng ghi một kết quả tìm được.
Ví dụ

Hướng dẫn giải
Áp dụng thuật toán đệ quy quay lui để giải quyết bài toán này, ta sẽ dùng thủ tục đệ quy Try(i). Giả sử ta đã điền các dấu’+’ và ’-’ vào các số từ 1 đến i, bây giờ cần điền các dấu giữa i và i + 1. Ta có thể chọn một trong ba khả năng: hoặc là điền dấu ’+’, hoặc là điền dấu ’-’, hoặc là không điền dấu nào cả. Khi đã chọn một trong ba khả năng trên, ta tiếp tục lựa chọn dấu để điền vào giữa i + 1 và i + 2 bằng cách gọi đệ quy Try(i+1). Ta sẽ lần lượt duyệt tất cả các khả năng đó để tìm tất cả các nghiệm của bài toán, như vậy bài toán sẽ không bị thiếu nghiệm.
Nếu i = N ta sẽ kiểm tra xem cách điền đó có thoả mãn kết quả bằng 0 hay không. Để kiểm tra ta dùng thủ tục Test trong chương trình. Nếu tổng đúng bằng 0 thì cách điền đó là một nghiệm của bài toán, ta ghi nhận nó. Nếu i < N thì tiếp tục gọi Try(i+1). Trong chương trình ta dùng biến dem để đếm các cách điền thoả mãn, còn mảng M kiểu string sẽ ghi nhận mọi cách điền dấu thoả mãn yêu cầu bài toán.
Văn bản chương trình
Program Zero_sum;
Type MangStr = array[1..15] of string;
Const Fi =’ZERO.INP’;
Fo =’ZERO.OUT’;
Dau : array[1..3] of string[1] = (’-’,’+’,’’);
S : array[1..9] of char =(’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’);
ChuSo = [’1’..’9’];

Var N,k,dem: byte;
D : array[2..9] of string[1];
F : Text;
St : String;
M : MangStr;

Procedure Write_out;
Var i : byte;
Begin
Assign(F,Fo); Rewrite(F);
Writeln(F,dem);
For i:= 1 to dem do writeln(F,M[i],’ = 0’);
Close(F); Halt;
End;

Procedure Read_inp;
Begin
Assign(F,Fi); Reset(F);
Read(F,N); Close(F);
If N < 3 then write_out;
End;

Function DocSo(S : String): longint;
Var M : longint;
t : byte;
Begin
M:= 0; t:= 0;
If S[k] in [’+’,’-’] then
begin
t:= k; Inc(k);
end;
While (k<= length(S)) and (s[k] in ChuSo) do
begin
m:= m*10 + ord(s[k]) - ord(’0’);
Inc(k);
end;
If (t <> 0) and (S[t] = ’-’) then DocSo:= -M
else DocSo:= M;
End;

Procedure Test;
Var St : string;
i : byte;
T : longint;
Begin
St:= ’1’; k:= 1; T:= 0;
For i:= 2 to N do St:= St + D[i] + S[i];
While k < length(St) + 1 do T:= T + DocSo(St);
If T = 0 then
begin
Inc(dem); M[dem]:= St;
end;
End;

Procedure Try(i: byte);
Var j : byte;
Begin
For j:= 1 to 3 do
begin
D[i]:= Dau[j];
If i = N then Test else try(i+1);
end;
End;

BEGIN
Read_inp;
Try(2);
Write_out;
END.