Trên một giá sách có n cuốn sách được đánh số từ 1 đến n (n ∈ N ∗ cho trước), ban đầu các cuốn sách được sắp xếp theo thứ tự nào đó. Một thủ thư muốn xếp lại theo đúng thứ tự 1, 2,...,n từ trái qua phải, quy tắc xếp như sau: Chọn quyển sách đầu tiên có số không đúng vị trí (tính từ bên phải sang) và chuyển cuốn sách đó về đúng vị trí của nó. Ví dụ, trên giá có 4 quyển sách theo thứ tự 3−1−4−2, sau một bước chuyển quyển số 2 về đúng vị trí của nó ta xếp lại thành 3 − 2 − 1 − 4. Chứng minh rằng người thủ thư có thể hoàn thành công việc của mình sau ít hơn 2 n lần xếp theo quy tắc.
Chứng minh rằng người thủ thư có thể hoàn thành công việc của mình sau ít hơn 2 n lần xếp theo quy tắc.
Bắt đầu bởi vuthilan742, 23-02-2017 - 15:41
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh
