01/10/2018, 08:38
Bài toán đổi màu bi
Đây là đề bài toán
bổ sung : nếu được thì in ra các bước thực hiện để ra toàn màu đỏ
Còn đây là lời giải
Program ba_bi;
Uses crt;
var v,x,d:integer;
BEGIN
Clrscr;
writeln('v x d ?(>=0)');
readln(v,x,d);
if ((v-x)mod 3 =0)and((x+d)*(v+d)<>0) then
while (v+x)<>0 do
begin
d:=d-1+3*((3*v*x)div(3*v*x-1 ));
x:=x+2-3*((3*x)div(3*x-1));
v:=v+2-3*((3*v)div(3*v-1));
writeln('>> ',v,' ',x,' ',d);
end
else writeln('Khong duoc !');
readln;
END.
Em không hiểu đoạn code này có nghĩa gì ạ, các anh chị giải thích giúp em với
d:=d-1+3*((3*v*x)div(3*v*x-1 ));
x:=x+2-3*((3*x)div(3*x-1));
v:=v+2-3*((3*v)div(3*v-1));
Bài liên quan
Hi tan_viet.
Theo mình cơ sở là như sau.
1 Nếu số bi V = X thì xong.
2 Nếu số bi V - X = 1 thì không thể chuyển được. (Bạn tự CM)
3 Nếu số bi V - X = 2 thì không thể chuyển được. (Bạn tự CM)
4 Nếu số bi V - X = 3 thì có thể chuyển được.
CM cho trường hợp tổng quát V - X = k có thể chuyển được khi k chia hết cho 3.
Quá trình truyển khử dần 3 bi một của k.
mà vòng lặp là để làm gì vậy? Đề bài này thế là đủ rồi
À không, em quên đăng cái đề mở rộng, đề nó nói là nếu được thì in ra các bước nữa
kiểu như này nè
Dạng bài biến đổi này thì những thao tác biến đổi luôn bảo toàn một cái gì đó. Cái này chia không gian trạng thái thành các lớp tương đương.
Anh có thể giải thích đoạn code đó được không ạ, và các bài tương cũng dùng thuật toán đó nữa
Hi rogp10.
Bạn nói rõ hơn được không. Cái này nghe nhiều mà không hiểu.
Để ý: hai viên bi hai màu sẽ biến thành hai viên bi màu thứ ba. Ta kí hiệu biến đổi này là (-1 -1 +2). Do 2-(-1) = 3 và -1-(-1) = 0 nên ta nhận ra hiệu số đôi một từng loại bi modulo 3 không đổi (1). Mà trạng thái đích là (0 0 v+x+d) nên điều kiện cần chắc chắn phải là (v-x) mod 3 = 0 (2).
Giờ phải c/m đây là điều kiện đủ. Từ (1) và (2) ta có 2v+d = d-v (mod 3) <=> 3v = 0 (mod 3) (hằng đúng). Vậy (2) là điều kiện cần và đủ để giải được.
Anh nói rõ hơn một chút được không ạ
Tại sao lại có các phép toán này ạ
d-1+3*((3*v*x)div(3*v*x-1 )) x+2-3*((3*x)div(3*x-1)) v+2-3*((3*v)div(3*v-1))Trang này có 1 bài tập tương tự. Bạn có thể xem lời giải
http://laptrinh.ntu.edu.vn/Blog/Details/1021
Bài C là bài toán kinh điển: với pt nghiệm nguyên dương ax+by = n, cực tiểu x+y.
Bài dạng này có hai câu hỏi chính: Trạng thái nào là trạng thái giải được? và giải (biến đổi) như thế nào?
Trạng thái giải được là những trạng thái mà tồn tại dãy biến đổi từ nó đưa đến trạng thái đích. Những biến đổi như vậy nếu nó bảo toàn một tính chất f(state) (f có thể là hàm bool) thì sẽ có những trạng thái không giải được vì f(start) != f(goal) (cái này vẽ hình chắc dễ thấy). Tức là f(state) luôn là hằng (số) với một f nào đấy, suốt quá trình biến đổi. Những bài phải dùng cây tìm kiếm (sâu, rộng, …) thì câu hỏi này càng quan trọng.
Còn lớp tương đương thì về thuật ngữ ta có thể định nghĩa một quan hệ (tương đương): s1Rs2 <=> f(s1) = f(s2). Ta hình dung là chỉ có các trạng thái có f() bằng nhau mới biến đổi cho nhau, điều này chia cắt không gian trạng thái thành nhiều phần, hay nhiều lớp tương đương.
-o0o-
Nếu bạn tự tìm ra được x = v (mod 3) thì động não một chút sẽ giải được thôi (dùng
ifcho dễ hiểu :D), còn công thức đó thì…