Câu hỏi 15
Năm thẻ mang các số từ 1 đến 5 được xếp ngẫu nhiên thành một hàng. Ta sắp xếp chúng theo thứ tự tăng dần bằng thuật toán “sắp xếp nổi bọt” (Bubble Sort): bắt đầu từ bên trái, so sánh hai thẻ kề nhau đầu tiên và đổi chỗ nếu thẻ bên trái lớn hơn; sau đó dịch sang phải một vị trí và lặp lại cho đến cuối hàng. Lặp lại quy trình từ đầu cho đến khi các thẻ được sắp xếp hoàn toàn.
Đếm mọi lần đổi chỗ trong toàn bộ quá trình. Ví dụ, $(4,5,3,2,1)$ cần 9 lần đổi chỗ:
$$(4,5,3,2,1)\to(4,3,5,2,1)\to(4,3,2,5,1)\to(4,3,2,1,5)$$
$$\to(3,4,2,1,5)\to(3,2,4,1,5)\to(3,2,1,4,5)\to(2,3,1,4,5)$$
$$\to(2,1,3,4,5)\to(1,2,3,4,5).$$
Có bao nhiêu cách xếp ban đầu cần đúng 5 lần đổi chỗ để sắp xếp hoàn toàn? Trình bày lời giải chi tiết.
Đếm mọi lần đổi chỗ trong toàn bộ quá trình. Ví dụ, $(4,5,3,2,1)$ cần 9 lần đổi chỗ:
$$(4,5,3,2,1)\to(4,3,5,2,1)\to(4,3,2,5,1)\to(4,3,2,1,5)$$
$$\to(3,4,2,1,5)\to(3,2,4,1,5)\to(3,2,1,4,5)\to(2,3,1,4,5)$$
$$\to(2,1,3,4,5)\to(1,2,3,4,5).$$
Có bao nhiêu cách xếp ban đầu cần đúng 5 lần đổi chỗ để sắp xếp hoàn toàn? Trình bày lời giải chi tiết.