PDA

View Full Version : [Q] Bai toan do sua.



hiensmart
07-12-2002, 17:32
Dao nay coi Nha toan hoc tre tuoi hay co phan do sua, vay cho hoi bai toan nay co thuat giai ko neu cho biet 1 binh lon chua day sua va 2 binh nho co tong dung tich bang cua binh lon.
Ai biet xin chi giao , tai ha xin cam on.

khôngtên
07-12-2002, 22:33
Bác đánh có dấu đi ! tôi đoc chẳng hiểu gì cả ! Thông cảm nhé !

hiensmart
08-12-2002, 19:10
Co ai coi "nha toan hoc tre tuoi" ko, o phan thi tro choi van dong, co thi do sua(milk), coa i biet thuat toan hay cach lam ko, chi tui.
*****ghi ro rang dzay thui******

khôngtên
08-12-2002, 19:15
Tôi chưa xem lần nào nhưng bác có thể miêu tả trò chơi cũng như cách chơi được không thì có lẽ các thành viên hay tôi mới biết mà giúp chứ !

hiensmart
08-12-2002, 19:21
Cho 1 binh lon chua day sua.
Cho 2 binh nho co tong dung tich bang dung tich binh lon.
Cho 1 so cho truoc la so lit sua phai dong.
Tu 3 binh tren dong ra so lit sua yeu cau.
Dung tich 3 binh va so lit sua can dong la nhap tu ban phim( hay file cung dc)

hiensmart
09-12-2002, 20:00
Day co phai la chua BA Danh ko dzay.
Phan doi, tu sang toi toi ko ai dzo day het a.

khôngtên
09-12-2002, 21:33
Để cho tiện bác nên gõ tiếng Việt có đấu đi ! Bác vào đây down chương trình vietkey mà sài ! vietkey.com/data/vknt.exe

hiensmart
11-12-2002, 13:56
[FONT=century gothic]Đề: cho 1 bình chứa đầy sữa. Cho 2 bình rỗng có tổng dung tích bằng dung tích bình lớn. Tử 3 bình trên, hãy đong ra 1 số l sữa nhất định hoặc thông báo ko có cách đong.
VD: cho bình 20 l chứa đầy sữa và 2 bình rổng có dung tích là 7 và 13 l. Hãy đong ra 3 l sữa.

Mach2
13-12-2002, 07:04
Chùi ui? Đâu phải chùa đâu bạn, có điều bài của bạn cũng ko biết là có giải thuật ko mà... Để từ từ mọi người mới suy nghĩ được chớ.

Mach2
15-12-2002, 22:37
Tôi vừa nghĩ ra một cách dùng một cây "tam" phân duyệt từ từ từng trường hợp cho đến khi tìm được lời giải hay đến một độ sâu nào đó thì dừng mà chưa chắc có được ko... Này tác giả ơi, bạn đã có hướng nào chưa nhỉ?

danceswithwolves
16-12-2002, 10:15
Mach2@, mày chơi kiểu vét cạn hả ? Có cần trâu bò brute-force đến mức đó không ? Reversely analyze (bottom-up) rồi recursive nó. Làm xong rồi post lên đây nhé.

chúc mày bảo vệ... rớt máy bay Concorde.

khôngtên
17-12-2002, 12:48
Bác Mach2 ơi post lên cho anh em tham khổ đi !

Mach2
17-12-2002, 22:26
Chùi ui, tôi đâu có biết mí cái thuật giải dww nói đâu, chỉ biết vét cơm thui, nhưng mà để thư thư tôi thử xem sao, mới là ý tưởng thui mà... Ý tưởng của khôngtên ra sao?

LuXuBu
18-12-2002, 15:37
Tôi xin gửi đoạn chương trình này để các bạn góp ý.

Uses crt;
type
chai=record
d1,d2:integer;
end;
var
c1,c2,c3:chai;
solan,cc,c11,c22,c33:integer;
kt:boolean;

{Chuong trinh chinh}

Begin
clrscr;
Write('Nhap vao tong so lit sua (tuong ung voi dung tich chai 1) : ');
readln(c1.d1);
Write('Nhap vao dung tich chai 2 : ');
readln(c2.d1);
Writeln('Dung tich chai 3 : ', c1.d1-c2.d1);
write('So lit can lay : ');
readln(cc);
c3.d1:=c1.d1-c2.d1;
if c2.d1<c3.d1 then
Begin
c2.d1:=c1.d1-c3.d1;
c3.d1:=c1.d1-c2.d2;
end;
c1.d2:=c1.d1;
c2.d2:=0;
c3.d2:=0;
writeln('Chai 1: ',c1.d2, ' Chai 2: ', c2.d2,' Chai 3: ', c3.d2);
solan:=0;
clrscr;
Writeln('Chai 1 dung tich: ',c1.d1,' Chai 2 dung tich: ',c2.d1,' Chai 3 dung tich: ',c3.d1);
repeat
inc(solan);
kt:=true;
{Chai 1 -> 2}

