Bài: Chỉ một lần cân

[damnguyenhuu]

Có N quả cân với các trọng lượng tương ứng là 1kg, 3kg, ..., 3^(N-1)kg và một cân bàn. Tìm phương án có thể được mà chỉ dùng cân bàn và N quả cân này để cân vật V có trọng lượng Mkg trong một lần cân.
Lập trình nhập từ bàn phím 2 số nguyên dương N và M (N <= 15, M <= 100000000). Nếu không cân được, in ra màn hình chữ 'KHONG', ngược lại in ra màn hình 2 dòng, dòng thứ nhất là số hiệu các quả cân đặt cùng phía vật V, dòng thứ hai là số hiệu các quả cân đặt ở phía bên kia.

[bld]

bài này thuộc dạng QHD tìm các phần tử của mảng sao cho có thể đặt các phép toán + , - giữa chúng để dc kết quả là M

tạo 2 mảng 2 chiều kích thước M*N , 1 mảng đặt tên là + , mảng kia là -
+[i,j]=true nếu +[i-1,j]=true hoặc -[i-1,j]=true hoặc +[i-1,j-i]=true hoặc
-[i-1,j-i]=true
-[i,j]=true nếu +[i-1,j]=true hoặc -[i-1,j]=true hoặc +[i-1,j+i]=true hoặc
-[i-1,j+i]=true


kết quả là true nếu +[N,M]=true hoặc -[N,M]=true.

truy vết ko khó .

-----------
cách giải này có thể sai ...bét ^^

[damnguyenhuu]

Để mình thử cách của bạn xem! Cảm ơn bạn ha!

[bld]

mình nói ko rõ (và sai nữa) mà bạn cũng hiểu àh ^^
sửa lại rồi đó

cơ sở QHD cho bài này chắc bạn cũng biết ^^

[damnguyenhuu]

Các bạn xem thử thuật toán mình tối ưu chưa nha! :)


Uses Crt;
Label tt;
Var
t, p: array[1..100] of Integer;
m, n, it, ip, j, h, mu: Longint;
Begin
Repeat
Clrscr;
Write('Nhap vao so mu gioi han N = ');
Readln(n);
Write('Nhap vao trong luong vat: M = ');
Readln(m);
h:= m; mu:= 0; ip:= 0; it:= 0;
While m <> 0 do
Begin
Case m mod 3 of
1: Begin
ip:= ip + 1;
p[ip]:= mu;
m:= m - 1;
End;
2: Begin
it:= it + 1;
t[it]:= mu;
m:= m + 1;
End;
End;
m:= m div 3; mu:= mu + 1;
End;
If mu > n then
Begin
Write('Khong can duoc!');
Goto tt;
End;
Write('Dia can ben trai: ');
For j:= 1 to it do Write(t[j] + 1: 2,' ');
Writeln('vat');
Write('Dia can ben phai: ');
For j:= 1 to ip do Write(p[j] + 1: 2,' ');
Write('vat');
tt: Write(#13#10,'An ESC => Thoat, phim khac...');
Until Readkey = #27;
End.

[bld]

thuật toán như thế nào vậy bạn ^^ ( hay hơn thì phải ^^)