[求助]请教一个有趣的c语言题目
是来是布置的作业 先是英文版 然后是我翻译的 请各位高手出手相助啊Chapter 1: Introduction
1.1 Problem description
This project requires us to help Bill to design the electric wiring for his new house.
First of all Bill has fixed the positions of several electrical outlets on the walls. To neatly connect any pair of outlets, we should make sure that the wire is always imbedded in the walls or the floor, and is parallel to at least one side of the wall. Naturally we should minimize the total length of wire he must buy to have all the outlets connected.
By the way, do not forget that there is a door for every room. The wire must not cross the door.
Hint: The house is big for any possibility and the door could be anywhere and also can be a window. And the most import thing is that the wire can’t cross the door and the ceiling but can cross the wall and the floor. Another important thing is that the wire must parallel one of the axes ( x, y, z ).
1.2 Method to measure the performance
While given a test case, the tester can calculate the length between any two distinct adjacent outlets and then generate the minimize length by himself. And then check with the result of the program. If it matches the result, we can say that the program works well. Or if it is smaller then the result, we can say that the program do not work well.
Chapter 2: Algorithm specification
2.1 Representation of graphs
Since it’s very difficult for us to solve the problem in three-dimensional, we change the house into a two-dimensional one.
As the triples of the door and the triples of the culminations of the house are given, so it’s not difficult to project the wall and the door on the floor.
After that the outlets are all on the floor. It means that we now can solve the problem in two-dimensional environment. Then each outlet can seem to be a point in a graph and the length between two points can be calculated by their triples. After that we could build a graph by queue ADT or stack ADT or other.
2.2 Implement of Kruscal’s algorithm
After we have built a graph, we can just use the Kruscal’s algorithm to solve the problem.
Chapter 3 Project Structure
3.1 Overview
The project wants us to find a optimal way to design the electric wiring. To complete the task, we should read the coordinates of the outlets and find the shortest path between each two outlets. Then, our job is finding the Minimum spanning tree. So the tree is the optimal precept, the total value of the tree is the minimum length of wire.
The problem is that the path cannot cross the door! To solve it, we put the four walls into one plane, then, our job is simple enough for us to do. Generally speaking, we need to find three paths between each two outlets, from left, right and floor. Then we say the value of each edge between the two outlets is the shortest one of the three.
Implement Kruskal’s algorithm to find the minimum spanning tree.
3.2 The main program
3.2.1 Details of the main program
1. Use for loop to deal with each case until the fscanf return EOF, which is to say we have dealt with all cases.
2. The main function open two files used in the program (If the “output.txt” file does not exist the program will generate it).
3. For each case, the program will give us a number in the "output.txt", which is the nearest integer length of wire.
4. Our program will close the two file, free all memory we used and then exit at last.
3.2.2 Flow chart of the main program
Chapter 4 Testing results and analysis
We will find that all the test cases are specially designed for the limited conditions the cases are contained in the “input.txt” file.
No. Correct Answers: Answers From "P6.exe"(Before Debugging) Answers From "P6.exe"(After Debugging)
1
2
3
4
5
6
7
8
9
10
11
For each test case, I used a piece of the program to calculate the weight of each edge and sorting, then spanning the tree manually, to find out the answer is right or wrong.
From the table above, we can find that all the answers are correct except the 3rd group. The purpose of the 3rd case is to check what and how the program will do when the connection must around the door. It has proved that the algorithm in the program to solve the crossing problem has a small bug.
Then, the programmer checked his program and found that when the program judged the condition of crossing the door and calculated the weight of the wire had a very silly mistake. Finally, the program had given the right answer. (Look at the table above!)
(The test case was from an accident. I also wrote the project for fun, but my results did not marching the results of the programmer’s. Then I found that in the test case there was a point, which generated by a “rand ()” function, in the door area. But just the wrong test case clued me on that when the program judging whether the wire had crossed door and calculated the wire length, there must bring a problem. Both of us were wrong).
Function Test:
In this part, I had test the function of the program to find out whether it can reach the requirement of Chenyue JJ.
No. Function State
1 The file operation SUCCESS
2 The format of output CORRECT
3 Whether give the result YES
4 The path of the files CORRECT
5 The state of the program STRONG
All the tests had finished, the result has listed above. The state of the program is strong enough to be tested with an enormous data file, which will not be crash.
Chapter 5 Algorithm analysis
5.1 The time complexity and space complexity analysis
5.1.1 The time complexity analysis
5.1.2 The space complexity analysis
5.2 The comments from tester
The program works well. All a word the program is: PASS!!
Duty assignments
Tester:
Programmer:
Reporter:
