Oliver sắp xếp những chú vịt và rùa đồ chơi của em thành một hàng như hình dưới đây.
 |
Oliver muốn sắp xếp tất cả vịt sang bên trái và rùa sang bên phải, nhưng em chỉ được phép đổi chỗ hai đồ chơi liền kề trong mỗi lần di chuyển. Oliver phải di chuyển đồ chơi tối thiểu bao nhiêu lần để xếp được hàng như mong muốn?
Đáp án: 17 lần.
Có hai cách sắp xếp tối ưu nhất dành cho Oliver là di chuyển hết số vịt sang trái hoặc di chuyển hết số rùa sang phải.
- Cách 1: Di chuyển hết vịt sang trái.
Từ trái qua phải, các chú vịt lần lượt ở vị trí 1, 3, 5, 8, 10 và 11.
Để tất cả vịt ở bên trái, Oliver cần dịch chuyển các chú vịt về vị trí 1, 2, 3, 4, 5 và 6.
Mỗi lần di chuyển, vịt sẽ dịch chuyển sang trái nhiều nhất một vị trí. Số lần Oliver phải dịch chuyển đồ chơi bằng tổng số lần thay đổi vị trí của mỗi chú vịt.
Vậy số lần tối thiểu Oliver phải di chuyển để xếp được hàng như mong muốn là
(1-1) + (3-2) + (5-3) + (8-4) + (10-5) + (11-6) = 17 lần.
- Cách 2: Di chuyển hết rùa sang phải.
Từ phải qua trái. các chú rùa lần lượt ở vị trí 2, 4, 6, 7 và 9.
Oliver cần dịch chuyển các chú rùa về vị trí 7, 8, 9, 10 và 11.
Vậy số lần tối thiểu Oliver phải di chuyển để xếp được hàng như mong muốn là
(7-2) + (8-4) + (9-6) + (10-7) + (11-9) = 17 lần.
Thanh Tâm
Chuyên trang mang đến những thông tin giáo dục nóng nhất tại Việt Nam. Chúc các bạn một ngày tốt lành!
0 nhận xét
Đăng nhận xét