Re[2]: f(f(x)) = -x - Этюды для программистов

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

Наверняка не самое короткое решение, но вроде работать будет.

if (x==0) {
  return 0;
}
if (x>0) {
  if (x & 1 == 1) {
    return x+1;
  } else {
    return -x+1;
  }
} else {
  if (x & 1 == 1) {
    return x-1;
  } else {
    return -x-1;
  }
}

Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
целые числа. x — целочисленный аргумент (например, 32-битный).

от avva

Здравствуйте, RomikT, Вы писали:

Я чуть короче решил, но идея аналогичная

f x = if even x then - sign x * (abs x - 1)
                else   sign x * (abs x + 1)

Проверка

*Main1> map (f . f) [-5..10]
[5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10]

Здравствуйте, Панда, Вы писали:

П>Найти функцию f, для которой f(f(x)) — -x
П>x — любое вещественное число без ограничений.

Делов-то...

f(f(x)) = -x
f² = -1
f = i
f(x) = ix

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

R>Ну, например:
R>

R>f(x) = x при x < 0  
R>f(x) = -x при x >= 0
R>

f(-1)=-1
f(f(-1))=-1 != -(-1)

Здравствуйте, rg45, Вы писали:

D>>>

D>>>Задача: написать функцию f(x), так, что f(f(x))= -x. Разрешено использовать только
D>>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>>от avva

R>>Ну, например:
R>>

R>>f(x) = x при x < 0  
R>>f(x) = -x при x >= 0
R>>

f(-1)= -1
f(f(-1))=f(-1)=-1.
лажа, однако.

Здравствуйте, Панда, Вы писали:

П>Подумал. В целом — задача неразрешимая. Потому что есть такое 32-битное x, для которого невозможно записать 32 битами -x. Это число, у которого все биты 1.

П>Если это число выкинуть из допустимых аргументов — то придумал.
П>Продемонстрирую идею такой функции, если x может принимать значения от -3 до 3.
П>

П>int f(int x)
П>{
П>  int y[] = {0, 1, 2, 3, 0, -1, -2, -3};
П>  return y[(x+2)%8];
П>}
П>

f(f(2)) = f(0) = 2
упс.

На языках с динамической типизацией все просто

<?php
function f($x)
{
  if (is_array($x)) return $x[0];
  return array(-$x);
}
?>

Здравствуйте, Панда, Вы писали:

П>На языках с динамической типизацией все просто

Да, прицепить атрибут — это идея

А без этого?

На сях:

int f(int x)
{
    return (x+MAX_INT/2);
}

ой, это я фигню какую-то написал

Подумал. В целом — задача неразрешимая. Потому что есть такое 32-битное x, для которого невозможно записать 32 битами -x. Это число, у которого все биты 1.

Если это число выкинуть из допустимых аргументов — то придумал.
Продемонстрирую идею такой функции, если x может принимать значения от -3 до 3.

int f(int x)
{
  int y[] = {0, 1, 2, 3, 0, -1, -2, -3};
  return y[(x+2)%8];
}

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

Так это невозможно. Отрицательных чисел больше, чем положительных.

Здравствуйте, Vintik_69, Вы писали:

V_>Так это невозможно. Отрицательных чисел больше, чем положительных.

Ну формалист! Откинь одно отрицательное.

Здравствуйте, RomikT, Вы писали:

RT>Наверняка не самое короткое решение, но вроде работать будет.

Не работает для 2147483647

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

int f(int x)
{
    const unsigned int MAX = (1 << 31);
    
    int order = x >= 0 ? x : -x + MAX;
    order = (order + MAX/2);
    if (order < MAX) return order;
    else return -(order - MAX);
}

Кстати, можно сформулировать аналогичную задачу по математике, а не по программированию.
Найти функцию f, для которой f(f(x)) — -x
x — любое вещественное число без ограничений.
Такую функцию я тоже придумал, но пока не смог записать ее аналитически.

Здравствуйте, Vintik_69, Вы писали:

V_>Здравствуйте, RomikT, Вы писали:

RT>>Наверняка не самое короткое решение, но вроде работать будет.

V_>Не работает для 2147483647

По моему, несложно доказать что среди чисел от -2147483648 до 2147483647 невозможно давать правильный результат для всех чисел.
Как минимум, два числа окажутся неохваченными. Одно — просто потому, что нет числа +2147483648. А второе — ну так мир устроен

Здравствуйте, RomikT, Вы писали:

RT>Как минимум, два числа окажутся неохваченными. Одно — просто потому, что нет числа +2147483648. А второе — ну так мир устроен

Ну насчет второго — не понятно. У меня вроде для всех, кроме одного, работает.

Здравствуйте, Vintik_69, Вы писали:

V_>

