Bài tập 12 viên bi, tìm viên bi khác loại

[hailoc12]

12 viên bi

Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.

[iamvtn]

Hừm bài này anh làm từ hồi mới học C nhưng chỉ là 8 viên bi.
Nếu 12 viên thì theo thuật giải của anh thì phải ít nhất 5 lần cân.
Nếu 3 lần cân thì quả thuật là khó.

[hailoc12]

Chắc chắn là 3 lần cân anh ạ

[ABC_HT]

Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .

[NVL]

Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .

Chính xác! You're Number 1

[Xcross87]

Thực ra bài này giải thế này là tối ưu nè ( theo suy nghĩ của pete ) ^^!
Với điều kiện phải biết chắc chắn viên bi đó nặng hơn hoặc nhẹ hơn.
Ví dụ nếu nó nhẹ hơn, nặng hơn tương tự, thì đáp án sẽ là :

-- Tối thiểu là 2 lần cân ra luôn
-- Không quá 3 lần cân là ra.

Xác định : lấy 12 viên bi chia làm 3 phần , mỗi phần 4 bi ( A , B , C )
lấy 2 phần A và B ra cân :
+ Nếu A = B --> thằng cần tìm trong C
+ Nếu A < B --> thằng cần tìm trong A
+ Nếu A > B --> thằng cân tìm trong B
Giả sử thằng cần tìm trong C , ta xét phần C có 4 bi ( C1,C2,C3,C4 )
Lấy 2 viên bi trong số 4 bi ra cân ^^
Giả sử lấy C1,C2
+ Nếu C1 < C2 hoặc C1 > C2 thì thằng cần tìm sẽ là C1 hoặc C2 ->> đúng 2 lần cân. XONG
+ Nếu C1 = C2 thì thằng cần tìm sẽ là C3 hoặc C4, đem cân ra là có kết quả.
---> Đúng 3 lần cân ^^. XONG

Đó là xử lý nếu biết chính xác viên bi đó nặng hay nhẹ.

Còn nếu không biết chính xác thì :-?...Lúc khác nghĩ chứ đau đầu lắm

[iamvtn]

Chia 12 quả ra làm 3 cân kiểu gì mà chả ra .

Vậy cậu thử trình bầy cách làm của cậu đi. Cứ nói thế mọi người không rõ đâu.

Thực ra bài này giải thế này là tối ưu nè ( theo suy nghĩ của pete ) ^^!
Với điều kiện phải biết chắc chắn viên bi đó nặng hơn hoặc nhẹ hơn.
Ví dụ nếu nó nhẹ hơn, nặng hơn tương tự, thì đáp án sẽ là :

-- Tối thiểu là 2 lần cân ra luôn
-- Không quá 3 lần cân là ra.

Xác định : lấy 12 viên bi chia làm 3 phần , mỗi phần 4 bi ( A , B , C )
lấy 2 phần A và B ra cân :
+ Nếu A = B --> thằng cần tìm trong C
+ Nếu A < B --> thằng cần tìm trong A
+ Nếu A > B --> thằng cân tìm trong B
Giả sử thằng cần tìm trong C , ta xét phần C có 4 bi ( C1,C2,C3,C4 )
Lấy 2 viên bi trong số 4 bi ra cân ^^
Giả sử lấy C1,C2
+ Nếu C1 < C2 hoặc C1 > C2 thì thằng cần tìm sẽ là C1 hoặc C2 ->> đúng 2 lần cân. XONG
+ Nếu C1 = C2 thì thằng cần tìm sẽ là C3 hoặc C4, đem cân ra là có kết quả.
---> Đúng 3 lần cân ^^. XONG

Đó là xử lý nếu biết chính xác viên bi đó nặng hay nhẹ.

Còn nếu không biết chính xác thì :-?...Lúc khác nghĩ chứ đau đầu lắm

