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)

Programación en C Ingeniería MySQL PHP Arquitectura de software Verificación de software

Nº del proyecto: #2967779

Sobre el proyecto