V_>int f(int x)
V_>{
V_>    const unsigned int MAX = (1 << 31);
    
V_>    int order = x >= 0 ? x : -x + MAX;
V_>    order = (order + MAX/2);
V_>    if (order < MAX) return order;
V_>    else return -(order - MAX);
V_>}
V_>

А это решение не работает для 1073741824...

Я же говорю — не получится всех чисел

RT>А это решение не работает для 1073741824...

RT>Я же говорю — не получится всех чисел

Ну давайте в пятый раз это скажем!

Здравствуйте, RomikT, Вы писали:

RT>А это решение не работает для 1073741824...

RT>Я же говорю — не получится всех чисел

Хмм, правда

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

D>от avva

Задача очевидно не имеет решения.

Здравствуйте, Аноним, Вы писали:

А>Задача очевидно не имеет решения.

Для пуристов: снимаю ограничение на 32 бита. Допустимы произвольные целые — BigInteger.

D>Для пуристов: снимаю ограничение на 32 бита. Допустимы произвольные целые — BigInteger.

Давайте тогда уж BigFloat — произвольные дробные с бесконечной точностью. Решение, которое приводил deniok, должно работать и для них. Только на even надо проверять не x, а round(abs(x)).

Здравствуйте, Roman Odaisky, Вы писали:

П>>Найти функцию f, для которой f(f(x)) — -x
П>>x — любое вещественное число без ограничений.

RO>Делов-то...

RO>f(f(x)) = -x
RO>f² = -1
RO>f = i
RO>f(x) = ix

А какое вещественное число обозначено таинственной буквой i?

Всееее, мозги заплелись! Не заметил, что deniok — это вы и есть :D

Здравствуйте, RomikT, Вы писали:
RT>А какое вещественное число обозначено таинственной буквой i?

С комплексными тоже прикольно. Но для вещественных тоже строится элементарно. Я уже просек фишку. Нам надо разбить все положительные вещественные числа на непересекающиеся пары. Это можно сделать сотнями способов.

После этого строим функцию:

f(0) = 0

Для любой пары (x1, x2)

f(x1) = x2
f(x2) = -x1
f(-x1) = -x2
f(-x2) = x1

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, Аноним, Вы писали:

А>>Задача очевидно не имеет решения.

D>Для пуристов: снимаю ограничение на 32 бита. Допустимы произвольные целые — BigInteger.

Ну тогда решение простое: мы имеем 4 перестановки(тк уравнение 4 порядка), так что рассмотрим кольцо -2 -1 0 1 2.
0 преобразуется сам на себя, а из остальных чисел выбираем любой из 2 вариантов, например -2 -> 1, -1 -> -2, 1 -> 2, 2 -> -1.
Так что решение существует для любого множества кратного 4 + тривиальные числа, например 0.

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

D>от avva

int f(int x) {
    if (CDROM_opened()) { CDROM_close(); while(CDROM_opened()); return -x; }
    else { CDROM_open(); while(CDROM_closed()); return x; }
}

Здравствуйте, RomikT, Вы писали:

RT>Здравствуйте, Vintik_69, Вы писали:

V_>>Здравствуйте, RomikT, Вы писали:

RT>>>Наверняка не самое короткое решение, но вроде работать будет.

V_>>Не работает для 2147483647

RT>По моему, несложно доказать что среди чисел от -2147483648 до 2147483647 невозможно давать правильный результат для всех чисел.
RT>Как минимум, два числа окажутся неохваченными. Одно — просто потому, что нет числа +2147483648. А второе — ну так мир устроен

Как это для двух?

Здравствуйте, RomikT, Вы писали:

RT>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

RT>Наверняка не самое короткое решение, но вроде работать будет.
RT>

RT>if (x==0) {
RT>  return 0;
RT>}
RT>if (x>0) {
RT>  if (x & 1 == 1) {
RT>    return x+1;
RT>  } else {
RT>    return -x+1;
RT>  }
RT>} else {
RT>  if (x & 1 == 1) {
RT>    return x-1;
RT>  } else {
RT>    return -x-1;
RT>  }
RT>}
RT>

Идея понятная. В случае переполнения для таких чисел как 0x7fffffff результат неверный: 0x7fffffff вместо 0x80000001.

Здравствуйте, Vintik_69, Вы писали:

V_>Так это невозможно. Отрицательных чисел больше, чем положительных.

А где-то в условии упоминается дополнительный код?

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

D>от avva

Ну, например:

f(x) = x при x < 0  
f(x) = -x при x >= 0

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

R>Ну, например:
R>

R>f(x) = x при x < 0  
R>f(x) = -x при x >= 0
R>

На C/С++:

int f(int x)
{
  return x < 0 ? x : -x;
}

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

R>Ну, например:
R>

R>f(x) = x при x < 0  
R>f(x) = -x при x >= 0
R>

Да, написал ерунду

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Didro, Вы писали:

