Encerrado

Data Structure Help

We manufacture boxes using a machine that make the size of each box based on an a--p random generator. The 2 dimensions of the base of the first box are a and a^2, the second box has dimensions a^3 and a^4, etc. with everything done mod p. We are concerned about whether we can "nest" a lot of boxes so that storage won't be a problem A sequence of boxes can be nested provided that each successive box can be oriented so that its two dimensions are less than or equal to the two dimensions of its predecessor. So a box of size 2 x 9 can be nested in a box of size 9 x 4, but cannot be nested in a box of size 8 x 7. Create a class Nester that contains a method maxNest that is given a,p, and n indicating n/2 boxes that will be manufactured and that returns the largest number of boxes that can be nested in one stack. DEFINITION Class: Nester Method Signature: int maxNest(int a, int p, int n); Your method may assume the following as preconditions: - a and p are between 1 and 2,000,000,000 inclusive and a*p<=2,000,000,000 (so no overlow will occur) - n is an even integer between 1 and 2,000,000 inclusive Here is a test program: int main(){ cout<<"a p n: "; int a,p,n; cin>>a>>p>>n; Nester nester; cout<<"longest nesting is "<<[url removed, login to view](a,p,n)<<endl; return 0; } EXAMPLES 1) a=2 p=17 n=20: return 6 The random sequence produces 2,4 8,16 15,13 9,1 2,4 8,16 15,13 9,1 2,4 8,16 The longest nesting is 3 boxes of size 2,4 nested inside 3 boxes of size 8,16. This is the only way to nest six boxes. (We could nest 5 boxes by nesting 2 of size 9,1 inside 3 of size 8,16) 2)a=10 p=17 n=12 : return 4 10,15 14,4 6,9 5,16 7,2 3,13 -- 10,15 contains 14,4 contains 3,13 contains 7,2 3) a=985 p=2,000,003 n=2,000,000: return 3353 REQUIREMENT: Must perform in less than 30 secs.

## Deliverables

1)Please use the following approach and algorithm:: Start by sorting the boxes according to their smaller dimension. Then the largest collection of nesting boxes is the longest increasing subsequence of the larger dimensions. There is a well known-algorithm for this (which is usually called the "up-sequence" problem) that is O(n*logn). The usual up-sequence algorithm works through the sequence, keeping track of the smallest value that could be the kth (for all k's) in an up-sequence using the values examined so far. So, to find the biggest up-sequence contained in 9,11,4,2,7,5,6 we would keep a vector or array and update it as possible k=1 k=2 k=3 k=4 k=5 k=6 - - - - - - 9 - - - - - 9 11 - - - - 4 11 - - - - 2 7 - - - - 2 5 - - - - 2 5 6 - - - 2)All lines of code must be commented. The program must be run from debug mode within Visual C++ Studio (6.0 or higher).

## Platform

WindowsXP, Visual C++ Studio 6.0( or equiv)

Habilidades: Programação C, Engenharia, MySQL, PHP, Arquitetura de software, Teste de Software

Ver mais: visual studio random number, vector vector int, vector problem examples, vector int int, vector int, use of data structure in programming, use of data structure, track 1 data, test data generator, test code generator, stack programming, stack program in data structure using c, stack of data structure, stack in data structure, stack definition in data structure, stack data structure, stack algorithm in data structure, sorting of data, sorting method, sorting in data structure, sorting in algorithm, sorting data structure, sorting array algorithm, sorting algorithm in data structure, sorting algorithm examples

Acerca do Empregador:
( 2 comentários ) United States

ID do Projeto: #2967779

6 freelancers estão ofertando em média $16 para este trabalho

mihaiscortaru

See private message.

$16.99 USD in 2 dias
(160 Comentários)
6.0
projetcoder

See private message.

$17 USD in 2 dias
(39 Comentários)
5.0
lalesculiviu

See private message.

$17 USD in 2 dias
(18 Comentários)
4.2
negue

See private message.

$15.3 USD in 2 dias
(17 Comentários)
3.3
chippydip

See private message.

$11.05 USD in 2 dias
(0 Comentários)
0.0
kuashavw

See private message.

$17 USD in 2 dias
(0 Comentários)
0.0