Các câu hỏi phỏng vấn [28]
- Bạn có 300 lít xăng và một cái xe tải. Xa tải chỉ chở được tối đa 100 lít xăng. Bạn muốn chở xăng đến bán ở chợ xăng cách khởi điểm 100 cây số. Vấn đề là xe tải chạy rất tốn xăng, mỗi cây số tốn 1 lít. Bạn được phép chở xăng để dọc đường rồi sau đó quay lại lấy để chở đi tiếp. Hỏi: Làm thế nào để bán được nhiều xăng nhất? (Nhớ là nếu bạn để xăng đâu đó dọc đường rồi quay lại lấy thêm xăng thì đoạn quay lại cũng tốn xăng.)
- Có một bàn cờ 8 x 8, các ô là các hình vuông đơn vị. Làm thế nào để cắt 3 mảnh giấy thỏa mãn điều kiện sau đây: với bất kỳ một ô X nào trên bàn cờ ta cũng có thể dùng 3 mảnh giấy để phủ bàn cờ sao cho
- Ô X không bị phủ bất kỳ chỗ nào
- Tất cả các ô còn lại đều bị phủ
- Các mảnh giấy không có phần nào chồng lên nhau
- Không có phần nào phủ ra ngoài bàn cờ
Chủ đề : Dành cho du học sinh, Vui - Giải Trí. Bookmark the
permalink. Trackbacks are closed, but you can .
5 Comments
78. Giả sử chỉ có 200 lít xăng thì giải pháp như sau:
– Lượt 1: chở 100 lít xăng từ điểm xuất phát, đến cây số 33 1/3 km, để lại 33 1/3 lít xăng, sau đó quay lại điểm xuất phát.
– Lượt 2: chở 100 lít xăng từ điểm xuất phát, đến cây số 33 1/3 km, nhặt 33 1/3 lít xăng ở đó, đi về đích.
Theo cách này, xe tải mang đến đích được 33 1/3 lít xăng.
Với 300 lít xăng thì một giải pháp (chưa chứng minh được là tối ưu) như sau:
– Lượt 1: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, để lại 50 lít xăng, quay lại điểm xuất phát.
– Lượt 2: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, nhặt 25 lít xăng ở đó, đến cây số 50 km, để lại 25 lít xăng, quay lại điểm xuất phát.
– Lượt 3: chở 100 lít xăng từ điểm xuất phát, đến cây số 25 km, nhặt 25 lít xăng ở đó, đến cây số 50 km, nhặt 25 lít xăng ở đó, đi về đích.
Theo cách này xe tải mang đến đích được 50 lít xăng.
Không biết ai có thể có giải pháp tổng quát với x lít xăng bất kỳ thì tốt quá.
79. Câu hỏi tổng quát hơn có thể là: cho một hình gốc tạo bởi các ô vuông đơn vị, chọn một mảnh giấy sao cho với bất kỳ một ô vuông nào trong hình gốc có thể dùng mảnh giấy phủ lên hình gốc không che ô vuông đã chọn, không phủ thừa ra ngoài mà diện tích không được phủ là ít nhất.
Với trường hợp hình chữ nhật, chia làm 4 hình chữ nhật con bằng nhau, khi đó bất kỳ một ô X nào trên hình gốc cũng phải thuộc 1 trong 4 hình chữ nhật con. Vì vậy chọn mảnh giấy phủ có hình của 3 hình chữ nhật con hợp lại (hình chữ L).
Khi hình gốc cụ thể là bàn cờ 8×8, chọn 3 mảnh giấy hình chữ L là hợp của 3 hình 4×4, 3 hình 2×2, 3 hình 1×1 thì sẽ đảm bảo yêu cầu phủ kín, không thừa và không che ô vuông đơn vị bât kỳ.
78. Không biết xài chương trình có ăn gian không nhỉ?
Với bước nhảy 1 và 2 thì số xăng có thẻ đua về là 52. Trình tự như sau:
-Chở 100 lít xăng đến km số 1, để lại 98 lít, về và chở tiếp.
Xe cuối cùng (ce thứ 3) đến km số 1 mất 1 lít, còn 99 lít. Bơm đầy và cứ tiếp túc từng km như thế, cuối cùng đêm về đích được 52 lít.
Tương tự, bước nhảy 2 km một lần cũng thế.
Với 100 lít : ta chỉ có một cách là chở hết và đem thẳng tới đích.
Với 200 lít : gọi a là vị trí sau 2 lượt chuyển xe còn 100 lít. KHi đó số xăng do lượt 1 cung cấp tại vị trí tối đa là 100 – 2a, lượt 1 là 100 – a, do đó vị trí a tối ưu là (100 -2a) + (100 – a) = 100 => a = 33+ 1/3 km.
Với 300 lít : ta cần tìm vị trí tối ưu a’ để dịch chuyển mà tại đó ta còn 200 lít.
lượt 1,2 tối ưu cũng chỉ cung cấp được 100 – 2a’
lượt 3 tối ưu cung cấp được 100 – a’ do đó vị trí tối ưu là
2(100 – 2a’) + 100 – a’ = 200 => a’= 20 km;
Như vậy ta thấy số xăng tối đa có thể dich chuyển được là 20 + 33 + 1/3 = 53+1/3 lít
Bài toán có thể giải tổng quát với n lít xăng > 200
78.
). Tuy nhiên tôi không thấy điều này trong đề bài!
Tất cả bài giải trên đều dựa vào giả định xe chở xăng trong bình xăng xe (hoặc xe lấy xăng trực tiếp từ cái xi-tẹc nó đang chở,
@choconlangthang: Xe hết xăng dừng lại láy trong tẹc dùng thì có sao?