Question

Cho một xâu S='123456789'.

Yêu cầu: 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ể).

Dữ liệu: Đọc từ tệp BIEUTHUC.INP gồm một dòng duy nhất ghi số nguyên dương M.

Kết quả: Ghi ra tệp BIEUTHUC.OUT:

- Dòng thứ nhất ghi K là số cách biểu diễn tìm được (ghi '0' nếu không thể thu được M từ cách làm trên).

- Nếu K>0 thì K dòng tiếp theo mỗi dòng ghi một biểu diễn nhận được.

Ví dụ:

BIEUTHUC.INP	BIEUTHUC.OUT
185	5 123-4+56-7+8+9 123+4-5-6+78-9 1-2+34+56+7+89 1+234-56+7+8-9 -1+234-56+7-8+9

Answer 1

Bạn tham khảo code này nhé.

Uses crt;
Const fo = 'chenxau.out';
dau: array[1..3] of String[1]= ('','-','+');
s:array[1..9] of char=('1','2','3','4','5','6','7','8','9');
Var d:array[1..9] of String[1];
m:longInt;
f:text;
k:integer;
found:boolean;
Procedure Init;
Begin
Write('Cho M=');
Readln(m);
found:=false;
end;
Function tinh(s:string):longint;
Var i,t:longint;
code:integer;
Begin
i:=length(s);
While not(s[i] in ['-','+']) and (i>0) do dec(i);
val(copy(s,i+1,length(s)-i),t,code);
If i=0 then begin tinh:=t; exit; end
else
begin
delete(s,i,length(s)-i+1);
If s[i]='+' then tinh:=t+tinh(s);
If s[i]='-' then tinh:=tinh(s)-t;
end;
End;
Procedure Test(i:integer);
Var st:string; j:integer;
Begin
st:='';
For j:=1 to i do st:=st+d[j]+s[j];
If Tinh(st) = m then begin writeln(f,st); found:=true; end;
End;
Procedure Try(i:integer);
Var j:integer;
Begin
for j:=1 to 3 do
begin
d[i]:=dau[j]; Test(i);
If i<9 then try(i+1);
end;
End;
BEGIN
Clrscr;
Init;
Assign(f,fo);Rewrite(f);
for k:=1 to 2 do
begin
d[1]:=dau[k];
Try(2);
end;
If not found then write(f,'khong co ngiem');
Close(f);
END.