ГЛЮКОМОРЬЕ
                               by Sassa


...а как было обещано в прошлом нумере, вот решения к задачам.

Задачка про свап чисел.

Решений пришло множество, все хороши, и выделить особенно некого.

Все решения сводятся к такому:

    в одну  из  переменных  заносится  разница  двух  чисел ( то ли это
разность,  то ли это XOR-маска, то ли еще что (а что еще?) ). Следующим
шагом   вторая   переменная,   с  использованием  этой  маски  получает
модифицированное значение  --  значение  первой  переменной.  Теперь  с
помощью  все той же маски и второй переменной ( которая теперь содержит
значение первой ) получаем начальное значение второй переменной.

( хихик-с! во, наговорил! J
...
a=a+b;
b=a-b;
a=a-b;
...




Задачка про сортировку чисел.

    Решений на эту задачку пришло очень мало.  То есть,  одно.  ;(  Это
анонимная группа студентов из конференции RELCOM.COMP.LANGS.C-C++

    Задача сводится   к  сортировке  двух  чисел.  А  три  числа  можно
отсортировать так:

Swap( a, b );
Swap( a, c );
Swap( b, c );

    где функция Swap( x,  y ) возвращает в x - максимальное из x и y, а
в y - минимальное.

    Понятно, что   таким   образом   конечное  количество  чисел  можно
отсортировать, написав соотвествующую конечную программу. ;)

    Вышеупомянутой Группой студентов была предложена такая функция Swap
( x, y ):

void Swap( int &x, int &y ){
  int z=x+y;
  int c=abs(x-y);

  x=(z+c)/2;
  y=(z-c)/2;
};

    Очевидно, что  эта  программа  легко  модифицируется  для  работы с
действительными числами.

    Эта задача очень похожа на предыдущую,  с той  лишь  разницей,  что
стоит задача найти не просто разность чисел,  а найти разность большего
и меньшего  чисел,  и  никогда  не  наоборот.  Именно  эта  разность  и
вычисляется в c.

    Да, правда, еще загвоздка: теперь нужно к минимальному _прибавить_,
а из максимального _вычесть_ эту разность,  и  поместить  результаты  в
соответствующие  переменные.  Тут  трудно  сказать,  как до этого можно
додуматься, отметим только, что это выглядит так:

x=(z+c)/2=(x+y+c)/2 <=> x=((max+min)+(max-min))/2=2*max/2=max

y=(z-c)/2=(x+y+c)/2 <=> y=((max+min)-(max-min))/2=2*min/2=min



МОЛОДЦЫ!

( а что еще я могу сказать?.. ;)

    ...а если говорить об авторском  решении,  то  мне  оно  больше  не
нравится после решения студентов :-|.
    Оно не такое строго математическое, а скорее алгоритмическое:

однако, здесь используется дополнительная функция sgn...

function sgn( f:integer ):integer;
{
 SGN=1, f>=0
 SGN=0, f<0
}

begin
    sgn:=(f+1) div (abs( f )+1);  {нетрудно сделать trunc... и
оперировать с real}
end;

procedure Swap( var a, b:integer );
{
  a=max( a, b );
  b=min( a, b );
}

var f:integer;
begin
  f:=b-a;
  f:=f*sgn(f);

  a:=a+f;
  b:=b-f;
end;

    Здесь хитрость   в   функции   SGN:   возвращает   0,   если  число
отрицательное, 1 в противном случае:

Если f>0, то abs(f)=|f|=f => f/|f|==1.
    Если f<0,  то |f|>f => f/|f|<1 => [ |  (f/|f|)  |  ]=0  --
целая часть от модуля отношения.

    Однако, чтобы не было  деления  на  ноль,  добавим  к  числителю  и
знаменателю по 1. Для целых чисел операция [ | a/b | ] сводится к a div
b.

Теперь, после

f=b-a;
f=f*sgn(f);

    будет f==b-a,  если b-a>0 => b>a.  К a нужно прибавить (b-a). Что и
будет сделано.  f==0,  если b-a<0 => b<a.  Оставить все как есть. Что и
будет сделано.


--

Sassa

       _____
     @()(_)
     /\\