Для этой задачи вам нужно реализовать две функции, 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).Применяются обычные правила целочисленного переполнения: ваше решение должно быть в состоянии работать с произвольно большими целыми числами в гипотетической (или, возможно, реальной) версии вашего языка, в которой все целые числа не ограничены по умолчанию, но если ваша программа на практике дает сбой из-за реализации не поддерживает такие большие целые числа, что не делает решение недействительным.
Вы можете использовать любой язык программирования , но учтите, что эти лазейки по умолчанию запрещены.
Это код-гольф , поэтому ваш результат представляет собой сумму количества байтов обеих функций и кратчайшего действительного ответа.
Ответы:
Python, 68 символов
f отображает отрицательные числа в нечетные числа и положительные числа в четные числа, а четные числа в положительные числа и нечетные числа в отрицательные числа, причем выходная величина строго возрастает вместе с входной величиной.
g делает то же самое, за исключением того, что отображает отрицательные числа в четные числа и положительные числа в нечетные числа.
f ∘ g отображает отрицательное → четное → положительное и положительное → нечетное → отрицательное.
g ∘ f отображает отрицательный → нечетный → отрицательный и положительный → четный → положительный.
Поэтому f и g обладают желаемыми свойствами.
источник
f
иg
могут быть безымянными функциями, поэтому вы можете отбросить четыре байта.(1-x%2*2)
как переменную, чтобы сохранить несколько байтов.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();
можно поиграть. Вы можете заменить его;
переводом строки для удобства чтения.Python , 40 байт
Попробуйте онлайн! Некоторые выходные данные являются числами
(-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 байт:
Попробуйте онлайн!
источник
(^)
это целочисленное возведение в степень.g
себя, вы можете сохранить два байта, сделав его безымянным.CJam (17 байт)
Функция f (названная
F
потому, что CJam допускает только имена в верхнем регистре):Функция g (анонимная):
Онлайн демо
Это экономит байт, полагаясь на детали реализации CJam, что, возможно, является ошибкой: при выполнении базовых преобразований используется абсолютное значение.
2b,
следовательно, дает число битов в абсолютном значении своего аргумента, поэтому f отрицает именно те числа, абсолютное значение которых имеет нечетное число битов. g применяет f и затем удваивает (изменяя четность количества бит).Таким образом, применение f, а затем g оставляет знак без изменений и удваивается, отображая
x
в2x
. Применение g, а затем f меняет знак ровно один раз и удваивается, отображаяx
в-2x
.источник
Pyth, 34 байта
Это просто прямой перевод моего ответа на Python.
источник