Chủ đề này có 4 trả lời

[VŨ Thanh Tùng]

Có 1 tòa nhà 2006 tầng và 1 số i có tính chất: nếu ta thả 1 viên bi từ 1 tầng thấp hơn tầng thứ i thì viên đi đó không bị vỡ, còn nếu ta thả từ tầng cao hơn hoặc bằng i thì nó sẽ vỡ. Biết rằng trong tay chúng ta có 4 viên bi, hỏi có thể thả bi ít nhất là bao nhiêu lần để chắc chắn xác định được số i đó?

[hoang]

Lấy 3 viên bi để sử dụng phương pháp "chia đôi để trị" ta tìm được một khoảng gồm
2006/(2^3) tầng liên tiếp mà chứa tầng cần tìm. Dùng viên còn lại thử lần lượt trong khoảng này từ thấp lên cao

Tóm lại : Trường hợp xấu nhất ta sẽ phải thử 2*2006/(2^3) tầng + 3 lần ban đầu

[shinichi9htv]

lời giải của bác Hoang chắc chưa tối ưu đâu. Bài của Tùng khó quá

[shinichi9htv]

Gọi m là số lần ít nhất cần thả ứng với tòa nhà n tầng.

1)Làm trường hợp 2 viên bi trước: vì m là số lần cần thả nên phải thả phát đầu ở tầng m => phát 2 ở tầng m+(m-1) =>... Như thế m phải thỏa mãn m+(m-1)+...+1 >= n hay là m là số nhỏ nhất thỏa mãn C(2,m)>= n

2)3 viên bi: Phải thả bắt đầu ở tầng C(2,m-1)+1 => phát 2 ở tầng C(2,m-1)+C(2,m-2)+2 => ... Như thế m là số nhỏ nhất thỏa mãn C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2)>=n . Kí hiệu là f(3,m)=C(2,m-1)+C(2,m-2)+...+C(2,2)+(m-2).

3)4 viên bi: Phải thả bắt đầu ở tầng f(3,m-1)+1 =>... => f(3,m-1)+f(3,m-2)+...+f(3,3)+(m-3) >=n

Thuật toán này cho ta lời giải tối ưu.

Bài viết đã được chỉnh sửa nội dung bởi shinichi9htv: 21-03-2006 - 02:31

[VŨ Thanh Tùng]

Cách bác shinichi có vẻ đúng, nhưng bác xem lại phát.

Bài viết đã được chỉnh sửa nội dung bởi VŨ Thanh Tùng: 21-03-2006 - 04:14