if (c2.d2=0)and kt then
Begin
c2.d2:=c1.d2-(c1.d2-c2.d1);
c1.d2:=c1.d2-c2.d2;
kt:=not kt;
Write('1->2 ');
end ;
{Chai 2 -> 3}

if ((c3.d2=0)or((c1.d2>0)and (c2.d2>0)and(c3.d2>0)and(c1.d2<>c3.d1)and (c2.d2<>c3.d1)and(c3.d2<>c3.d1) ))and kt then
Begin
if c2.d2>=c3.d1 then
Begin
c3.d2:=c3.d1;
c2.d2:=c1.d1-c1.d2-c3.d2;
kt:= not kt;
end
else
Begin
c3.d2:=c2.d2;
c2.d2:=0;
end;
Write('2->3 ');
end;
{Chai 3 -1}
if ((c1.d2>0)and(c2.d2>0)and(c3.d2>0))and kt and(c3.d2=c3.d1) then
Begin
c1.d2:=c1.d2+c3.d2;
c3.d2:=0;
kt:=not kt;
Write('3->1 ');
end;
writeln('Chai 1: ',c1.d2, ' Chai 2: ', c2.d2,' Chai 3: ', c3.d2);
Until (cc=c1.d2)or(cc=c2.d2)or(cc=c3.d2)or (solan>1000);

readln;
end.

LuXuBu
18-12-2002, 15:43
Ở địa chỉ DelphiSource.com có nhiều mã nguồn bằng Pascal lắm.
Các bạn vào thử. Nếu có download được cái gì vừa hay vừa mới thì cho mình xem với nghen.

Cám ơn các chiến hữu.

skywalker
05-01-2003, 23:04
bài đong sữa chắc là dùng loang đó, để em thử viết xem

btkiet
15-01-2003, 10:24
Tôi vừa tìm được một thuật toán cũng khá hay và đơn giản trong một cuốn sách toán học thuần túy, mời các bạn tham khảo.
Giả sử ta có 3 bình với dung tích như sau
Bình A: 12 lít.
Bình B: 8 lít.
Bình C: 5 lít.
Bình A chứa đầy 12 lít sữa, bình B và C rỗng. Bây giờ làm thế nào để đong được 6 lít sữa vào bình B.
Cách làm như sau:
Gọi bộ ba (x,y,z) là trạng thái hiện tại của 3 bình A, B và C. Với điều kiện (x<=12, y<=8, z<=5).
Suy ra trạng thái ban đầu là (12,0,0)
Ta cần đưa trạng thái này về trạng thái sau cùng là: (x1,6,x2) với điều kiện (x1+x2=6, x2<=5).
Cụ thể như sau:
Ban đầu (12,0,0)
đổ từ A sang B (4,8,0)
đổ từ B sang C (4,3,5)
đổ từ C sang A (9,3,0)
đổ từ B sang C (9,0,3)
đổ từ A sang B (1,8,3)
đổ từ B sang C (1,6,5).
(1,6,5) là trạng thái kết thúc.

hiensmart
15-01-2003, 17:34
To SW:Đong sữa mà xài loang à, hơi lạ hỉ. Đâu skywalker thử viết xem.
To BTK:tôi vẫn chưa hiểu lắm,bạn thử viết xem.

btkiet
16-01-2003, 08:31
Ba trục A,B,C tương ứng với 3 bình, trong đó bình A đầy sữa. Thực hiện theo nguyên tắc phản xạ của bàn bi-a. Từ điểm xuất phát đổ đầy bình B thì lúc này bình A còn 4 lit... để tôi viết thử post lên cho...

hiensmart
19-01-2003, 07:51
Chời, sao chỉ toàn nói miệng ko dzậy

