Vấn đề về đai ốc và bu lông

Danh sách các loại đai ốc khác nhau và một danh sách các loại bu lông khác được đưa ra. Nhiệm vụ của chúng tôi là tìm sự khớp chính xác của đai ốc và bu lông từ danh sách đã cho và gán đai ốc đó với Bu lông, khi nó được khớp.

Vấn đề này được giải quyết bằng kỹ thuật 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 trục, sắp xếp lại danh sách đai ốc và lấy vị trí cuối cùng của đai ốc có bu lông là phần tử trụ. Sau khi phân vùng danh sách đai ốc, chúng 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ũng được thực hiện cho danh sách phụ bên trái và bên phải để nhận được tất cả các kết quả phù hợp.

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

Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching nuts and bolts:
Nuts:  ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^

Thuật toán

phân vùng (mảng, thấp, cao, tổng hợp)

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

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

Begin
   i := low
   for j in range low to high, do
      if array[j] < pivot, then
         swap array[i] and array[j]
         increase i by 1
      else if array[j] = pivot, then
         swap array[j] and array[high]
         decrease j by 1
   done

   swap array[i] and array[high]
   return i
End

nutAndBoltMatch (đai ốc, bu lông, thấp, cao)

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

Đầu ra: Hiển thị đai ốc nào dùng 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ụ

#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) {    //find location of pivot for quick sort
   int i = low;
   for(int j = low; j<high; j++) {
      if(array[j] <pivot) {    //when jth element less than pivot, swap ith and jth element
         swap(array[i], array[j]);
         i++;
      }else if(array[j] == pivot) {    //when jth element is same as pivot, swap jth and last element
         swap(array[j], array[high]);
         j--;
      }
   }
   swap(array[i], array[high]);
   return i;    //the location of pivot element
}

void nutAndBoltMatch(char nuts[], char bolts[], int low, int high) {
   if(low < high) {
      int pivotLoc = partition(nuts, low, high, bolts[high]);   //choose item from bolt to nut partitioning
      partition(bolts, low, high, nuts[pivotLoc]);    //place previous pivot location in bolt also
      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;
}

Đầu ra

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