数据结构
网络
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+ 浏览量
广告