ureka
19-01-2003, 08:38
Bài toán của bkiet nghe ra tưởng có lý nhưng tui nhìn lại thì thấy sai nguyên tắc, đó là tổng của 2 bình nhỏ phải bằng bình lớn!
Còn bài viết của Lubuxu tui chưa biết thế nào nhưng không lẽ phải hiểu được Pascal mới giải quyết được hay sao? Với lại sao bao nhiêu bước thì lấy được 1/2 số sữa của bình lớn nhất? Đây chỉ là một bài toán đơn giản của cấp 2, chẳng cần gì đến tin học cả. Tui trình bày cho các ông thấy giải thuật nhưng đừng có phổ biến quá mức mà làm cuộc thi nhà toán học trẻ tuổi bị mất vui đó.
Lấy lại giả thiết của hiensmart : bình 1 < bình 2 < bình 3 và
bình 1 = 7 ; bình 2 = 13 ; bình 3 =20. Trạng thái ban đầu là bình 3 chứa đầy sữa.
Nguyên tắc là:
1. Nếu bình 2 rỗng thì đổ đầy từ bình 3 sang.
2. Đổ từ bình 2 sang bình 1 cho đến khi bình 1 đầy.
3. Nếu bình 1 đầy thì đổ nó sang bình 3.
4. Quay lại bước 1.
Cụ thể như sau:
-----------------
Bước Bình 1 Bình 2 Bình 3
0 0 0 20
1 0 13 7
2 7 6 7
3 0 6 14
4 6 0 14
5 6 13 1
6 7 12 1
7 0 12 8
8 7 5 8
9 0 5 15
10 5 0 15
11 5 13 2
12 7 11 2
13 0 11 9
14 7 4 9
15 0 4 16
16 4 0 16
17 4 13 3
18 7 10 3
----------------
Trong bảng trên xuất hiện tất cả các số từ 1 đến 19. Và cũng có thể thấy số 10 xuất hiiện ở bước thứ 18 và là số sau cùng. Đó cũng là lý do tại sao người ta chọn 1/2 dung tích lớn nhất làm câu hỏi. Tóm lại, để đạt 1/2 dung tích lớn nhất cần n-2 bước đổ sữa. Không tin các bác kiểm tra lại xem.

ureka
19-01-2003, 20:26
Giải thuật trên cũng có lý nhưng mà sao tui làm thử bài ví dụ với bình 3=42lít ; bình 2=26 lít ; bình 1 =16 lít sao tui đong wài mà không được 19lít vậy?

Junior IT
19-01-2003, 22:42
Hình như ureka nhầm lẫn rồi thì phải. Quy tắc cho đề bài là số lít sữa cần đong = (bình 1 + bình 2) / 2 mà. (26+16) /2 đâu có bằng 19?

btkiet
20-01-2003, 08:52
giải thuật của ureka giống với giải thuật của tôi thôi mà, một cái diễn tả bằng lời còn một cái diễn tả bằng sơ đồ. Giải thuật của tôi có thể áp dụng cho cả trường hợp tổng dung tích 2 bình nhỏ không cần bằng dung tích bình lớn. Số sữa cần đong bằng phân nữa dung tích bình lớn.

hiensmart
20-01-2003, 16:50
Cảm ơn sự tham gia của tất cả các bạn, theo tôi thì thuật giải của btkiet khá đúng. Còn của bạn eureka thì ko hẳn là đúng vì theo bạn thì mức sữa cần đong luôn =(bình 1+bình 2)/2=bình 3/2. Cách giải như vậy ko linh động, và khi làm thì nó sẽ luôn đúng với số sữa cần đongbằng nửa dung tích bình lớn nhưng với các trường hợp khác chưa chắc đúng.
Đối với cách làm của eureka tôi đã viết thử chương trình và kết quả là chưa chắc luôn đúng với trường hợp tổng dung tích 2 bình nhỏ bằng bình lớn còn lại thì sẽ cho số sữa cần đong bất kì, còn của btkiet thì ngược lại. Hy vọng các bạn sẽ góp ý, sửa chữa thêm.

ureka
21-01-2003, 23:54
Các ông nhìn làm sao vậy? Tôi nói là có thể lấy ra bất kỳ dung tích nào từ 1 đến 19 chỉ trong 18 bước đổ sữa đó thôi. Không nhất thiết nó nằm ở bình nào. Chẳng hạn nếu ông cần 1 lít thì ông dừng lại ở bước 5, bình 3 chứa 1lít; nếu ông cần 18 lít thì dừng lại ở bước 11, tổng bình 1+bình 2 là 18 lít. Các ông hiểu chưa vậy???

ureka
21-01-2003, 23:58
To Junior IT: Không có nhầm lẫn đâu, tôi chỉ kiểm tra xem các ông hiểu những gì tôi viết đến mức độ nào thôi. Đừng tự ái nha bồ!!!

skywalker
31-01-2003, 00:59
Bài này dùng loang, mình sẽ đánh dấu bằng cách, khai báo hàng đợi là mảng d:array[0..1,1..1000] of longint;
dùng 5 bit đầu để đánh dấu số lít trong thùng 1, 5 bit kế tiếp để đánh dấu số lít trong thùng 2, 5 bít tiếp nữa đánh dấu thùng thứ 3.
(hình như số lít mỗi thùng ko quá 20, cho nên dùng 5 bit là đủ để biểu diễn). cứ thế ta sẽ loang bình thường cho đến khi nào tới đích

hiensmart
03-02-2003, 15:23
Viết chương trình đi

