Листинг 6. Модуль Pascaline.
Реализация треугольника Паскаля через динамические сегменты

PROCEDURE Segment (s,t: SHORTINT): LONGINT;
VAR k: INTEGER;
BEGIN (* обращение к одномерному массиву через динамические сегменты *)
  k := (((s+3) DIV 2)-1) * ((s+2) DIV 2) + t;
  (* вычисление индекса *)
  ASSERT(pas[k] > 0);
  (* проверка на инициализацию элемента *)
  RETURN pas[k]
END Segment;

PROCEDURE LoadPas;
VAR s,t,size: SHORTINT; k: INTEGER;
BEGIN (* заполнение массива готовыми значениями *)
  FOR k := 0 TO MaxPasINDEX-1 DO
    pas[k] := -1;
  (* для контроля за заполнением *)
  END;
  pas[0] := 6;
  (* первый элемент знаем *)
  k := 1; (* индекс массива pas *) s := 1;
  (* номер сегмента *)
  REPEAT (* цикл по сегментам *)
    size := ((s+4) DIV 2) - 1;
    (* кол-во элементов в сегменте *)
    t := 0;
    (* индекс внутри сегмента *)
    WHILE (k < PasCOUNT) & (t < size) DO
    (* цикл внутри сегмента *)
      IF (t = 0) THEN pas[k] := Segment(s-1,0) + (s+3);
      (* ODD — признак нечетности; смотрим посл. эл-ты
         четных сегментов *)
      ELSIF ~ODD(s) & (t = size-1) THEN
        pas[k] := 2*Segment(s-1,size-2);
      ELSE pas[k] := Segment(s-1,t-1) + Segment(s-1,t);
      END;
      INC(t); INC(k)
    END;
    INC(s);
  UNTIL (s > MaxPasINDEX+4);
END LoadPas;

PROCEDURE PascalTriangle2* (i,j: SHORTINT): LONGINT;
VAR k: LONGINT;
BEGIN (* PRE: i >= 0; j >= 0; j <= i; i <= MaxPasINDEX *)
  IF (j = 0) OR (j = i) THEN RETURN 1
  (* стороны треугольника *)
  ELSIF (j = 1) OR (j = i-1) THEN RETURN i
  (* диагонали под сторонами *)
  ELSE (* j <= i; i > 3; j > 1 *)
    IF (j-2 >= ((i DIV 2)-1)) THEN j := i-j END;
    (* за счет симметрии *)
    k := (((i-1) DIV 2)-1) * ((i-2) DIV 2) + (j-2);
    (* нужен индекс *)
    RETURN pas[k]
  END; (* POST: sBadIndex = FALSE *)
END PascalTriangle2;

назад