資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究C++ 程式，用於查詢最接近 S 的 k 個數字，其中 S 是 n 個數字的一組
下列是 C++ 程式，用於查詢最接近 S 的 k 個數字，其中 S 是 n 個數字的一組。
演算法
Begin function partition() for partitioning the array on the basis of values at high as pivot value: Arguments: a[]=an array. l=low H=high Body of the function: Declare variables pivot, in, i Initialize in = l Set pivot = h For i=l to h-1 if(a[i] < a[pivot]) swap a[i] and a[in]) increment in. swap a[pivot] and a[in] return in. End Begin function QuickSort() to implement quicksort algorithm to sort the data elements: Arguments: a[]=an array. l=low h=high Body of the function: declare pindex if(l < h) index = Partition(a, l, h) QuickSort(a, l, pindex-1); QuickSort(a, pindex+1, h); Return 0. End Begin Function main(), If the number of the data element are odd, Assign the middle index to low and the index next to it to high and calculate median. Run a loop for k times and print the element which his closer to the median. Else The median will be an average of two middle values . Run a loop for k times and print the element which his closer to the median. End
示例
#include<iostream>
using namespace std;
void swap(int *x, int *y) { //swapping two values
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
int Partition(int a[], int l, int h) {
int pivot, in, i;
in = l;
pivot = h;
for(i=l; i < h; i++) {
if(a[i] < a[pivot]) {
swap(&a[i], &a[in]);
in++;
}
}
swap(&a[pivot], &a[in]);
return in;
}
int QuickSort(int a[], int l, int h) {
int pindex;
if(l < h) {
pindex = Partition(a, l, h);
QuickSort(a, l, pindex-1);
QuickSort(a, pindex+1, h);
}
return 0;
}
int main() {
int n, i, h, l, k;
double d1,d2, median;
cout<<"Enter the number of element in dataset: ";
cin>>n;
int a[n];
for(i = 0; i < n; i++) {
cout<<"\nEnter "<<i+1<<" element: ";
cin>>a[i];
}
cout<<"\nEnter the number of element nearest to the median required: ";
cin>>k;
QuickSort(a, 0, n-1);
cout<<"The K element nearest to the median are: ";
if(n%2 == 1) {
median = a[n/2];
h = n/2+1;
l= n/2;
while(k > 0) {
if((median-a[l] <= a[h]-median) && l >= 0) {
cout<<" "<<a[l];
l--;
k--;
} else if((median-a[l] > a[h]-median) && h <= n-1) {
cout<<" "<<a[h];
h++;
k--;
}
}
} else {
d1 = a[n/2];
d2 = a[n/2-1];
median = (d1+d2)/2;
h = n/2;
l = n/2-1;
while(k > 0) {
d1 = a[l];
d2 = a[h];
if((median-d2 <= d1-median) && l >= 0) {
cout<<" "<<a[l];
l--;
k--;
} else if((median-d2 > d1-median) && h <= n-1) {
cout<<" "<<a[h];
h++;
k--;
}
}
}
return 0;
}輸出
Enter the number of element in dataset: 7 Enter 1 element: 7 Enter 2 element: 6 Enter 3 element: 5 Enter 4 element: 4 Enter 5 element: 3 Enter 6 element: 2 Enter 7 element: 1 Enter the number of element nearest to the median required: 2 The K element nearest to the median are: 4 3
更新日期：2019-7-30
144 次瀏覽
廣告