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; }
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
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
广告