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 cộng (+) và dấu trừ (-) 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ụ:
|
ZERO.INP |
ZERO.OUT |
|
7 |
6 1-2-3-4-5+6+7 = 0 1-2+3+4-5+6-7 = 0 1-23-45+67 = 0 1-23+4+5+6+7 = 0 1+2-3-4+5+6-7 = 0 1+2-3+4-5-6+7 = 0 |
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.
CODE THAM KHẢO:
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.
Đăng nhận xét