面试题 - 副本.docx

Problem one: TrainsThe local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are one-way. That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.Output: For test input 1 through 5, if no such route exists, output NO SUCH ROUTE. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).1. The distance of the route A-B-C.2. The distance of the route A-D.3. The distance of the route A-D-C.4. The distance of the route A-E-B-C-D.5. The distance of the route A-E-D./算法1， 用于查表计算6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B)./算法2，只计算边的条数，使用dfs解决8. The length of the shortest route (in terms of distance to travel) from A to C. /使用经典的最短路径解决9. The length of the shortest route (in terms of distance to travel) from B to B.10. number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC./某个范围内的路径数，。使用dfs解决Test Input:For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7Expected Output:Output #1: 9Output #2: 5Output #3: 13Output #4: 22Output #5: NO SUCH ROUTEOutput #6: 2Output #7: 3Output #8: 9Output #9: 9Output #10: 7设计方案一、 总体设计分类实现单向图数据输入规则N输入规则1输入规则1结果二、详细设计将以上10个问题，归纳总结为4种问题：1. 15 为一类问题解决思路：将Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7 转为邻接矩阵， 读取相应的权值相加即可。行名代表：from, 列名：to。 -1：没路 ，正数：权值。 例如：A,B,5B,C,4C,D,8D,C,8D,E,6A,D,5C,E,2E,B,3A,E,7ABCDEA-15-157B-1-14-1-1C-1-1-182D-1-18-16E-13-1-1-1转化2. 6,7,10 为一类问题解决思路：1使用DFS（深度优先搜索），2细节上对于6问题，从起点到终点，经历的路线数是小于等于某个值。对于问题7，从起点到终点，经历的路线数是等于某个值。对于问题10，从起点到终点，经历的路线数是小于某个值。6，7每走一条路，累加路的条数，10为累加路的权值。DFS 的设计：以7问为例public void dfs(GraphData data, int maxstops, int tn, int fn, int curstops)/1.递归的出口if(curstops maxstops)return;if(curstops = maxstops)if(fn = tn)System.out.println(log);equalWay+;return;/2.递归遍历到达结点for(int i = 0; i data.getLength(); +i)if(data.getEdge(fn, i) 0)continue;log.add(i);dfs(data, maxstops, tn, i, curstops+1);log.remove(