|
Письма
читателей 24
|
|
Я конечно думал, что заметка про обмен значений переменных вызовет
некоторое количество замечаний, но в таком объёме...;[]
|
|
From: Andy Ice <AndyIce@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:32:19 AM
Subject: Олимпиадные задачи с решениями на Turbo Pascal
Хотелось бы предостеречь от явной ошибки в данном алгоритме. Дело в том, информатика - это, все таки, не "чистая математика", и возможно сразу же в первой строчке получить ошибку переполнения.
Пример:
a, b: Byte;
a0 := 250;
b0 := 200;
Результат? |
|
From: Andrew Ezhguroff <eandr@com2com.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:29:42 AM
Subject: Обмен значений переменных
Здравствуйте.
Если в языке возможны битовые операции с целыми числами (не знаю, есть ли это в TP), то subj можно записать забавнее:
a:=a xor b; {a=a0^b0, b=b0}
b:=a xor b; {a=a0^b0, b=a0^b0^b0=a0}
a:=a xor b; {a=a0^b0^a0=b0, b=a0}
С уважением, Андрей. |
|
From: zugr <zugr@unikon-ua.net>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 2:10:18 PM
Subject: Обмен значений переменных
А на С это ищё красивее:
a^=b;
b^=a;
a^=b;
:-)
|
|
From: Boris Bukh <brbukh@yahoo.com>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 6:20:58 PM
Subject: Неточность в теории
Hello,
В последней рассылке неточность в разделе теория. Если использовать +,- то тогда если нечайно откомпилировать прогу с проверкой переполнения, то тогда можете получить run-time error в самый неприятный момент. Лучше пользоваться xor.
a:=a xor b; {a=a0 xor b0 }
b:=a xor b; {b=a0}
a:=a xor b; {a=b0}
Проблемы в том что это работает только на целочисленных и булевых переменных, а вот на вещественных как быть? Ваш прием на вещественных также не пройдет еще по причине неассоциативности сложения в компьютерной арифметики. Предлагаю выставить эту задачу в раздел "Нерешенные задачи". |
|
From: Serhiy Serbin <serhiys@adarvo.com>
To: sapisoft@yandex.ru
Date: Friday, March 15, 2002, 9:32:38 AM
Subject: Обмен значений переменных
Привет, то что придумали давно не спорю :)) Но знать должен каждый :)) Есть еще один вариант, по идее должен роботать быстрее:
a = a ^ b;
b = a ^ b;
a = b ^ a;
, где = - оператор присваивания, а ^ - xor. К сожалению Паскакаль не знаю, так что в его нотации записать не могу.
Best regards,
Serhiy Serbin |
|
From: Alex <malex@ua.fm>
To: sapisoft@yandex.ru
Date: Friday, March 15, 2002, 2:45:38 PM
Subject: Обмен значений переменных
Hi!
хорошая рассылка! только imho: 1 - мало:(, 2 - только самые известные проблемы!
в рассылке от 11.03.2002 был известный пример Сабжа от HellMan
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
procedure swap(var a, b: char);
begin
if a = b then
exit;
byte(a) := byte(a) xor byte(b);
byte(b) := byte(a) xor byte(b);
byte(a) := byte(a) xor byte(b);
end;
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==
дык этот обмен имеет несложное продолжение на циклический сдвиг n переменных:
procedure rotR(var x1, x2, ...., xn: longint);
begin
x1:= x1 xor x2 xor x3 xor ..... xor xn;
x2:= x1 xor x2 xor x3 xor ..... xor xn;
x3:= x1 xor x2 xor x3 xor ..... xor xn;
.....
xn:= x1 xor x2 xor x3 xor ..... xor xn;
x1:= x1 xor x2 xor x3 xor ..... xor xn;
end;
зы: ну и далее можно развивать экстенсивно....
ззыы: в частности можно любую !ИЗВЕСТНУЮ! (!) перестановку n чисел реализовать - за n+1 строчку!
Gby! Gby! See you later... |
|
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Saturday, March 16, 2002, 6:37:40 AM
Subject: Теоретическая часть: обмен значений переменных
Здравствуйте, Алексей.
Хотелось бы прокомментировать хитрость, которую вы продемонстрировали в теоретическом разделе выпуска 23.
Есть практически аналогичный способ, обеспечивающий нам полную устойчивость. Оператор A := A + B; может выполниться с ошибкой, т.к. никто нам не гарантирует, что размер переменной A позволяет хранить значение суммы A + B. Чтобы избежать такого маленького недоразумения, как переполнение, можно тот же приём проделать через XOR-сумму. Например так:
A := A xor B; {A = a0 xor b0}
B := A xor B; {B = a0 xor b0 xor b0 = a0}
A := A xor B; {A = a0 xor b0 xor a0 = b0}
Ещё хотелось бы предостеречь читателей от типичной ошибки:
Procedure Swap(Var A, B : Integer);
begin
A := A xor B;
B := A xor B;
A := A xor B;
end;
Если такой процедурке задать в качестве параметров одну и ту же переменную, она обнулиться. Т.к. получится, что A и B - это одна и та же переменная, а как известно A xor B = 0. То есть если вы пишите алгоритм, в котором вы не застрахованны от подобного вызова, лучше не жадничать, и выделить лишних несколько байт для обмена через 3-ю переменную. (эта ошибка касается так же обмена через сумму). |
|
Алексей Шамис: От себя хочу добавить, что на существование имеет право любой из представленых алгоритмов, просто каждый из них имеет те или иные ограничения. Начинающему легче понять первый вариант решения задачи, а "продвинутые" программисты могут использовать функцию XOR для сложения чисел. В любом случае, спасибо за активность! |
|
Я конечно думал, что заметка про обмен значений переменных вызовет некоторое количество замечаний, но в таком объёме...;[] |
|
From: Andy Ice <AndyIce@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:32:19 AM
Subject: Олимпиадные задачи с решениями на Turbo Pascal
Хотелось бы предостеречь от явной ошибки в данном алгоритме. Дело в том, информатика - это, все таки, не "чистая математика", и возможно сразу же в первой строчке получить ошибку переполнения.
Пример:
a, b: Byte;
a0 := 250;
b0 := 200;
Результат? |
|
From: Andrew Ezhguroff <eandr@com2com.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:29:42 AM
Subject: Обмен значений переменных
Здравствуйте.
Если в языке возможны битовые операции с целыми числами (не знаю, есть ли это в TP), то subj можно записать забавнее:
a:=a xor b; {a=a0^b0, b=b0}
b:=a xor b; {a=a0^b0, b=a0^b0^b0=a0}
a:=a xor b; {a=a0^b0^a0=b0, b=a0}
С уважением, Андрей. |
|
From: zugr <zugr@unikon-ua.net>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 2:10:18 PM
Subject: Обмен значений переменных
А на С это ищё красивее:
a^=b;
b^=a;
a^=b;
:-) |
|
From: Boris Bukh <brbukh@yahoo.com>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 6:20:58 PM
Subject: Неточность в теории
Hello,
В последней рассылке неточность в разделе теория. Если использовать +,- то тогда если нечайно откомпилировать прогу с проверкой переполнения, то тогда можете получить run-time error в самый неприятный момент. Лучше пользоваться xor.
a:=a xor b; {a=a0 xor b0 }
b:=a xor b; {b=a0}
a:=a xor b; {a=b0}
Проблемы в том что это работает только на целочисленных и булевых переменных, а вот на вещественных как быть? Ваш прием на вещественных также не пройдет еще по причине неассоциативности сложения в компьютерной арифметики. Предлагаю выставить эту задачу в раздел "Нерешенные задачи". |