Главная Промышленная автоматика.

X[n +1 ] :=х [ 1 ]; у [п +1J :==:у [ 1 ]; b:=true; юг i:=i step 1 until n do M0<y[i]=yO>y[i+l] then beghi

if xO-x[i]<(yO-y[i])X(x[i + l]-x[i])/(y[l+i]-y[i]) then b:=--ib

end; poinLpoI:==-1 b end pointpo;

Свидетельство к алгоритму П2б

Алгоритм И2б является стереотипным переизданием алгоритма И2а.

Свидетельство к алгоргетму И2а

Алгоритм И2а получен в результате исправления и ординарной переработки алгоритма 112 (Shimrat М. «САСМ», 1962, № 8). Кроме внесения поправки, указанной в нижеследующем подтверждении Р. Хакера, в алгоритме 112 сделано изменение, разбивающее логическое выражение в условном операторе на две части для того, чтобы ликвидировать возможное переполнение при делении на {y[i+l]-y[i]), когда одна из сторон многоугольника параллельна оси ОХ (т. е. когда yli + \]y[i]), в трансляторах, всегда вычисляющих логическое вы-ралсеаие полностью.

.Алгоритм был транслирован для треугольника с вершинами (0,0): (2,1 j: (0,3) и для И точек, координаты которых перечислены в табл. 4.

Подтверждение к алгоритму 112

Р. Хакер (Hacker R. «САСМ», 1962, № 12)

Алгоритм 112 был запрограммирован на языке ФОРТРАН для машины IBM 7090. Алгоритм дал удовлетворительные результаты, кроме случая, когда вершинами многоугольника являются (0,0), (1,0), (2,1),(1,2), (0,2).

Т а б л и ц а 4

Результат

Положение точки"1

true

Внутри

false



в этом случае процедура не обнаруживает, что точка (1,1) находится внутри многоугольника. Однако правильный результат был получен после исправления

» (y<y[i]y>y[i + l])A .

if (уО<у[1]уО>у[1-Ы])Л

Свидетельство к алгоритму 1136 [Ml]

Алгоритм 1136 «Сортировка» не публикуется здесь" потому, что соответствующий алгоритм ИЗ (Floyd R. W. «САСМ», 1962, № 8) был позднее заменен более совершенным алгоритмом 245 (Floyd R. W. «САСМ», 1964, № 12).

АЛГОРИТМ 1146

Генератор разбиений с ограничением [А1]

Каждое обращение к процедуре ср generator (сокращение от constraint - ограничение, рагШюпразбиение и generator - генератор) дает очередное разбиение целого числа « на /е частей, каждая из которых не больше h. Любое разбиение представляется массивом частей от р[1] до р[А], где р[1]р[2].. .p\k].

Первое обращение к процедуре производится либо с f=true и 2:=true, если допускаются части, равные нулю, либо с f=true и =false, если желательно получать только ненулевые части. При первом обращении процедура игнорирует массив р, присваивает переменной f значение false и образует начальное разбиение. При последующих обращениях с /false процедура использует исходное разбиение для получения нового разбиения, если оно существует.

Таким образом, будут образованы всевозможные непереставлен-ные разбиения с указанным ограничением, если каждый раз процедура будет оперировать результатами предыдущего обращения. Если следовать этим правилам и обратиться к процедуре первый раз с /=true, г=true, А-п и h=n, то будут получены всевозможные непереставлен-ные разбиения п. При последнем обращении процедура восстанавливает f=true. Входные параметры ограничиваются следующими условиями: >1, /1>1, р[1]р[2]...р[А]. Для zstrue число п ограничивается интервалом Onkh, а для 0=false-интервалом knkh. Нельзя обращаться к процедуре с р[1]-p[k]<2 и /sfalse.

procedure ср generator (n,k,h,z) dataresult: (p,f);

value n,k,h,z; integer n,k,h; Boolean f,z;

integer array p; begin integer a,b,i,j,q;

if-] f then begin a:=p[l]-p[2]-2; j:=2; test: if p[l]-p[j] >2 then go to div;

a:z=a-l-fjX(p[j]-p[j-bl]); j:=j + I; go to test end;

a:= if z then n else n-k; .



р[к]:= if zthen-1 elseO;

f:=false ; j: = k; . " . , .

div: b:=h-1-p[j]; q: = entier a/b); .

for i:-=l step 1 until q do p[i]: = h;

if q=k then go to fin;

for i:=q-t-l step 1 until i do p[i]:=l+ p[j];

i)iq4-l]:=a-bxq + p[q+i]; P[1J-P[k]<2then fin: f:= true end cp generator;

Свидетельство к алгоритму 1146

Алгоритм 1146 является стереотипным переизданием алгорит» ма 114а.

Свидетельство к алгоритму 114а

Алгоритм 114а получен в результате сокращения и ординарной переработки алгоритма 114 (Stockmal F. «САСМ», 1962, № 8).

Алгоритм был транслирован со следующими вариантами исходных данных:

1. п-6; k=4; h=G; /true; z=false.

Результаты

3 111 2 2 11

2. «=6; k=4; ft-6; ftrue; 2=true.

Результаты

6000 3: 00 2220 5100 4110 3111 4200 3210 2211

3. «=20; k=4; h=S; f=true; false.

Результаты

6 662 6644 5555 6653 6554

4. л-4; k=4; h=4; f=true; ,2=true.

Результаты

4000 2200 1111 3 1 0 0 2 1 1 0

АЛГОРИТМ 1156

Генератор перестановок [G6]

Каждое обращение к процедуре perm изменяет порядок первых п компонент массива х, а п\ последовательных обращений дадут вее п\ перестановок этих компонент. Нелокализованная логическая переменная primWb при первом обращении к процедуре perm должна иметь значение true. После первого обращения prim И 5=false и остается та-





0 1 2 3 4 [5] 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

0.0018