PRO_3_1.pas 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148
  1. Program Pro_3_1; {例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. Dis :Array[1..Max,1..Max] Of Real; {记录动态规划中状态的权值}
  11. N :Integer; {点的总数}
  12. Procedure Init; {初始化过程}
  13. Var
  14. I :Integer;
  15. Begin
  16. Assign(F,Inputfile); {读入数据}
  17. Reset(F);
  18. Readln(F,N);
  19. For I:=1 To N Do
  20. Readln(F,Po[I,1],Po[I,2]);
  21. Close(F);
  22. End;
  23. Function Len(P1,P2:Integer):Real; {求两个点之间的距离}
  24. Begin
  25. Len:=Sqrt(Sqr(Po[P1,1]-Po[P2,1])+Sqr(Po[P1,2]-Po[P2,2]));
  26. End;
  27. Procedure Main; {动态规划过程}
  28. Var
  29. I,J,K :Integer;
  30. Now :Real; {当前最小值}
  31. Begin
  32. Dis[N,N]:=0; {初始化动态规划数组}
  33. For I:=N-1 Downto 1 Do
  34. Begin
  35. Dis[I,N]:=Len(I,I+1)+Dis[I+1,N];
  36. Dis[N,I]:=Dis[I,N];
  37. End;
  38. For I:=N-2 Downto 1 Do {递推最小值}
  39. For J:=N-1 Downto I+1 Do
  40. Begin
  41. If I+1<J Then Now:=Dis[I+1,J]+Len(I,I+1)
  42. Else
  43. Begin
  44. Now:=Big;
  45. For K:=J+1 To N Do
  46. If Dis[K,J]+Len(I,K)<Now Then
  47. Now:=Dis[K,J]+Len(I,K);
  48. End;
  49. For K:=J+1 To N Do
  50. If Dis[I,K]+Len(J,K)<Now Then
  51. Now:=Dis[I,K]+Len(J,K);
  52. Dis[I,J]:=Now;
  53. Dis[J,I]:=Now;
  54. End;
  55. End;
  56. Procedure Print; {输出过程}
  57. Var
  58. X1,X2,I,D :Integer;
  59. Now :Real; {当前最小值}
  60. P :Array[1..2] Of Integer; {打印数组的长度}
  61. Pr :Array[1..2,1..Max] Of Byte; {打印数组}
  62. Ok :Boolean;
  63. Procedure Change; {交换两个数的值}
  64. Var
  65. G :Integer;
  66. Begin
  67. D:=3-D;
  68. G:=X1;X1:=X2;X2:=G;
  69. End;
  70. Begin
  71. Assign(F,Outputfile);
  72. Rewrite(F); {输出数据}
  73. Now:=Big;
  74. For I:=2 To N Do {求最短的路径值}
  75. If Dis[1,I]+Len(1,I)<Now Then
  76. Begin
  77. Now:=Dis[1,I]+Len(1,I);
  78. X2:=I;
  79. End;
  80. X1:=1;
  81. Writeln(F,Now:0:2);
  82. P[1]:=1;P[2]:=1; {打印数组初始化}
  83. Pr[1,1]:=X1;Pr[2,1]:=X2;
  84. D:=1;
  85. While (X1<>N) And (X2<>N) Do
  86. Begin
  87. Ok:=True; {根据动态规划递推规则构造打印数组}
  88. If X1+1<X2 Then
  89. Begin
  90. If Dis[X1+1,X2]+Len(X1,X1+1)=Dis[X1,X2] Then
  91. Begin
  92. Inc(X1);
  93. Inc(P[D]);
  94. Pr[D,P[D]]:=X1;
  95. Ok:=False;
  96. End;
  97. End
  98. Else
  99. Begin
  100. I:=X2+1;
  101. While (I<=N) And ( Dis[I,X2]+Len(X1,I)<>Dis[X1,X2]) Do
  102. Inc(I);
  103. If I<=N Then
  104. Begin
  105. Ok:=False;
  106. X1:=I;
  107. Inc(P[D]);
  108. Pr[D,P[D]]:=X1;
  109. Change;
  110. End;
  111. End;
  112. If Ok Then
  113. Begin
  114. I:=X2+1;
  115. While Dis[X1,I]+Len(I,X2)<>Dis[X1,X2] Do
  116. Inc(I);
  117. X2:=I;
  118. Inc(P[3-D]);
  119. Pr[3-D,P[3-D]]:=X2;
  120. End;
  121. End;
  122. While Pr[D,P[D]]<>N Do
  123. Begin
  124. Inc(P[D]);
  125. Pr[D,P[D]]:=Pr[D,P[D]-1]+1;
  126. End;
  127. For I:=1 To P[1] Do {输出打印数组}
  128. Write(F,Pr[1,I],' ');
  129. Writeln(F);
  130. For I:=1 To P[2] Do
  131. Write(F,Pr[2,I],' ');
  132. Close(F);
  133. End;
  134. Begin
  135. Init; {初始化}
  136. Main; {动态规划递推最短路径}
  137. Print; {输出结果}
  138. End.