C++ Data Structure Problem
$15-20 USD
着払い
Sorted Vector
----------------
class SortedVector{
public:
void add(double myVal);
// adds myVal to the SortedVector. duplicates are allowed, so myVal is always added
double get(i);
// pre: i < number of values in the SortedVector.
// post: return is the value in position i (position 0 holds the smallest value).
int size(); //returns the number of elements currently in the SortedVector
private:
//.....
};
Implement this class however you can so that each add or get is fast. The class is called SortedVector because it allows you to keep adding values to it, and it behaves as if it keeps them in a vector sorted in ascending order -- [url removed, login to view](3) returns the value that would be in myVec[3].
Here is a test program with some test cases:
a=10 p=17 n=10 ==> 12 ,10 were placed in position 10
a=10 p=100,000,007 n=522 ==> 92884289 was placed in position 522
a=10, p=100,000,007 n=520 ==> 94387374, 58959785 were placed in position 520
a=10, p=17, n=100,000 ==> 16 was placed in position 100,000 at least 20 times
int main(){
cout<<"enter a,p,n "; int a,p,n; cin>>a>>p>>n;
cout<<"storing "<<n<<" values into the SortedVector"<<endl;
SortedVector sv; int val = 1;
for(int i=0; i<n; i++){
val = a*val%p; [url removed, login to view](val);
}
cout<<"finished "<<n<<" adds. Now will add and get "<<n<<" times"<<endl;
int ct=0;
for(int i=0; i<n; i++){
val = a*val%p; [url removed, login to view](val);
if( [url removed, login to view](n)==val && ct++<20 ) cout<< val << " was placed in position "<<n<<endl;
}
return 0;
}
REQUIREMENT: if n is 100,000 this program should finish in less than 30 seconds after entering a,p,n.
## Deliverables
1) I need the problem solved with an efficient algorithm involving data structures so it will complete in a reasonable amount of time.
2)All lines of code must be commented. The program must be run from debug mode within Visual C++ Studio (6.0 or higher).
3)Before coding, please describe how you plan to complete the problem and what algorthims and data structures you plan on using.
## Platform
WindowsXP, Visual C++ Studio 6.0( or equiv)
プロジェクトID: #2965069