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

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

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

Делов-то...

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

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>

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

Здравствуйте, 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>>

Здравствуйте, 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.
лажа, однако.

Здравствуйте, 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;
}

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

П>Подумал. В целом — задача неразрешимая. Потому что есть такое 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
упс.

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

	От:	Панда
	Дата:	17.01.08 21:28
	Оценка:

	От:	RomikT
	Дата:	17.01.08 21:29
	Оценка:

	От:	Панда
	Дата:	17.01.08 21:32
	Оценка:

	От:	Панда
	Дата:	17.01.08 21:38
	Оценка:

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

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