The Code-Bin
Links
Home
Add your code!
All Listings
About
Latest Entry
Featured Scripts
Author's Website
Latest Entries
FFMPEG Thumbnail Scr...
PHP, 0.8KB
Jul. 29, 10:24pm
John
Z80 Assembler, 190 bytes
Feb. 17, 3:36am
John
Z80 Assembler, 176 bytes
Sep. 13, 2:19am
John
Z80 Assembler, 77 bytes
Sep. 13, 2:18am
John
Z80 Assembler, 209 bytes
Sep. 13, 2:17am
untitled C++ Code
Posted by: archie | March 21, 2011 @ 8:04am
C++ Code
[
Download
]
// DA_serie03.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <string> #include <iostream> #include <string> using namespace std; static int currentsize=0; void merge(int in[], int l, int m, int r); void sort(int *in); int main() { int testcases ; for ( cin >> testcases ; testcases > 0 ; testcases-- ) { int *values=NULL; cin >> currentsize; values = new int[currentsize]; int element; cin >> element; int length; cin >> length; for (int i = 2; i<currentsize;i++) cin >> values[i-2]; int median = medianOfMedian(values,false); sort(values); int found = values[element]; cout << found << " "<<median << "\n"; delete [] values; } //system("pause"); return 0; } static int medianOfMedian(int* in, bool second){ int length = sizeof(in); if (length<6) return -1; //no medianofmedian, only a median // CHEAT? this is the real median of medians instead of again the median of medians of more groups of 5. if (second) { sort(in); return in[length/2]; } int* currentgroup=new int[5]; //to save the groups of 5 int nrmedians = (length%5==0)?length/5:length/5+1; int* medians=new int[nrmedians]; //to save all the medians /* loop through numbers, make groups of five, sort them and compute their medians*/ for (int s = 0;s<nrmedians;s++){ int j=0; if (s==nrmedians-1) currentgroup= new int[length-s*5]; while (j<5&&j+s*5<length) { currentgroup[j]=in[s*5+j]; j++; } sort(currentgroup); if (j==5||j==4) medians[s]=currentgroup[2]; else if (j==3||j==2) medians[s]=currentgroup[1]; else medians[s]=currentgroup[0]; } if (nrmedians<6) { sort(medians); if (nrmedians==5||nrmedians==4) return medians[2]; else if (nrmedians==3||nrmedians==2) return medians[1]; else return medians[0]; } else return medianOfMedian(medians,true); } static void merge(int *in, int l, int m, int r) { int *out = new int[currentsize]; int i = l; int j = m + 1; int k = l; while (i <= m && j <= r) { // vergleiche von Folgeleementen if (in[i] < in[j]) { out[k] = in[i]; i++; } else { out[k] = in[j]; j++; } k++; } if (i > m) { for (int h = l; h < j; h++) { in[h] = out[h]; } // for (int h = j; h<=r;h++){ // out[h]=in[h]; // k++; // } } else { for (int h = i; h <= m; h++) { out[k + h - i] = in[h]; } for (int h = l; h <= r; h++) { in[h] = out[h]; } } delete [] out; } static void sort(int *in) { int ll = 0, rr = 0, mm = 0; int l = 0; int r = sizeof(in); do { rr = l - 1; while (rr < r) { ll = rr + 1; mm = ll; while (mm < r && in[mm + 1] > in[mm]) { mm++; } if (mm < r) { rr = mm + 1; while (rr < r && in[rr + 1] > in[rr]) { rr++; } merge(in, ll, mm, rr); } else { rr = mm; } } } while (ll != l); }
Syntax Highlighting
[
Open in new window
]
Author Comments
none
Rating
4.50 / 8
184 Votes
http://codebin.yi.org/1178
page generated in 0.01 seconds