f (g (x)) уменьшается, а g (f (x)) увеличивается

42

Для этой задачи вам нужно реализовать две функции, f и g , на целых числах, так что f ∘ g - строго убывающая функция, а g ∘ f - строго возрастающая функция. Другими словами, если вы берете любые два целых числа a <b , то f (g (a))> f (g (b)) и g (f (a)) <g (f (b)) . Не существует никаких ограничений для f и g в отдельности, за исключением того, что каждый из них должен отображать одно целое число в другое целое число.

Пожалуйста, включите краткое описание f и g и аргумент, почему у них есть обязательное свойство.

Предоставлено: Эта задача была вызвана проблемой в Румынском конкурсе магистров математики 2011 года (который запрашивает то же самое, но не с целыми числами, а с действительными числами). Если вы действительно хотите спойлеры, теперь вы знаете, что искать.

правила

  • Слово «функция» в этой задаче следует понимать в математическом смысле отображения одного целого числа на другое: вы можете написать две программы или две функции и использовать любой из стандартных методов получения ввода и вывода, как обычно. Вы можете использовать строковые представления целых чисел вместо фактических целочисленных переменных, но типы ввода и вывода должны быть идентичными, чтобы можно было составлять функции без ручного преобразования типов между ними. Помните, что концептуально, f и g все еще должны быть функциями на ℤ, поэтому вы не можете обмануть, используя два разных строковых представления одного и того же числа или что-то в этом роде.

  • Помните, что функции могут быть безымянными , если их имя не требуется само по себе или другой функции, которую вы определяете. Если вы назовете одну или обе функции, вы можете предположить, что они существуют в одной и той же программе, так что они могут ссылаться друг на друга в своей реализации (например, def f(x): return -g(x)в Python).

  • Применяются обычные правила целочисленного переполнения: ваше решение должно быть в состоянии работать с произвольно большими целыми числами в гипотетической (или, возможно, реальной) версии вашего языка, в которой все целые числа не ограничены по умолчанию, но если ваша программа на практике дает сбой из-за реализации не поддерживает такие большие целые числа, что не делает решение недействительным.

  • Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.

  • Это , поэтому ваш результат представляет собой сумму количества байтов обеих функций и кратчайшего действительного ответа.

Мартин Эндер
источник
Могут ли функции вернуть строку?
Мэтью Ро
@SIGSEGV Я бы сказал, да, но только если они также принимают строку в качестве входных данных, поэтому они могут быть составлены без необходимости вставлять какие-либо преобразования типов.
Мартин Эндер,
О, darnit, я попытался преобразовать в строку, чтобы другая функция не смогла редактировать результаты дальше.
Мэтью Ро
1
@ Фатализировать Правильно. Каждый должен быть функцией типа ℤ → ℤ.
Мартин Эндер,
1
@ Биджан как положительный, так и отрицательный.
Мартин Эндер

Ответы:

18

Python, 68 символов

f=lambda x:(1-x%2*2)*(2*x*x+(x<0))
g=lambda x:(1-x%2*2)*(2*x*x+(x>0))

f отображает отрицательные числа в нечетные числа и положительные числа в четные числа, а четные числа в положительные числа и нечетные числа в отрицательные числа, причем выходная величина строго возрастает вместе с входной величиной.

g делает то же самое, за исключением того, что отображает отрицательные числа в четные числа и положительные числа в нечетные числа.

f ∘ g отображает отрицательное → четное → положительное и положительное → нечетное → отрицательное.
g ∘ f отображает отрицательный → нечетный → отрицательный и положительный → четный → положительный.

Поэтому f и g обладают желаемыми свойствами.

user1502040
источник
2
fи gмогут быть безымянными функциями, поэтому вы можете отбросить четыре байта.
Мартин Эндер
Вы можете определить (1-x%2*2)как переменную, чтобы сохранить несколько байтов.
OldBunny2800
Вот полный код, с которым import numpy as np; import matplotlib.pyplot as plt; xrange=np.arange(-3,4); f=lambda x:(1-x%2*2)*(2*x*x+(x<0)); g=lambda x:(1-x%2*2)*(2*x*x+(x>0)); plt.plot(xrange, map(f, xrange), 'ro'); plt.plot(xrange, map(g, xrange), 'go'); plt.plot(xrange, map(f, map(g, xrange)), 'b--'); plt.plot(xrange, map(g, map(f, xrange)), 'y--'); plt.show(); можно поиграть. Вы можете заменить его ;переводом строки для удобства чтения.
Стефан Гурихон
16

Python , 40 байт

f=lambda x:x*(-1)**x
g=lambda x:3*f(x)+1

Попробуйте онлайн! Некоторые выходные данные являются числами (-1)**(-3)с плавающей точкой, которые равны целым числам, потому что, например, дает число с плавающей точкой.

Основано на идеях Питера Тейлора . Функция fотменяет нечетные числа и оставляет четные без изменений. Функция gделает то же самое, затем применяет монотонную карту переключения четности x -> 3*x + 1.

С тех пор f(f(x)) = xмы g(f(x)) = 3*f(f(x))+1 = 3*x+1увеличиваем.

Для f(g(x)) = f(3*f(x)+1), идея заключается в том , что именно один из внутреннего и внешнего fпереворачивает знак, что делает его уменьшения.

  • Ибо четно x, f(x) = xа f(3*x+1) = -3*x-1потому что 3*x+1странно.
  • Ибо нечетно x, f(x) = -xа f(-3*x+1) = -3*x+1потому -3*x+1чётно.

Теперь нам нужно только, чтобы чётные и нечетные входы чередовались убывающим образом, что верно, потому что -3*x±1уменьшается независимо от того, как выбраны знаки. Вот почему 3*это необходимо.

Порт Haskell составляет 25 байт:

f x=x*(-1)**x
g x=1+3*f x

Попробуйте онлайн!

XNOR
источник
В Хаскеле (^)это целочисленное возведение в степень.
user1502040
1
@ user1502040 Он не может обрабатывать отрицательные показатели.
xnor
1
Поскольку вы не называете gсебя, вы можете сохранить два байта, сделав его безымянным.
Мартин Эндер
14

CJam (17 байт)

Функция f (названная Fпотому, что CJam допускает только имена в верхнем регистре):

{W1$2b,#*}:F

Функция g (анонимная):

{F2*}

Онлайн демо

Это экономит байт, полагаясь на детали реализации CJam, что, возможно, является ошибкой: при выполнении базовых преобразований используется абсолютное значение. 2b,следовательно, дает число битов в абсолютном значении своего аргумента, поэтому f отрицает именно те числа, абсолютное значение которых имеет нечетное число битов. g применяет f и затем удваивает (изменяя четность количества бит).

Таким образом, применение f, а затем g оставляет знак без изменений и удваивается, отображая xв 2x. Применение g, а затем f меняет знак ровно один раз и удваивается, отображая xв -2x.

Питер Тейлор
источник
Хорошо, это именно эталонное решение, представленное в конкурсе. (Полагаю, вы придумали это самостоятельно?)
Мартин Эндер,
@MartinEnder, я видел эту проблему где-то раньше. Возможно, по математике.
Питер Тейлор
2

Pyth, 34 байта

Это просто прямой перевод моего ответа на Python.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
user1502040
источник