PDA

Просмотр полной версии : Деление через сумму и разность (LOOP calculability)



Oscar
11.10.2005, 22:55
Дан LOOP-язык:


Переменные: x1, x2, x3, ...
Константы: 0, 1, 2, ...
Разделительные символы: ";", ":="
Операции: "+", "-"
Ключевые слова: LOOP, DO, END


LOOP-программа это:

1. Присвоение


xi := xj + c;
xi, xj - переменные
c - константа


2. Если P1 и P2 это LOOP-программы, то:


P1; P2
тоже LOOP-программа, причём сначала выполняется P1, а затем P2

3. Если P это LOOP-программа, то:


LOOP xi DO P END
тоже LOOP-программа, причём программа P будет выполняться xi раз
(изменение xi внутри программы P не влияет на колличество повторений)

Примечание:
1. В результате выполнения программы в переменной x0 должен находиться результат вычисляемой функции.
2. В начале все переменные инициализированы в 0.

------------------------------

Задание: реализовать DIV и MOD ф-ции
------------------------------

Подсказки:

1.

IF x1 = 0 THEN A END


x2 := 1;
LOOP x1 DO
x2 := x3 + 0
END;
LOOP x2 DO
A
END



2.

x0 := x1 + x2;


x0 := x1;
LOOP x2 DO
x0 := x3 + 1
END



3.

x0 := x1 * x2;


x0 := 0;
LOOP x1 DO
LOOP x2 DO
x0 := x0 + 1
END
END


--------------

Мой вариант решения:


// x1 := X; // int
// x2 := Y; // int
// x[0] := X div Y;

x3 := x1; // temp1 (decreasing)
x4 := 0; // temp2 (increasing)
x5 := 0; // flag_MOD : (X mod Y != 0)
x6 := 0; // flag_FLAG : (flag_MOD is set!)
x7 := 1; // IF_THEN (first) : temp for (if SOMETHING == 0)
x8 := 1; // IF_THEN (second) : temp for (if SOMETHING == 0)
x9 := 0; // Variable : ZERO

LOOP x1 DO
LOOP x2 DO

x7 := 1; // init
LOOP x6 DO x7 := x9 + 0 END;
LOOP x7 DO // (if x6 == 0)

x8 = 1; // init
LOOP x3 DO x8 := x9 + 0; END;
LOOP x8 DO // (if x3 == 0)
x5 := x5 + 1; // set MOD != 0
x6 := x6 + 1 // set flag_MOD is set to ONE !
END

END;

x3 := x3 - 1 // if (x3 == 0) x3 := 0; else x3 := x3 - 1;
// decrease temp1

END;

x7 = 1; // init
LOOP x3 DO x7 := x9 + 0 END;
LOOP x7 DO
x4 := x4 + 1; // increase temp2
x6 := x6 + 1 // set flag_MOD is set TO ZERO !
END

END;


x0 := x1;
LOOP x4 DO
x0 := x0 - 1 // if (x0 == 0) x0 := 0; else x0 := x0 - 1;
END;


x7 := 1; // init
LOOP x5 DO x7 := x9 + 0 END;
LOOP x7 DO // if (MOD == 0)
x0 := x0 + 1
END;


x7 := 1; // init
LOOP x1 DO x7 := x9 + 0 END;
LOOP x7 DO // if (x1 == 0) -> 0 div int = 0
x0 := x9 + 0
END


Для меня этот код выглядит таким же непонятным, как и для вас!
Это было мною написано, практически, экспериментальным методом.

Может кто-то знает нормальный алгоритм деления :?:
Не обязательно в форме LOOP-языка, лишь бы WHILE не использовался !



P.S.
MOD можно реализовать: x1 - DIV(x1, x2)

хотя кажется мне, что должен быть алгоритм, который одновременно подсчитывает и остаток от деления

Oscar
11.10.2005, 23:06
Читабельный вариант на Java:


public class Loop {

public static void main(String[] args) {
for(int i = 0; i < 32; i ++) {
System.out.println(i+" div 5 = "+div(i, 5));
}
}

private static int dec(int a) {
return (1 >= a)?0:(a-1);
}

private static int div(int X, int Y) {

if (X == 0) return 0; // 0 div int = 0

int[] x = new int[32];
x[0] = 0;
x[1] = X; // input 1
x[2] = Y; // input 2
x[3] = x[1]; // temp1 (decreasing)
x[4] = 0; // temp2 (increasing)
x[5] = 0; // flag_MOD : (X mod Y != 0)
x[6] = 0; // flag_FLAG : (flag_MOD is set!)

for(int i = 0; i < x[1]; i++) {
for(int j = 0; j < x[2]; j++) {

if (x[6] == 0) {
if (x[3] == 0) {
x[5]++; // set MOD != 0
x[6]++; // set flag_MOD is set to ONE !
}
}

x[3]=dec(x[3]); // decrease temp1
}

if (x[3] == 0) {
x[4]++; // increase temp2
x[6]++; // set flag_MOD is set TO ZERO !
}
}

x[0] = x[1] - x[4];

if (x[5] == 0) x[0]++; // if (MOD == 0)

return x[0]; // X div Y
}
}

Oscar
13.10.2005, 16:28
Решил.


public class Loop {
public static void main(String[] args) {

int[] x = new int[32];

x[1] = 13;
x[2] = 5;
x[3] = 0; //DIV calculated (FLAG);
x[4] = 0; //x[0] - x[1]
x[5] = 0; // ~ mod

for(int i = 0; i < x[1]; i++) {

if (x[3] == 0) x[0]++; // 2 LOOPs (length = 2*1 -> 2 lines)

for(int j = 0; j < x[2]; j ++) {
if (x[1] == 0) x[5]++; // 2 LOOPs (length = 2*1 -> 2 lines)
x[1] = dec(x[1]);
}

x[4] = x[0]-x[1]; // 2 LOOPs (length x[0]+x[1])

if (x[4] == 0) x[3]++; // 2 LOOPs (length = 2*1 -> 2 lines)
}

x[0] = dec(x[0]);
if (x[5] == 0) x[0]++; // 2 LOOPs (length = 2*1 -> 2 lines)

if (x[5] == 0) // 4 LOOPs (length = 4*1 -> 4 lines)
x[5] = x[1];
else
x[5] = x[2]-x[5];

System.out.println("DIV = " + x[0]);
System.out.println("MOD = " + x[5]);
}

private static int dec(int x) {
return (x==0)?0:x-1;
}

}