讲解：C++ School of Computing and Information Systemson?? ??Stock

Introduction三个stage均已完成，并按照题目要求算法编写School of Computing and Information SystemsCOMP10002 Foundations of AlgorithmsSemester 2, 2017Assignment 2Learning OutcomesInthisprojectyouwilldemonstrateyourunderstandingofdynamicmemoryandlinkeddatastructures,and extend your skills in terms of program design, testing, and debugging. You will also learn aboutgraph labeling, and implement a simple shortest path mechanism (broadly speaking, the equivalentof bubblesort) in preparation for the more principled approaches that are introduced in comp20007Design of Algorithms.Path PlanningAny process that involves movement requires path planning. If we are at location A and wish to getto location B, we seek out and follow the “best” route between them, where “best” might be shortest(in terms of distance), or fastest (in terms of time taken), or cheapest (in terms of cost), or most scenic(in terms of appeal), or any weighted combination of those factors. This simple operation happenswhen we use Google maps, when we request quotes for airline tickets, and when we use our phone torequest an Uber pickup.Rectangular GridsThe founders of Gridsville were a mix of mathematicians and computer scientists. So when theydiscovered an uninhabited rectangular island off the south coast of Antarctica that they could use fortheir new colony, they planned a town using a rectangular grid of streets running north-south and east-west. The diagram on the next page shows the seven north-south streets that they built, and the fiveeast-west streets. Streets are named with digits (“0” to “6”) or letters (“a” to “e”), and intersections arelabeled by their locations on the grid that results, for example, “4c”. (They were very boring people.)Hundreds of years later, Gridsville is finally getting an Uber-like service, provided courtesy of theGridsville City Council (gcc, get it?). But the Gridsville Council has remained very traditional andis insisting that pick-ups and drop-offs may only happen at street corners, that is, locations that areaddressable via the grid coordinates. To help prepare for the arrival of the new service, the Council hasapproached a local software company, Algs-R-Fun, and has commissioned software to help managethe vehicle fleet. In particular, each time a customer (standing at an intersection in the grid) calls for apickup, the “best available” car should be directed to go and pick them, where “best” means “the onethat can get there the fastest”. The Council has already collected some travel-time measurements, andhas recorded for each street, and for each city block on that street, how long it takes to travel in thatdirection along that block. For example, looking at Figure 1, travel east from “4c” to “5c” takes 34seconds. Some streets cannot be used in some directions because they are one-way, and in that casethe Council notes them as having a cost of 999 seconds. In the example in Figure 1, it is not possibleto travel south from “4c” to get to “4d”.Stage 1 – Reading the Data (marks up to 8/15)Write a program that reads data from stdin in the format illustrated on the right-hand side of Figure 1(see test2.txt linked from the LMS page for the full file) where the two numbers on the first lineare always the grid dimensions, x and y (they will be 7 and 5 respectively for Gridsville, but might bedifferent for other towns elsewhere in the world, and the GCC has bold ideas about being able to sell13 0 1 2 4 5edcba6349999389101781526Input test2.txt39 lines in total:7 50a 9 999 999 381a … 999 … …2a … 999 … ……4c 34 15 26 999…4e … … … 9995e … … … 9996e 999 10 17 9994c5c1eFigure 1: Street layout in Gridsville. Intersections are labeled by their grid coordinates. See the FAQpage for the full test2.txt input file for this example.their software to other towns), followed by x×y lines, each line describing the travel times out of oneintersection; and where “…” in the figure represent further integer values. Those x × y lines (35 ofthem for GrC++代写 School of Computing and Information Systemson?? ??Stoidsville) will always be presented in row-at-a-time order of intersection name, and eachintersection name will always be an integer immediately followed by a single alphabetic characterstarting from a, and is followed by exactly four more integers on that line, representing the time inseconds needed to travel (respectively) one block east, one block north, one block west, and one blocksouth of that intersection.Your program should build an internal representation of the specified intersections, using structswhereeverappropriate. Youmayassumethatallinputfilesyouwillbeprovidedwithwillbe“correct”,according to the description given above, that all of the times will be strictly positive integers, and thatthere won’t be any tricksy-wicksy special cases introduced during the testing, nor any missing lines,nor any incorrect or wacky values in the lines; but you may not assume any upper limit on the numberof streets involved in the city grid. Note also that the input values will be int, to keep it simple andavoid the rounding problems associated with floating point representations.The grid size line and grid cost data lines are is followed by a third section of data in the input file:one or more grid references, one per line. You are also to read those grid references into a suitabledata structure. Required output from this stage is the following summary:mac: ass2-soln >>> 27S3: | ^ ^ ^ ^ vS3: | ^ ^ ^ ^ vS3: c | 42 43 25 26 >>> 26 >>>> 60 8 47S3: | ^ ^ ^ v ^S3: | ^ ^ ^ v ^S3: e | 13 >>> 5 >>>> 26 >>>> 70 26 >>>> 37Figure 2: Example of Stage 3 output. More examples are linked from the FAQ page. If there isdisagreement between the examples on the FAQ page and this handout, follow the ones in the FAQ.The boring stuff…This project is worth 15% of your final mark. A rubric explaining the marking expectations will beprovided on the FAQ page.Submission will again be done via dimefox and the submit system. You can (and should) usesubmit both early and often – to get used to the way it works, and also to check that your programcompiles and executes correctly on our test system, which has some different characteristics to the labmachines. Only the last submission that you make before the deadline will be marked.You may discuss your work during your workshop, and with others in the class, but what getstyped into your program must be individual work, not copied from anyone else. So, do not give hardcopy or soft copy of your work to anyone else; do not “lend” your “Uni backup” memory stick toothers for any reason at all; and do not ask others to give you their programs “just so that I can takea look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regardis to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out thatyour “no”, and their acceptance of that decision, is the only thing that will preserve your friendship.A sophisticated program that undertakes deep structural analysis of C code identifying regions ofsimilarity will be run over all submissions in “compare every pair” mode. Students whose programsare so identified will be referred to the Student Center for possible disciplinary action without furtherwarning. This message is the warning. See formore information. Note also that solicitation of solutions via posts to online forums, whether or notthere is payment involved, is also taken very seriously. In the past students have had their enrolmentterminated for such behavior.Deadline: Programs not submitted by 10:00am on Monday 16 October will lose penalty marksat the rate of two marks per day or part day late. Students seeking extensions for medical or other“outside my control” reasons should email as soon as possible afterthose circumstances arise. If you attend a GP or other health care professional as a result of illness, besure to take a Health Professional Report form. with you (get it from the Special Consideration sectionof the Student Portal), you will need this form. to be filled out if your illness develops in to somethingthat later requires a Special Consideration application to be lodged. You should scan the HPR formand send it in connection with any non-Special Consideration assignment extension requests.Marks and a sample solution will be available on the LMS before Tuesday 31 October.And remember, algorithms are fun!4转自：http://ass.3daixie.com/2019030464070312.html