ngocquynh85
12-02-2003, 12:11
về thuật toán chia sữa này có 1 cách dựa theo ý tuởng viên bi a lăn trên hình chữ nhật. Cực kì đơn giản không phải dùng bất kì thuật toán loang hay đệ quy phức tạp nào cả.
Hồi lớp 10 ôn thi Tin tui cũng đã làm bài này, hồi đó chưa biết nên nghĩ mãi chẳng ra !
Ngoài ra trong báo toan học tuổi trẻ cũng có 1 bài viết về thuật toán chia sữa tổng quát cũng rât hay !
bác nào muốn tìm hiểu thì mail cho tui
ngocquynh852002@yahoo.com

hiensmart
19-02-2003, 15:46
Q học lớp 12CTIN LHP dung ko?

btkiet
21-02-2003, 10:48
to ngocquynh85 Thuật toán dựa theo ý tưởng viên bi a lăn trên hình chữ nhật đã được tôi trình bày ở trên rồi đó, có luôn sơ đồ biểu diễn nữa, bạn không có đọc kỹ sao ?

khôngtên
26-02-2003, 18:15
Tôi có làm nhưng bằng phương pháp tìm kiếm theo chiều rộng ! Chạy cũng tương đối ! Tôi sẽ post sau ! Hình như bài này có thể làm bằng Quy Hoạch Động nhưng tôi chưa nghĩ ra !

hiensmart
01-03-2003, 22:47
Chà, bài toán này nhiều người nghĩ ra cách mà cũng nhiều người ko post lên cho bà con xem thử wá, xin wí vị làm ơn post đi, tui chờ mỏi mòn mà ko thấy, nếu ko đc thì hướng giải cũng đc

hiensmart
11-03-2003, 16:51
À, bài toán có biến tấu mới, cho dung tích 3 bình bất kỳ(<20) hẵy tìm số l sữa có thể đong đc tất cả, liệt kê ra hết

hiensmart
20-03-2003, 16:17
Sao ko ai nói năng gì hết vậy

hiensmart
20-03-2003, 17:27
Wá chán
const
inp = 'milk3.in';
out = 'milk3.out';
maxcase = 10000;
maxval = 20;
a = 1;
b = 2;
c = 3;

type
info = array [1..c] of byte;
infoarr = array [1..maxcase] of info;
markarr = array [1..maxcase] of boolean;

var
fi, fo: text;
save: ^infoarr;
mark: ^markarr;
max, cur, tmp: info;
valc: array [1..maxval] of byte;
source, target, countval, i: byte;
countsave: integer;

procedure try;
begin
if cur[target] + cur[source] <= max[target] then
begin
inc(cur[target], cur[source]);
cur[source] := 0;
end
else
begin
dec(cur[source], max[target] - cur[target]);
cur[target] := max[target];
end;
end;

procedure solve;
var
i, j, u, v: integer;
found1, found2: boolean;

begin
repeat

found1 := false;
for i := countsave downto 1 do
if not mark^[i] then
begin
mark^[i] := true;
tmp := save^[i];
cur := tmp;
found1 := true;
break;
end;

if found1 then
begin
for i := a to c do
for j := a to c do
if (i <> j) and (cur[i] > 0) and (cur[j] < max[j])
then begin
source := i;
target := j;
try;
found2 := false;
for u := 1 to countsave do
if (save^[u][a] = cur[a])
and (save^[u][b] = cur[b])
and (save^[u][c] = cur[c]) then
begin
found2 := true;
break;
end;
if not found2 then
begin
inc(countsave);
save^[countsave] := cur;
mark^[countsave] := false;
if cur[a] = 0 then
begin
u := countval + 1;
while cur[c] > valc[u - 1] do
dec(u);
if cur[c] <> valc[u - 1] then
begin
for v := countval downto u do
valc[v + 1] := valc[v];
valc[u] := cur[c];
inc(countval);
end;
end;
end;
cur := tmp;
end;
end;

until not found1;

end;

begin

assign(fi, inp);
reset(fi);
read(fi, max[a], max[b], max[c]);
close(fi);

new(save);

save^[1][a] := 0;
save^[1][b] := 0;
save^[1][c] := max[c];
mark^[1] := false;
countsave := 1;

valc[1] := max[c];
countval := 1;

solve;

dispose(save);

assign(fo, out);
rewrite(fo);
write(fo, valc[countval]);
for i := countval - 1 downto 1 do
write(fo, ' ', valc[i]);
close(fo);

end.

btkiet
31-03-2003, 10:57
Đã giải được rồi mà còn kêu người ta post code lên làm gì nữa ;)

monkeyvu
05-05-2003, 08:26
ngocquynh85 đeo cặp mắt kiếng very big big big big.....