C代写|C语言代写|算法|数据结构:该题目通过基因知识的场景，实际训练C编程能力和一般的算法设计能力
ECE368 Programming Assignment
Description
This programming assignment is to be completed on your own. You will implement a pro-gram involving perhaps graph traverals to compute the packing of rectangles, represented bya sequence pairSP(S 1 ,S 2 ). Suppose thenrectangles are labeled 1 throughn, a sequence is apermutation of thenintegers. Consider a problem instance of 8 rectangles,( 1 , 7 , 4 , 5 , 2 , 6 , 3 , 8 )is a sequence, and( 8 , 4 , 7 , 2 , 5 , 3 , 6 , 1 )is also a sequence. Together, they form a sequence pairSP(( 1 , 7 , 4 , 5 , 2 , 6 , 3 , 8 ),( 8 , 4 , 7 , 2 , 5 , 3 , 6 , 1 )).The order in which a rectangle appear in the two sequences determines its relative positionswith respect to other rectangles. Given a rectanglexin a sequence pairSP(S 1 ,S 2 ), the list ofrectangles that appear beforexin bothS 1 andS 2 are located to the left ofxin the packing. Allrectangles that appear afterxin bothS 1 andS 2 are located to the right ofxin the packing. Rectan-gles that appear afterxinS 1 but beforexinS 2 are located belowxin the packing. Rectangles thatappear beforexinS 1 but afterxinS 2 are located abovexin the packing.To compute the coordinates of the rectangles in the packing, we can use a directed graph calledHorizontal Constraint Graph (HCG) to represent the right-of and left-of relation, where adirected edgea,bmeans that rectangleais to the left ofb. The weight of the edgea,bis thewidth of rectanglea. We add a source nodesand connect it to all nodes in HCG with zero-weightedges. We also add a sink nodetand connect all nodes in HCG to it. The weights of these edgesare the widths of the originating nodes. Thexcoordinate of a rectangle in the packing is given bythe longest path from the source to the corresponding node in HCG. The width of the boundingrectangle containing the packing is the longest path from the source to the sink. The left figurein the following shows the HCG of the sequence pairSP(( 1 , 7 , 4 , 5 , 2 , 6 , 3 , 8 ),( 8 , 4 , 7 , 2 , 5 , 3 , 6 , 1 )),whereas the right figure shows the same HCG except that transitive edges are removed for clarity.An edgea,cis transitive if there exists a nodebsuch thatacan reachcthroughb, i.e., edgesa,bandb,cexist.
Likewise, we can use a Vertical Constraint Graph (VCG) to represent the above and belowrelation, where a directed edgea,bmeans that rectangleais belowb. The weight of the edge
a,bis the height ofa. We add a source node and coonect it to all nodes in VCG with zero-weightedges, and add a sink node and connect all nodes in VCG to it with edges whose weights are theheights of the originating rectangles. Theycoordinate of a rectanlge in the packing is given bythe longest path from the source to the corresponding node in VCG. The height of the boundingrectangle containing the packing is the longest path from the source to the sink. The followingfigure shows the VCG of the sequence pairSP(( 1 , 7 , 4 , 5 , 2 , 6 , 3 , 8 ),( 8 , 4 , 7 , 2 , 5 , 3 , 6 , 1 )), with thetransitive edges are removed for clarity.
Assuming that the (width, height) of the rectangles 1 through 8 are{( 2 , 4 ),( 1 , 3 ),( 3 , 3 ),( 3 , 5 ),( 3 , 2 ),( 5 , 3 ),( 1 , 2 ),( 2 , 4 )}. The following figure shows the longest paths from the source nodeto the sink node in (a) HCG and (b) VCG. The numbers next to each node denotes its width (inHCG) or height (in VCG). The longest paths from the source to each node in HCG and VCG,respectively, give thexandycoordinates of each rectangle. The figure to the right of (a) and (b)shows the packing based on the sequence pairSP(( 1 , 7 , 4 , 5 , 2 , 6 , 3 , 8 ),( 8 , 4 , 7 , 2 , 5 , 3 , 6 , 1 )).
Deliverables:
You are to develop your own include fileseqpair.hand source filesseqpair.candseqpairmain.c,which can be compiled with the following command:
gcc -std=c99 -Wall -Wshadow -Wvla -pedantic -O3 seqpair.c seqpairmain.c -oproj
(While developing your program, you should use the flag-ginstead of the flag-O3so that youcan debug your program more effectively.)To run the program,
./proj5 inputfile outputfile
where theinputfileis the filename of an input file andoutputfileis the filename of theoutput file. The formats of the input file and the output file are explained below.
Format of Input File
The input file is divided into three sections. The first section is a line that contains the numberof rectanlges (in format"%d\n") you have to pack.The second section specifies the dimensions of the rectangles, with each line specifiying thelabel, width, and height of a rectangle (in format"%d(%le,%le)\n"). This is similar how the labeland dimensions of a rectangle are specified in PA3.Ifnis the number of rectangles specified in the first line of the input file, the nextnlines ofthe file specifies the label and dimensions of the rectangles. The labels are from 1 throughninascending order.The third section contains 2 lines, with each line containing a permutation of 1throughn. Thefirst line corresponds to the first sequence in the sequence pair, and the second line corresponds tothe second sequence in the sequence pair. In each line, an integer is in the format"%d", and everytwo adjacent integers are separated by a white space.The following corresponds to the input file for the example shown earlier.
8
1(2.000000e+00,4.000000e+00)2(1.000000e+00,3.000000e+00)3(3.000000e+00,3.000000e+00)4(3.000000e+00,5.000000e+00)5(3.000000e+00,2.000000e+00)6(5.000000e+00,3.000000e+00)7(1.000000e+00,2.000000e+00)8(2.000000e+00,4.000000e+00)1 7 4 5 2 6 3 88 4 7 2 5 3 6 1
Format of Output File
The format of the output file is similar to the last output file in PA3. The file should containa line for each rectanlge, with the label,x-coordinate andy-coordinate of the rectangle specifiedin the"%d(%le,%le)\n". The rectangles are ordered from 1 throughn, withnbeing the totalnumber of rectangles.The output file for the example given above should have the following format:
1(0.000000e+00,1.100000e+01)2(3.000000e+00,4.000000e+00)3(6.000000e+00,4.000000e+00)4(0.000000e+00,4.000000e+00)5(3.000000e+00,7.000000e+00)6(6.000000e+00,7.000000e+00)7(0.000000e+00,9.000000e+00)8(0.000000e+00,0.000000e+00)
Grading:
The project requires the submission (through Blackboard) of the source and include files anda 1-page report. Your report should comment on the run-time and space complexity of your algo-rithm. It is best that your run-time is supported by run-times tabulated by executing your programon a set of examples of different numbers of rectangles. The report accounts for 10% of the gradeand the program accounts for 90% of the grade. You should create a zip file called proj5.zip thatcontains all of the above and submit the zip file. For example, you can create a zip file with thefollowing command:
zip proj5.zip seqpair.c seqpair.h seqpair_main.c report.pdf
Getting started:
We provide sample input files for you to evaluate the run-times of your packing program.Four sample input filesr8.sp,r100h.sp,r100v.sp, andr100.spare provided with respectivesolutions:r8.pck,r100h.pck,r100v.pck,r100.pck. In particular,r8.spandr8.pckare theinput and output files for the example used in the description.Two other sample input files are larger but no solutions are provided:r1K.spandr2K.sp.Copy over the files from the Blackboard website. Check out the Blackboard website for anyupdates to these instructions.Start packing!