資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究螺母螺栓問題
給定一份不同的螺母清單和另一份螺栓清單。我們的任務是從給定的列表中找到螺母和螺栓的正確匹配，並在匹配後將該螺母分配給螺栓。
這個問題是透過快速排序技術解決的。透過將螺栓的最後一個元素用作樞軸，重新排列螺母列表並獲得螺栓為樞軸元素的螺母的最終位置。對螺母列表進行分割槽後，我們可以使用選定的螺母對螺栓列表進行分割槽。對左右子列表執行相同的任務以獲得所有匹配項。
輸入和輸出
Input:
The lists of locks and keys.
nuts = { ),@,*,^,(,%, !,$,&,#}
bolts = { !, (, #, %, ), ^, &, *, $, @ }
Output:
After matching nuts and bolts:
Nuts: ! # $ % & ( ) * @ ^
Bolts: ! # $ % & ( ) * @ ^演算法
partition(array, low, high, pivot)
輸入：一個數組、low 和 high 索引、樞軸元素。
輸出：樞軸元素的最終位置。
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(nuts, bolts, low, high)
輸入：螺母列表、螺栓列表、陣列的 lower 和 higher 索引。
輸出：顯示哪個螺母與哪個螺栓匹配。
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
示例
#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;
}輸出
After matching nuts and bolts: Nuts: ! # $ % & ( ) * @ ^ Bolts: ! # $ % & ( ) * @ ^
更新於： 17-06-2020
2K+ 瀏覽量
廣告