Em Andamento

Data Structures Help in C++

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, visual c++ programming, vector vector int, vector problem examples, vector int int, vector int, vector in c, use of data structures, use of algorithm in programming, track 1 data, test data generator, test code generator, structures data, storage data structures, stack programming, stack in data structures, stack data structures, sorting of data, sorting method, sorting in data structures, sorting in algorithm, sorting data structures, sorting array algorithm, sorting algorithm examples, size of vector

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

ID do Projeto: #2968885

Premiar a:

projetcoder

See private message.

$15 USD em 3 dias
(39 Avaliações)
5.0

2 freelancers estão ofertando em média $15 para este trabalho

shashikhanvw

See private message.

$15.3 USD in 3 dias
(15 Comentários)
3.8