D>f(-1)= -1
D>f(f(-1))=f(-1)=-1.
D>лажа, однако.

Пока писал, Курилка уже ответил, извиняюся.

Здравствуйте, rg45, Вы писали:

R>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

R>Ну, например:
R>

R>f(x) = x при x < 0  
R>f(x) = -x при x >= 0
R>

int f(int x)
{
  return (x&1 ? -(x^1) : x^1) - 1;
}

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Что то я не в форме сегодня

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Панда, Вы писали:

П>На языках с динамической типизацией все просто

П>

П><?php
П>function f($x)
П>{
П>  if (is_array($x)) return $x[0];
П>  return array(-$x);
П>}
П>?>
П>

аналогичная идея для C++

struct othertype
{
    int val;
    int atr;
};

othertype f(int i)
{
    othertype r;
    r.val = i;
    return r;
}

int f(othertype o)
{
    return -o.val;
}

Здравствуйте, Панда, Вы писали:

П>Кстати, можно сформулировать аналогичную задачу по математике, а не по программированию.
П>Найти функцию f, для которой f(f(x)) — -x
П>x — любое вещественное число без ограничений.
П>Такую функцию я тоже придумал, но пока не смог записать ее аналитически.

А для комплексных?

Здравствуйте, Аноним, Вы писали:

А>А для комплексных?

f(x)=i*x
f(f(x))=-x

Легко и программно реализуется(класс КЧ и всё такое)...

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

D>от avva

int f(int x)
{
static bool bEvenCall = false;
if( bEvenCall )
x = ~x;
else
x++;
bEvenCall = !bEvenCall;
return x;
}

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

А>int f(int x)
А>{
А> static bool bEvenCall = false;
А> if( bEvenCall )
А> x = ~x;
А> else
А> x++;
А> bEvenCall = !bEvenCall;
А> return x;
А>}

Я эту идею уже утрировал в виде выдвигающегося/задвигающегося CD-ROM-а. В обоих случаях используется статическая переменная (в случае с CD-ROM -- hard static bool). Идея в том, что если между двумя последовательными вызовами что-то произойдет, ну, например, вы вызовите эту же функцию для другого аргумента из другого потока (или вручную задвините CD-ROM

), то все полетит.

Здравствуйте, deniok, Вы писали:

D>

D>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>целые числа. x — целочисленный аргумент (например, 32-битный).

D>от avva

Лехко:

   typedef TArgType int;

   TArgType f( TArgType x )
    {
        if( x )
        {
            if( x & 1 )
            {
                if( x > 0 ) x++;
                else        x--;
            }
            else
            {
                x = -x;
                if( x > 0 ) x--;
                else        x++;
            }
        }

        return x;
    }

Всего наилучшего

Здравствуйте, yachmen, Вы писали:

Y>Здравствуйте, deniok, Вы писали:

D>>

D>>Задача: написать функцию f(x), так, что f(f(x)) = -x. Разрешено использовать только
D>>целые числа. x — целочисленный аргумент (например, 32-битный).

D>>от avva

Y>Лехко:

Y>

Y>   typedef TArgType int;

Y>   TArgType f( TArgType x )
Y>    {
Y>        if( x )
Y>        {
Y>            if( x & 1 )
Y>            {
Y>                if( x > 0 ) x++;
Y>                else        x--;
Y>            }
Y>            else
Y>            {
Y>                x = -x;
Y>                if( x > 0 ) x--;
Y>                else        x++;
Y>            }
Y>        }

Y>        return x;
Y>    }
Y>

Y>Всего наилучшего

f(f(0x80000001)) = 0x80000001

Здравствуйте, vadimcher, Вы писали:

V>f(f(0x80000001)) = 0x80000001

Прикольно — ведь я и проверял-то только -1, 0, 1, 0x7fffffff, 0x80000000 и 0x80000001 — но глаз замылился и не увидел это в логе

Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

Всего наилучшего

Здравствуйте, Ячменников Александр, Вы писали:

ЯА>Здравствуйте, vadimcher, Вы писали:

V>>f(f(0x80000001)) = 0x80000001

ЯА>Прикольно — ведь я и проверял-то только -1, 0, 1, 0x7fffffff, 0x80000000 и 0x80000001 — но глаз замылился и не увидел это в логе

ЯА>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

ЯА>Всего наилучшего

Я бы даже сказал, можно для всех чисел, кроме одного.

Здравствуйте, vadimcher, Вы писали:

V>Здравствуйте, Ячменников Александр, Вы писали:

ЯА>>Здравствуйте, vadimcher, Вы писали:

V>>>f(f(0x80000001)) = 0x80000001

ЯА>>Прикольно — ведь я и проверял-то только -1, 0, 1, 0x7fffffff, 0x80000000 и 0x80000001 — но глаз замылился и не увидел это в логе

