C++ Data Structure Problem

完了済み 投稿 Aug 19, 2003 着払い
完了済み 着払い

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)

C プログラミング エンジニアリング MySQL PHP ソフトウェアアーキテクチャ ソフトウェアテスト

プロジェクトID: #2965069

プロジェクトについて

15個の提案 リモートプロジェクト アクティブ Aug 20, 2003

アワード:

mihaidanila

See private message.

$2 USD 5日以内
(12レビュー)
3.3

15人のフリーランサーが、平均$11 で、この仕事に入札しています。

mihaiscortaru

See private message.

$10.2 USD 5日以内
(160件のレビュー)
6.0
emilianbold

See private message.

$8.5 USD 5日以内
(77件のレビュー)
5.8
projetcoder

See private message.

$17 USD 5日以内
(39件のレビュー)
5.0
Uplink03

See private message.

$17 USD 5日以内
(68件のレビュー)
4.8
vw821235vw

See private message.

$8.5 USD 5日以内
(94件のレビュー)
4.3
lalesculiviu

See private message.

$17 USD 5日以内
(18件のレビュー)
4.2
teamvw

See private message.

$17 USD 5日以内
(36件のレビュー)
3.8
vw472664vw

See private message.

$6.8 USD 5日以内
(37件のレビュー)
3.0
vasilevalaiba

See private message.

$17 USD 5日以内
(9件のレビュー)
2.5
codepvw

See private message.

$10.2 USD 5日以内
(9件のレビュー)
2.6
gurux

See private message.

$11.05 USD 5日以内
(4件のレビュー)
2.7
blabbone

See private message.

$17 USD 5日以内
(レビュー1件)
1.9
bruce1970

See private message.

$4.25 USD 5日以内
(5件のレビュー)
1.7
vw914040vw

See private message.

$5.95 USD 5日以内
(16件のレビュー)
1.6