PRO_3_2.pas 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
  1. Program Pro_3_2; {例3的搜索解法}
  2. Const
  3. Inputfile ='input.Txt'; {输入文件名}
  4. Outputfile ='output.Txt'; {输出文件名}
  5. Max =100; {最多点的数目}
  6. Big =10000; {最大整数值}
  7. Var
  8. F :Text; {文件变量}
  9. Po :Array[1..Max,1..2] Of Integer; {记录各个点的坐标}
  10. Qiu,Pr :Array[1..Max] Of Byte; {记录搜索过程的数组}
  11. Lpr :Integer; {打印数组的长度}
  12. N :Integer; {点的数目}
  13. Min :Real; {最短路径的长度}
  14. Procedure Init; {初始化过程}
  15. Var
  16. I :Integer;
  17. Begin
  18. Assign(F,Inputfile);
  19. Reset(F); {读入数据}
  20. Readln(F,N);
  21. For I:=1 To N Do
  22. Readln(F,Po[I,1],Po[I,2]);
  23. Close(F);
  24. End;
  25. Function Len(P1,P2:Integer):Real; {求两点之间距离的函数}
  26. Begin
  27. Len:=Sqrt(Sqr(Po[P1,1]-Po[P2,1])+Sqr(Po[P1,2]-Po[P2,2]));
  28. End;
  29. Procedure Search(Dep,Fr,Last:Byte;Al:Real); {搜索最短路径}
  30. Var
  31. I,P:Byte;
  32. Rs:Real;
  33. Procedure Did; {将第2条路径的长度加入当前的长度}
  34. Var
  35. K:Byte;
  36. Begin
  37. K:=Fr+1;
  38. Rs:=0;
  39. P:=Last;
  40. While K<>I Do
  41. Begin
  42. Rs:=Rs+Len(P,K);
  43. P:=K;
  44. Inc(K);
  45. End;
  46. Rs:=Rs+Len(Fr,I);
  47. End;
  48. Begin
  49. If Al>=Min Then Exit;
  50. If Fr=N Then
  51. Begin
  52. If Al+Len(Last,N)<Min Then {如果更优,记录}
  53. Begin
  54. Min:=Al+Len(Last,N);
  55. Pr:=Qiu;
  56. Lpr:=Dep-1;
  57. End;
  58. End
  59. Else
  60. For I:=Fr+1 To N Do {访问每一个点}
  61. Begin
  62. Qiu[Dep]:=I;
  63. Did;
  64. Search(Dep+1,I,P,Al+Rs);
  65. End
  66. End;
  67. Procedure Print; {输出数据}
  68. Var
  69. I :Byte;
  70. Se :Set Of Byte; {记录未输出的点}
  71. Begin
  72. Assign(F,Outputfile);
  73. Rewrite(F);
  74. Writeln(F,Min:0:2);
  75. Se:=[1..N];
  76. For I:=1 To Lpr Do
  77. Begin
  78. Write(F,Pr[I],' ');
  79. Se:=Se-[Pr[I]];
  80. End;
  81. Se:=Se+[1,N];
  82. Writeln(F);
  83. For I:=1 To N Do
  84. If I In Se Then
  85. Write(F,I,' ');
  86. Close(F);
  87. End;
  88. Begin
  89. Init; {输入数据}
  90. Min:=Big; {最小值初始化}
  91. Search(1,1,1,0); {搜索最短路径}
  92. Print; {输出结果}
  93. End.