Задача по программированию

xoma

мне на собеседовании задали сабж. Помогите, пожалуйста, решить.
Есть двухадресная машина с двумя операциями
+= и -= ( c - шная семантика)
И есть N ячеек памяти R1, R2, ..., RN.
Нужно поменять местами R1 и R2, не изменив R3, ...,RN.
Кстати, не уверен что это вообще можна сделать, но как тогда доказать невозможность.

stm7504407

с такими операциями - нельзя
можно только так:
R1 = R1 + R2
R1 = R1 - R2
R2 = R1 - R2
как еще - я придумать не смог... правда, и думал недолго

ocean

Например так:
R1=A
R2=B
{
R1+=R2 (R1=A+B;R2=B)
R2-=R1 (R1=A+B;R2=B-(A+B)=-A)
R1+=R2 (R1=B;R2=-A)
} повторить 4 раза
Не оптимально, но это первое, что пришло в голову.

stm7504407

так нельзя! у машины есть только те ячейки, которые даны
больше ничего

ARHANGEL-ANGEL

а мне кажется невозможно

ocean

во, блин, нагнал...
сорри...

z731a

а больше ничего и не требуется......

stm7504407

блин, перепутал
р1 = р1 + р2
р2 = р1 - р2
р1 = р1 - р2

ARHANGEL-ANGEL

+= -= это умножение на положительно определенную матрицу а тебе нужно получить отрицательно
(0,1,
1,0)

ARHANGEL-ANGEL

p2=p1-p2 запрещено

galya1

Ты не понял, сложность в том и заключается, что у тебя только операции += и -=, под них твое решение не канает

stm7504407

в этой задаче - да
так как другого алгоритма замены значений я не знаю (и, в общем-то, не думаю, что есть то других очевидных решений не вижу

stm7504407

ежели с пивом подумать, то как-нить хитро можно доказать, что эта задача неразрешима. знать бы только, как доказывается неразрешимость...

G100my

А почему ето решение не подходит, вернее почему оно не верное?

kachokslava

предложил одно из правильных решений.
{
R1+=R2;R2-=R1;R1+=R2
} 4 раза
А вот, к стати, swap без временной переменной с одной операцией ^= ( a=a xor b):

#define swap(a,b) a^=b^=a^=b


реальный код.

Timoha

(a,b)->(b,-a)->(-a,-b)->(-b,a)->(a,b) - получаем то же самое

ocean

ни хрена оно не правильное - тождественное преобразование получилось
а вот дело говорит

z731a

шурикk предложил неправильное решение...... и вообще док-во неразрешимости хронус привел

Slavos

задание было такое, поменять местами заданые 2 элемента массива длины N, так что б В ИТОГЕ остальные элементы остались на своих местах

stm7504407

ни фига, почитай - не изменив ни одного другого! в процессе трогать их нельзя

Slavos

тогда зачем говорилось что есть N ячеек памяти?
сказали бы что их только две
вобстчем советую ещё раз прочитать оригинал условия, если конечно он отличается от приведённого тут

ocean

На решение задачи это не повлияет

stm7504407

точно. если бы не А и В, которые он ввел, я бы сразу решение проверил %)

ocean

Очередное подтверждение ненужности комментариев в программах :-)
Без них всё намного понятнее

xoma

Дельная идея.
из (1, 0, 0, 1) не получить (0, 1, 1, 0) с помощью
преобразований += и -= ( соответствующих матриц я указывать не буду)
Ну это для 2 ячеек а как же для N?
И зачем вообще это N?

Slavos

вариант - научится сдвигать массивы из более чем 3ёх элементов на один такими операциями
тогда задача решена для N > 4

galya1

По-моему, все решил
Неавжно, скока элементов - описаные операции в матричной записи - это умножение на матрицу с положительным определителем
А перестановка двух элементов меняет у определителя знак

laguna1980

а ты случайно не в аспирантуру мехмата устраивался?

xoma

Нет, упаси господи.

z731a

обосрали млин
Оставить комментарий
Имя или ник:
Комментарий: