Đếm số lần 'move-to-front' tối thiểu để sắp xếp mảng trong C++

Chúng ta được cho một mảng các số từ 1 đến n. Mục tiêu là tìm số phép 'move to front' (di chuyển về đầu) cần thiết để sắp xếp mảng đã cho. Mảng không có phần tử trùng lặp. Phép 'move to front' chọn một phần tử và đặt tại vị trí đầu tiên, ở đây là chỉ số 0.

Chúng ta sẽ duyệt mảng từ cuối, nếu phần tử ở đúng vị trí thì không cần di chuyển ngược lại cần di chuyển. Với các phần tử từ 1 đến n, vị trí đúng trong mảng của phần tử arr[i] nên ở chỉ số i+1. arr[0] nên là 1, arr[1] nên là 2 và... arr[n-1] nên là n.

Ví dụ

Đầu vào

Arr[] = { 4, 3, 2, 1 }

Đầu ra

Số phép move-to-front tối thiểu: 3

Giải thích

Kéo 3: 3,4,2,1 count=1
Kéo 2: 2,3,4,1 count=2
Kéo 1: 1,2,3,4 count=3

Đầu vào

Arr[] = { 6, 1, 2, 5, 4, 3 }

Đầu ra

Số phép move-to-front tối thiểu: 5

Giải thích

Kéo 5: 5,6,1,2,4,3 count=1
Kéo 4: 4,5,6,1,2,3 count=2
Kéo 3: ,4,5,6,1,2 count=3
Kéo 2: 2,3,4,5,6,1 count=4
Kéo 1: 1,2,3,4,5,6 count=5

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số 1 đến n.
• Biến số nguyên size lưu độ dài mảng Arr[].
• Hàm movetoFront(int arr[], int n) nhận mảng và độ dài, trả về số phép 'move-to-front' tối thiểu để sắp xếp mảng đó.
• Biến count khởi tạo bằng kích thước mảng vì tất cả phần tử có thể di chuyển trong trường hợp mảng giảm dần.
• Bắt đầu duyệt từ chỉ số cuối về phía trước, nếu giá trị phần tử bằng count (với phần tử sắp xếp 1 đến n, n là cuối, n-1 là倒数 thứ hai...) thì giảm count vì phần tử đó ở đúng vị trí.
• Theo cách này cuối vòng lặp, count có kết quả mong muốn.

Ví dụ mã nguồn

#include <bits/stdc++.h> 
using namespace std; 

// Tính số lần di chuyển tối thiểu để sắp xếp mảng
// theo thứ tự tăng dần.
int movetoFront(int arr[], int n) { 
    // lấy count như tất cả phần tử đặt đúng
    int count = n; 
    // Duyệt mảng từ cuối
    for (int i = n - 1; i >= 0; i--) { 
        // Nếu phần tử hiện tại ở đúng vị trí,
        // giảm count
        // phạm vi 1 đến n nên mỗi arr[i] nên có giá trị i+1
        // 1 tại chỉ số 0, 2 tại chỉ số 1........
        if (arr[i] == count) 
            count--; 
    } 
    return count; 
} 

int main() { 
    int Arr[] = {5, 3, 4, 7, 2, 6, 1}; 
    int size = 7; 
    cout << "Số phép 'move-to-front' tối thiểu sắp xếp mảng: " 
         << movetoFront(Arr, size); 
    return 0; 
}

Kết quả

Số phép 'move-to-front' tối thiểu sắp xếp mảng: 6