вторник, 2 ноября 2010 г.

Try to f(f(n)) == -n

Увидел недавно интересный вопрос.
Написать такую функцию f, что: f(f(n)) == -n

У кого какие идеи?

Вот самый простой вариант на мой взгляд (правда это не совсем функция):
#define f(n) 0-n
Ну а вот посложнее (правда тут получается 2 функции с одним именем):

template<typename T>
struct param
{
   T n;
   param(T t) : n(t) {}
};

template<typename T>
param<T> f(T n)
{
   T a = (1&(n^(n>>1)));
   n ^= (a ? 0xAA : 0x55);
   return param<T>(n);
}

template<typename T>
T f(param<T> n)
{
   return f(n.n).n + 1;
}

(ссылка - http://codepad.org/TK0GhhAe)

Этот код пока работает только для char.
Так было намного быстрее прогонять полный тест))
Нетрудно модифицировать его для остальных типов.

8 комментариев:

Dmytro Prylipko комментирует...

А решение существует?
А то я сильно сомневаюсь

iB0BAH комментирует...

// Обратную функцию к f(x) я буду обозначать как f'(x)

Пусть f( f(x) ) = -x
<=> f'(-x) = f(x)
<=> f'( x ) = f(-x) // *1
<=> f'( f(x) ) = f( -f(x) ) = x // по опр обратной ф-ции и *1
<=> f'( x ) = -f(x) => учитывая *1 f(x) = -f(x) = f'(x)
=> f'( f(x) ) = -x => x = -x Оппа! Это верно только при x = 0

jokz@nxt.ru комментирует...

хм. реализация на php:

function f($n) {
if(substr($n,0,6)=='unique') {
return -((int)(substr($n,6)));
} else {
return 'unique'.$n;
}
}

agarus комментирует...

f(n)=in; f(f(n))=f(in)=ni^2=-n

Сергей комментирует...

int f(int n)
{
return -1;
}

Анонимный комментирует...

Хм. Подходит такая функция (n -- произвольное натуральное число):
f(2n-1) = 2n;
f(2n) = -2n + 1;
f(-2n+1) = -2n;
f(-2n) = 2n - 1;
f(0) = 0.

В рассуждении iB0BAH, кажется, ошибка в 3 знаке равносильности.

[k06a] комментирует...

Анонимный, отличный вариант решения! Вроде все пункты учтены, я даже схемку набросал http://t.co/UOQa3WSx

Serhiy Kalinets комментирует...

return n < 0 ? n : -n;