Слово недетерминированный можно было не писать, так как цикл Дейкстры, который ввел Дейкстра, он по определению недетерминированный. В языке Оберон-07 есть цикл Дейкстры, но он детерминированный, то есть он не совсем цикл Дейкстры. Ну ладно, вопрос в том, как реализовать настояций цикл Дейкстры на Оберон-07.
Я реализовал один вариант (вы его можете приспособить под свои нужды, если замените существующие модули Console и Random на свои):
Код:
MODULE Nondeterminate;
IMPORT
con := Console,
Random;
CONST
MAX_NUM = 10;
VAR
permutation: ARRAY MAX_NUM OF INTEGER;
PROCEDURE RandomPermutation(n: INTEGER);
VAR
i: INTEGER;
j: INTEGER;
rnd: INTEGER;
choosen: ARRAY MAX_NUM OF BOOLEAN;
BEGIN
FOR i := 0 TO n - 1 DO
choosen[j] := FALSE;
END;
FOR i := n TO 1 BY -1 DO
IF i # 1 THEN
rnd := Random.Random() MOD i;
ELSE
rnd := 0;
END;
j := 0;
WHILE choosen[j] OR (rnd # 0) DO
IF ~choosen[j] THEN
rnd := rnd - 1;
END;
j := j + 1;
END;
choosen[j] := TRUE;
permutation[n - i] := j;
END;
END RandomPermutation;
PROCEDURE PrintPermutation(n: INTEGER);
VAR
i: INTEGER;
BEGIN
FOR i := 0 TO n - 1 DO
con.Int(permutation[i]); con.Str(" ");
END;
con.Ln;
END PrintPermutation;
PROCEDURE Test1(n: INTEGER);
BEGIN
WHILE n MOD 2 = 0 DO
con.Int(2); con.Str(" ");
n := n DIV 2;
ELSIF n MOD 3 = 0 DO
con.Int(3); con.Str(" ");
n := n DIV 3;
ELSIF n MOD 5 = 0 DO
con.Int(5); con.Str(" ");
n := n DIV 5;
END;
con.Ln;
END Test1;
PROCEDURE Test2(n: INTEGER);
VAR
step: INTEGER;
continue: BOOLEAN;
BEGIN
continue := TRUE;
WHILE continue DO
RandomPermutation(3);
continue := FALSE;
step := 0;
WHILE (step < 3) & ~continue DO
continue := TRUE;
IF (permutation[step] = 0) & (n MOD 2 = 0) THEN
con.Int(2); con.Str(" ");
n := n DIV 2;
ELSIF (permutation[step] = 1) & (n MOD 3 = 0) THEN
con.Int(3); con.Str(" ");
n := n DIV 3;
ELSIF (permutation[step] = 2) & (n MOD 5 = 0) THEN
con.Int(5); con.Str(" ");
n := n DIV 5;
ELSE
continue := FALSE;
step := step + 1;
END;
END;
END;
con.Ln;
END Test2;
BEGIN
Random.Randomize();
Test1(466560000);
Test2(466560000);
END Nondeterminate.
Test1 раскладывает число на множители 2, 3 и 5, используя встроенный цикл Дейкстры, и в результате получается: 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 5 5 5 5.
Test2 эмулирует недетерминированный цикл Дейкстры и в результате получается примерно такая последовательность: 3 2 3 2 2 5 3 5 3 3 5 5 2 2 3 2 2 2 2 2.
Может быть у кого-то будут идеи как можно лучше эмулировать недетерминированность.