Pro_1.pas 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111
  1. {序关系计数问题,包括算法1-1,1-2和1-3}
  2. const
  3. MaxN =17;{为了避免高精度计算,N所能达到的最大值}
  4. type
  5. TSet =set of 1..MaxN;
  6. var
  7. Total :Comp;{答案}
  8. F :array[0..MaxN] of Comp;{辅助数组}
  9. N :Integer;
  10. Time :Longint;
  11. procedure Count1(Step,First:Integer;Can:TSet);
  12. {
  13. Step表示当前确定第Step个大写字母
  14. First表示当前大写字母可能取到的最小值
  15. Can是一个集合,集合中的元素是还可以使用的大写字母
  16. }
  17. var
  18. i :Integer;
  19. begin
  20. if Step=N then begin{确定最后一个字母}
  21. for i:=First to N do if i in Can then Total:=Total+1; {Total为统计的结果}
  22. Exit
  23. end;
  24. for i:=First to N do{枚举当前的大写字母}
  25. if i in Can then begin{i可以使用}
  26. Count1(Step+1,i+1,Can-[i]);{添等于号}
  27. Count1(Step+1,1,Can-[i]){添小于号}
  28. end
  29. end;
  30. procedure Main1;{算法1-1}
  31. begin
  32. Time:=-MemL[$40:$6C];
  33. Total:=0;
  34. Count1(1,1,[1..n]);
  35. Inc(Time,MemL[$40:$6C])
  36. end;
  37. procedure Count2(Step,First:Integer;Can:TSet);
  38. {
  39. Step表示当前确定第Step个大写字母
  40. First表示当前大写字母可能取到的最小值
  41. Can是一个集合,集合中的元素是还可以使用的大写字母
  42. }
  43. var
  44. i :Integer;
  45. begin
  46. if Step=N then begin{确定最后一个字母}
  47. for i:=First to N do if i in Can then Total:=Total+1; {Total为统计的结果}
  48. Exit
  49. end;
  50. for i:=First to N do{枚举当前的大写字母}
  51. if i in Can then begin{i可以使用}
  52. Count2(Step+1,i+1,Can-[i]);{添等于号}
  53. if F[N-Step]=-1 then begin
  54. F[N-Step]:=Total;
  55. Count2(Step+1,1,Can-[i]);{添小于号}
  56. F[N-Step]:=Total-F[N-Step]
  57. end else Total:=Total+F[N-Step]
  58. end
  59. end;
  60. procedure Main2;{算法1-2}
  61. begin
  62. Time:=-MemL[$40:$6C];
  63. Total:=0;
  64. FillChar(F,Sizeof(F),$FF);
  65. Count2(1,1,[1..n]);
  66. Inc(Time,MemL[$40:$6C])
  67. end;
  68. procedure Main3;{算法1-3}
  69. var
  70. i,j :Integer;
  71. x :Comp;
  72. begin
  73. Time:=-MemL[$40:$6C];
  74. FillChar(F,Sizeof(F),0);
  75. F[0]:=1;
  76. for i:=1 to n do begin
  77. F[i]:=0;
  78. x:=1;
  79. for j:=1 to i do begin
  80. x:=x*(i-j+1)/j;
  81. F[i]:=F[i]+x*F[i-j]
  82. end
  83. end;
  84. Total:=F[n];
  85. Inc(Time,MemL[$40:$6C])
  86. end;
  87. begin
  88. Write('Input N (1<=N<=',MaxN,'): ');Readln(N);
  89. Main1;
  90. Writeln('Algorithm 1 : ');
  91. Writeln('Total = ',Total:0:0,' Time = ',Time);
  92. Main2;
  93. Writeln('Algorithm 2 : ');
  94. Writeln('Total = ',Total:0:0,' Time = ',Time);
  95. Main3;
  96. Writeln('Algorithm 3 : ');
  97. Writeln('Total = ',Total:0:0,' Time = ',Time)
  98. end.