Vấn đề là ở chỗ không biết rõ nó nặng hơn hay nhẹ hơn. Chứ nếu biết chắc thì không nói làm gì. Đúng là min là 2 lần cân và max là 5 lần cân theo suy nghĩ của tớ.
Thế này nhá. Có 12 viên chia ra cân thế này:
- Cân các viên 1 2 3 4 5 với 6 7 8 9 10
+ nếu bằng nhau đem 11 12 ra cân là Ok (Min 2 lần)
+ nếu một trong 2 bên nặng hơn hoặc nhẹ hơn thì đem ra cân thế này
VD: 1 2 3 4 cân với 5 6 7 8
+ nếu bằng nhau đem 9 10 ra cân là OK (3 lân cân)
+ nếu không bằng nhau thì lại cân thế này tiếp
*Đem 1 2 3 với 5 6 7 ra cần
- nếu lại bằng nhau thì lại đem 8 9 ra cần (4 lân cân)
- nếu cân lại lệch thì lại cân thế này
+ Đem 1 2 với 3 5 ra cân
+ nếu bằng nhau thì lại đem 6 7 ra cân ( 5 Lần)
+ nếu không bằng nhau thì đem 1 2 hoặc 3 5 ra cân cứ thế phải đến 6 lần chứ chả chơi.
Cái chính là thuật toán để viết ra chương trình ý.

[naolmikevol]

Thế thì thế này nhé HL.

12 chia làm 3 phần A,B,C mỗi phần 4 viên.
Lần Cân 1:

Cân A,B,C Trong đó sẽ có 1 phần có trọng lượng khác so với 2 phần còn lại.
Giả sử: A=B != C .
Nếu C> A thì hòn bi đó có khối lượng nặng hơn.
Nếu C< A thì hòn bi đó có khối lượng nhỏ hơn.

Lần Cân 2:

Chia C ra làm 2 phần. E & F:
Cân E ,F . Phần nào có khối lượng khác với A/2 thì phần đó chứa viên bi cần tìm.

Hoặc :

Do ta biết được khối lượng của viên bi là nặng hay nhẹ hơn các viên bi còn lại nên phần nào nặng hay nhẹ hơn tương ứng sẽ là phần chứ viên bi cần tìm.
Giả sử ở đây ta tìm được E là phần cần tìm.

Lần Chia Thứ 3 :

Chia E ra làm 2 mỗi phần 1 viên và cân. Tương tự như lần chia thứ 2 ta sẽ biết được viên cần tìm và trọng lượng của nó.

[Xcross87]

@naolmikevol : Logic toán học sai ngay từ đầu , lần cân 1.

Cân A,B,C Trong đó sẽ có 1 phần có trọng lượng khác so với 2 phần còn lại.
Giả sử: A=B != C .
Nếu C> A thì hòn bi đó có khối lượng nặng hơn.
Nếu C< A thì hòn bi đó có khối lượng nhỏ hơn.

Khi chưa biết thì không được giả sử. Phải CÂN xác định rồi không mất tính tổng quát mới được giả sử.

Phân tích lỗi sai nè :

A, B, C : lúc đầu chưa cân chưa biết thế nào, không biết bi nặng hay nhẹ.
Ta đem vào cân lấy ra A và B :
+ Nếu A = B -> bi cần tìm sẽ là C
+ Nếu A != B -> Chưa biết là viên bi đó nằm trong A hay B và nặng hơn hay nhẹ hơn. Để xác định nặng hơn hay nhẹ hơn, phải lấy A hoặc B đem cân thử với C. Giả sử ở trên là A < B và lấy ra A so sánh với C :
__Nếu A = C : --> viên bi đó nặng hơn và trong B.
__Nếu A < C : --> viên bi đó nhẹ hơn và trong A.
__Không có trường hợp A > C : vì trong 3 phần có 2 phần chắc chắn bằng nhau và đã so sánh trước đó.

---> Không mất tính tổng quát : đáp án của naolmikevol sai ^^!

[xwaystyle]

hixx,,, chữ nếu kia của bác thì nói làm gì????
ai mà biết được nó nặng hơn hay nhẹ hơn,,,,
cứ giả sử như bác thì tui giả sử viễn cảnh giết người,, tui giết ai đó rùi chốc lát người ta sống lại à????

Nghĩ cách khác đi bạn nhá.....