ЯА>>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

ЯА>>Всего наилучшего

V>Я бы даже сказал, можно для всех чисел, кроме одного.

Что, кстати, иллюстрирует необходимость покрытия кода тотальными тестами (или использования формальной верификации программы)

Здравствуйте, Ячменников Александр, Вы писали:

ЯА>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

Ну это скорее следствие того, что для какого-то числа х нельзя вычислить -х...

Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Ячменников Александр, Вы писали:

ЯА>>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

E>Ну это скорее следствие того, что для какого-то числа х нельзя вычислить -х...

Ну, в общем, да... Хотя, -x формально можно вычислить для любого числа: -0=0, -0x80000000=0x80000000. Просто для одного из них это будет математически неверное -x.

Но проблема здесь не в этом. Если a->b, то b->-a, и -a->-b->a. Т.е. если a!=-a, то требуются четверки чисел, а все такие числа, для которых a!=-a на четверки как раз и не делятся. Т.е. если бы таких чисел было число, кратное 4, то задача решалась бы.

Здравствуйте, deniok, Вы писали:

D>Здравствуйте, vadimcher, Вы писали:

V>>Здравствуйте, Ячменников Александр, Вы писали:

ЯА>>>Здравствуйте, vadimcher, Вы писали:

V>>>>f(f(0x80000001)) = 0x80000001

ЯА>>>Прикольно — ведь я и проверял-то только -1, 0, 1, 0x7fffffff, 0x80000000 и 0x80000001 — но глаз замылился и не увидел это в логе

ЯА>>>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

ЯА>>>Всего наилучшего

V>>Я бы даже сказал, можно для всех чисел, кроме одного.

D>Что, кстати, иллюстрирует необходимость покрытия кода тотальными тестами (или использования формальной верификации программы)

Да уж... Я сразу вспоминаю недавний глюк Excel 2007, который "работал" только для 12 из 9.2*10^18 64-битных чисел с плавающей точкой.

Здравствуйте, vadimcher, Вы писали:

V>Ну, в общем, да... Хотя, -x формально можно вычислить для любого числа: -0=0, -0x80000000=0x80000000. Просто для одного из них это будет математически неверное -x.

Зависит от. Если используется прямой код, то -0x80000000=0x00000000, т.е -(-0)=0.
В обратном коде -0x80000000=0x7FFFFFFFF или -(-2147385345)=2147385345.

Здравствуйте, Ячменников Александр, Вы писали:

ЯА>Прикольно — ведь я и проверял-то только -1, 0, 1, 0x7fffffff, 0x80000000 и 0x80000001 — но глаз замылился и не увидел это в логе

ЯА>Т.о. вывод такой — можно сделать эту функцию для всех чисел кроме двух, необязательно 0x80000000 и 0x80000001.

Ну, тут уже показывали, что для 32-битных целых (да и вообще для любых целых в двоичной сетке) это невозможно.
Дело в том, что все числа кроме 0 и INT_MIN (в дополнительном коде INT_MIN < -INT_MAX) группируются по 4:
{ x, y=f(x), -x=f(y), -y=f(-x) }, дальше будет x=f(-y)
Остаются 0 и INT_MIN, так что либо f(0)=0, f(INT_MIN)=INT_MIN, либо f(0)=INT_MIN, f(INT_MIN)=0.

Итого, мощность множества целых чисел равна 4n+2. А на самом деле — 2^p.

А в прямом коде, где -0 и 0 — это разные числа, и они не выпадают из общего правила f(f(x))=-x, f(f(0))=-0, — решение есть.
Произвольным образом разбиваем множество Z+ неотрицательных чисел на два равномощных подмножества A+, B+ и строим f как колечки: A+ -> B+ -> A- -> B-.
В качестве способа разбиения проще всего предложить чётность.

То же касается неограниченных целых чисел, и для вещественных. Там есть единственное особое число 0, и для него f(0)=0. А все остальные так же группируются.
У вещественных можно разбивать по признаку frac(x) < / >= 0.5, например.

... << RSDN@Home 1.2.0 alpha rev. 655>>

	От:	RomikT
	Дата:	17.01.08 20:14
	Оценка:	10 (3)

	От:	deniok
	Дата:	17.01.08 19:50
	Оценка:	10 (2)

	От:	deniok
	Дата:	17.01.08 20:40
	Оценка:	15 (1)

	От:	Roman Odaisky
	Дата:	17.01.08 21:25
	Оценка:	2 (1)

От:	Курилка	http://kirya.narod.ru/
Дата:	18.01.08 07:20
Оценка:	1 (1)

От:	Didro	home~pages
Дата:	18.01.08 07:24
Оценка:	1 (1)

	От:	Ячменников Александр
	Дата:	02.02.08 21:37
	Оценка: