Bài toán Đỉnh bu lông (Nuts and Bolts Problem)

Giới thiệu

Một danh sách các đai ốc (nuts) khác nhau và một danh sách bu lông (bolts) khác được cho. Nhiệm vụ của ta là tìm sự khớp đúng của đai ốc và bu lông từ danh sách cho trước, và gán đai ốc đó với bu lông khi nó khớp.

Bài toán này được giải quyết bằng kỹ thuật quick-sort (sắp xếp nhanh). Bằng cách lấy phần tử cuối cùng của bu lông làm chốt (pivot), sắp xếp lại danh sách đai ốc và lấy vị trí cuối cùng của đai ốc mà bu lông của nó là phần tử chốt. Sau khi phân vùng danh sách đai ốc, ta có thể phân vùng danh sách bu lông bằng đai ốc đã chọn. Các tác vụ tương tự được thực hiện cho các danh sách con trái và phải để có tất cả các cặp khớp.

Đầu vào và Đầu ra

Đầu vào: Danh sách khóa và chìa khóa.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Đầu ra: Sau khi khớp đai ốc và bu lông:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

Thuật toán

partition(array, low, high, pivot)

Đầu vào: Một mảng, chỉ số thấp và cao, phần tử chốt.

Đầu ra: Vị trí cuối cùng của phần tử chốt.

Begin
    i := low
    for j in range low to high, do
        if array[j] < pivot, then
            hoán đổi array[i] và array[j]
            tăng i lên 1
        else if array[j] = pivot, then
            hoán đổi array[j] và array[high]
            giảm j xuống 1
    done
    hoán đổi array[i] và array[high]
    return i
End

nutAndBoltMatch(nuts, bolts, low, high)

Đầu vào: Danh sách đai ốc, danh sách bu lông, chỉ số thấp và cao của mảng.

Đầu ra: Hiển thị đai ốc nào cho bu lông nào.

Begin
    pivotLoc := partition(nuts, low, high, bolts[high])
    partition(bolts, low, high, nuts[pivotLoc])
    nutAndBoltMatch(nuts, bolts, low, pivotLoc-1)
    nutAndBoltMatch(nuts, bolts, pivotLoc + 1, high)
End

Ví dụ (C++)

#include <iostream>
using namespace std;

void show(char array[], int n) {
    for(int i = 0; i < n; i++)
        cout << array[i] << " ";
}

int partition(char array[], int low, int high, char pivot) {
    // tìm vị trí chốt cho quick sort
    int i = low;
    for(int j = low; j < high; j++) {
        if(array[j] < pivot) {
            // khi phần tử j nhỏ hơn chốt, hoán đổi i và j
            swap(array[i], array[j]);
            i++;
        } else if(array[j] == pivot) {
            // khi phần tử j giống chốt, hoán đổi j và cuối
            swap(array[j], array[high]);
            j--;
        }
    }
    swap(array[i], array[high]);
    return i;  // vị trí phần tử chốt
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
    if(low < high) {
        int pivotLoc = partition(nuts, low, high, bolts[high]);  // chọn từ bu lông để phân vùng đai ốc
        partition(bolts, low, high, nuts[pivotLoc]);  // đặt vị trí chốt trước vào bu lông
        nutAndBoltMatch(nuts, bolts, low, pivotLoc - 1);
        nutAndBoltMatch(nuts, bolts, pivotLoc+1, high);
    }
}

int main() {
    char nuts[] = {')','@','*','^','(','%','!','$','&','#'};
    char bolts[] = {'!','(','#','%','}','^','&','*','$','@'};
    int n = 10;
    nutAndBoltMatch(nuts, bolts, 0, n-1);
    cout << "After matching nuts and bolts:" << endl;
    cout << "Nuts:  "; show(nuts, n); cout << endl;
    cout << "Bolts: "; show(bolts, n); cout << endl;
}

Kết quả

After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^