问题描述
根据某市地铁线路图写一个地铁票价计算程序需求描述：1.计费规则：最低2元，超过5站以上每站加收0.5元，换乘重新起算，例如L1先坐4站，换乘L2再坐6站，结果就是2+2.5=5.5元2.程序启动以后读取输入文件（in.txt），内容格式如：L2-8,L2-2X3,L3-8....每行表示一次行程，起点站和终点站之间用逗号分隔，行数不限4.系统按最短路径方案（尽量少换乘且站数少，假设乘客换乘一次用的时间相当于坐4个站）规划路线，计算票价，并把路线和票价输出到文件(out.txt)，内容格式如：L2-8,L2-2=2.5:L2-8,L2-7,L2-6,L2-5,L2-4,L2-3,L2-2X3,L3-8=4:X3,X4,L3-8....等号后面的表示票价和路径地铁线路图如下：共有5条线路，X开头的站点表示换乘车站
解决方案
解决方案二：
没做过但是觉得可以看看数据结构里面有一个图结构有个计算最大最小路径的算法可以做最短路程的计算不过这个系统要是比较大的话我还是觉得路线肯定是固定的不如把所有两站之间的最短距离算出来直接全都枚举出来即使用算法在系统初始化的时候一次把所有的A站-》B站之间的最短路线算出来后面就可以直接从内存中获取应该很快毕竟这个数据量其实不是很大而且系统比较大要是每次都去计算就算算法再好也比较慢吧
解决方案三：
因为地铁站是固定的所以按照初次加载所有两站之间最短路线的方式的话数据也是固定的（1）如果两站在同一个地铁线上那就不用换乘很容易计算（2）剩下的就是做一个算法把不在同一条地铁线上的算出来加载到map中在服务器上开辟一段内存把这些数据加载上因为这些数据肯定是固定的所以数据变化可能性比较小适合这样做不过要考虑遇到非常情况比如地铁坏了或者其他事故导致某条线路某段-某段之间不能正常运行所以这个时候可以使用动态算法应急等这一段修复了就继续使用静态数据方式
解决方案四：
packagecom.test.test;importjava.util.HashMap;importjava.util.HashSet;importjava.util.Iterator;importjava.util.Map;importjava.util.Set;publicclassTest3{staticMap<Integer,Station>stationMap=newHashMap<Integer,Station>();publicstaticvoidmain(String[]args){Stationstation1=newStation(1,"1号线第一站",true,false);Stationstation2=newStation(1,"1号线第二站",false,false);station1.setNextStation(station2);Stationstation3=newStation(1,"第三站",false,true);station3.addTransferStations(2);station2.setNextStation(station3);Stationstation4=newStation(1,"1号线第四站",true,false);station3.setNextStation(station4);Stationstation21=newStation(2,"2号线第一站",true,false);Stationstation22=newStation(2,"2号线第二站",false,false);station21.setNextStation(station22);Stationstation23=newStation(2,"第三站",false,true);station23.addTransferStations(1);station22.setNextStation(station23);Stationstation24=newStation(2,"2号线第四站",true,false);station23.setNextStation(station24);stationMap.put(1,station1);stationMap.put(1,station21);intn=getPosition(station1,"1号线第一站","1号线第四站",0);System.out.println(n);}/***计算站点间距离*@paramstation*@paramstart*@paramend*@paramstationNum前面已经经过几站*@return*/publicstaticintgetPosition(Stationstation,Stringstart,Stringend,intstationNum){Iterator<Station>it=station.iterator();StationstartStation=null;while(it.hasNext()){//找到起始站Stations=it.next();if(s.getStationName().equals(start)){startStation=s;break;}}Stationnext=startStation.getNextStation();intnum=1;while(!next.getStationName().equals(end)){next=next.getNextStation();if(next==null){return-1;//不可达}if(next.isTransfer){//如果是换成站//循环所以可以换成的路线递归调用getPosition}else{//如果不是换成站}num++;}returnstationNum+num;}/***站点类*@authorAdministrator**/staticclassStationimplementsIterable<Station>{privateintlineNum;//几号线privateStringstationName;//站名privatebooleanisStartOrEnd;//是否是首站或末站privatebooleanisTransfer;//是否是换乘站privateStationnextStation;//該号线的下一站privateStationpreStation;//上一站privateSet<Integer>transferStations;//可以换乘那几号线publicStation(intlineNum,StringstationName,booleanisStartOrEnd,booleanisTransfer){this.lineNum=lineNum;this.stationName=stationName;this.isStartOrEnd=isStartOrEnd;this.isTransfer=isTransfer;}publicintgetLineNum(){returnlineNum;}publicvoidsetLineNum(intlineNum){this.lineNum=lineNum;}publicStringgetStationName(){returnstationName;}publicvoidsetStationName(StringstationName){this.stationName=stationName;}publicbooleanisStartOrEnd(){returnisStartOrEnd;}publicvoidsetStartOrEnd(booleanisStartOrEnd){this.isStartOrEnd=isStartOrEnd;}publicbooleanisTransfer(){returnisTransfer;}publicvoidsetTransfer(booleanisTransfer){this.isTransfer=isTransfer;}publicStationgetNextStation(){returnnextStation;}publicvoidsetNextStation(StationnextStation){this.nextStation=nextStation;}publicStationgetPreStation(){returnpreStation;}publicvoidsetPreStation(StationpreStation){this.preStation=preStation;}publicSet<Integer>getTransferStations(){returntransferStations;}publicvoidaddTransferStations(IntegertransferStation){if(transferStations==null){transferStations=newHashSet<Integer>();}transferStations.add(transferStation);}@OverridepublicStringtoString(){return"开始站--->[lineNum="+lineNum+",stationName="+stationName+",isStartOrEnd="+isStartOrEnd+",isTransfer="+isTransfer+"]";}@OverridepublicIterator<Station>iterator(){returnnewStationIterator(this);}}staticclassStationIteratorimplementsIterator<Station>{privateStationstation;publicStationIterator(Stationstation){this.station=station;}@OverridepublicbooleanhasNext(){returnstation!=null;}@OverridepublicStationnext(){Stationtemp=station;this.station=temp.getNextStation();returntemp;}@Overridepublicvoidremove(){}}}
写了一部分，目前只可以算在同一号线上的距离。
解决方案五：
。。。这面试题，我刚做完packageorg.train.test;importjava.util.*;publicclassMain{publicstaticvoidmain(Stringargs[]){Scannercin=newScanner(System.in);Stringstation="A1A2A3A4A5A6A7A8A9T1A10A11A12A13T2A14A15A16A17A18B1B2B3B4B5T1B6B7B8B9B10T2B11B12B13B14B15";String[]stations=station.split("");intlength=stations.length;int[][]arr=newint[length][length];HashMap<String,Integer>stationMap=newHashMap<String,Integer>();for(inti=0;i<stations.length;i++){stationMap.put(stations[i],i);}for(inti=0;i<length;i++){for(intj=0;j<length;j++){if(i==j){arr[i][j]=0;}else{arr[i][j]=1000;}}}for(inti=0;i<length-1;i++){arr[i][i+1]=1;arr[i+1][i]=1;}arr[9][25]=0;arr[14][31]=0;arr[25][9]=0;arr[31][14]=0;arr[stationMap.get("A18")][stationMap.get("B1")]=1000;arr[stationMap.get("B1")][stationMap.get("A18")]=1000;arr[stationMap.get("A1").intValue()][stationMap.get("A18").intValue()]=1;//Floyd算法求解for(intk=0;k<length;k++){for(inti=0;i<length;i++){for(intj=0;j<length;j++){if((arr[i][k]+arr[k][j])<arr[i][j]){arr[i][j]=arr[i][k]+arr[k][j];}}}}while(cin.hasNext()){Stringstate1=cin.next();Stringstate2=cin.next();inti=stationMap.get(state1);intj=stationMap.get(state2);System.out.println(arr[i][j]+1);}}}祝你北京面试成功
解决方案六：
引用4楼shibing624的回复:
。。。这面试题，我刚做完packageorg.train.test;importjava.util.*;publicclassMain{publicstaticvoidmain(Stringargs[]){Scannercin=newScanner(System.in);Stringstation="A1A2A3A4A5A6A7A8A9T1A10A11A12A13T2A14A15A16A17A18B1B2B3B4B5T1B6B7B8B9B10T2B11B12B13B14B15";String[]stations=station.split("");intlength=stations.length;int[][]arr=newint[length][length];HashMap<String,Integer>stationMap=newHashMap<String,Integer>();for(inti=0;i<stations.length;i++){stationMap.put(stations[i],i);}for(inti=0;i<length;i++){for(intj=0;j<length;j++){if(i==j){arr[i][j]=0;}else{arr[i][j]=1000;}}}for(inti=0;i<length-1;i++){arr[i][i+1]=1;arr[i+1][i]=1;}arr[9][25]=0;arr[14][31]=0;arr[25][9]=0;arr[31][14]=0;arr[stationMap.get("A18")][stationMap.get("B1")]=1000;arr[stationMap.get("B1")][stationMap.get("A18")]=1000;arr[stationMap.get("A1").intValue()][stationMap.get("A18").intValue()]=1;//Floyd算法求解for(intk=0;k<length;k++){for(inti=0;i<length;i++){for(intj=0;j<length;j++){if((arr[i][k]+arr[k][j])<arr[i][j]){arr[i][j]=arr[i][k]+arr[k][j];}}}}while(cin.hasNext()){Stringstate1=cin.next();Stringstate2=cin.next();inti=stationMap.get(state1);intj=stationMap.get(state2);System.out.println(arr[i][j]+1);}}}祝你北京面试成功
哪个公司的？