Эта проблема была вдохновлена программистским блогом, который я часто посещаю. Пожалуйста, смотрите оригинальный пост здесь: программирование головоломки
Вызов
Определите функцию так f:Q->Q
, чтобы f(f(n)) = -n
для всех ненулевых целых чисел n
и где Q
было множество рациональных чисел.
Детали
На любом языке, который вы предпочитаете, определите одну функцию или программу, f
которая принимает в качестве параметра один номер n
и возвращает или выводит один номер f(n)
.
Ввод может быть осуществлен с помощью любого наиболее естественного для вашего языка механизма: аргумент функции, чтение из STDIN, аргумент командной строки, позиция стека, голосовой ввод, знаки банды и т. Д.
Выходные данные должны быть возвращаемым значением из функции / программы или распечатаны в STDOUT.
Я хотел бы ограничить ответы функциями, которые не используют состояние программы или глобальную память / данные, которые видны снаружи функции f
. Например, сохранение счетчика вне f
этого подсчета подсчитывает, сколько раз f
было вызвано, и просто делать отрицание на основе этого подсчета не очень сложно или интересно для всех. Принятие решений f
должно опираться только на данные в f
лексической области.
Однако это ограничение, вероятно, не подходит для некоторых языков, ориентированных на стек, или для других типов языков, которые не различают эти типы данных или области. Пожалуйста, используйте свое лучшее суждение, чтобы соответствовать духу этой задачи.
счет
Применяются общепринятые правила игры в гольф - ваш счет - это количество байтов в исходном коде.
Минимальный ответ требует, чтобы домен и кодомен f
были подмножеством рациональных чисел Q
. Если вы ограничите свой домен и кодомен f
до целых чисел Z
, то ваш счет - это верхний предел 90% количества байтов в вашем исходном коде.
Баадур
В случае ничьей будет использовано следующее:
- Наименьшее количество печатаемых непробельных символов в вашем исходном коде
- Самая ранняя дата и время подачи ответа
редактировать
Вы не обязаны поддерживать номера произвольного размера. Пожалуйста, интерпретируйте наборы Z
и Q
типы данных на выбранном вами языке (обычно целочисленные и с плавающей запятой соответственно).
Если ваше решение полностью основано на базовой структуре или битовой структуре типа данных, пожалуйста, опишите ее ограничения и способы ее использования.
f:Q->Q
значит?f
что это функция, отображающая членовQ
(рациональных чисел) в другие члены (возможно, одинаковые) изQ
. см. en.wikipedia.org/wiki/Function_(matmatics)#NotationОтветы:
J, 9 баллов (10 символов)
На основании ответа stackoverflow :
Первая идея (13 символов):
источник
Питон:
61 34 30 2927 очковf: Q -> Q
в математике:
в Python:
проверено с
логика за этим:
Когда вы возьмете целое число
n
и вставите его,f
вы получитеx+0.5
. Это не является целым числом больше, так что следующая заявка будет0.5-(x+0.5)
что-x
.кредиты
Благодаря
Заметки
Сначала я думал, что это будет хорошо
но это f: N-> C, и это не разрешено: - /
источник
f=lambda x:x%1>0and(-x+x%1)or x+.1
длиной всего 34 символа.f=lambda x:[x+.1,x%1-x](x%1>0)
только 30 летf=lambda x:[x+.5,.5-x][x%1>0]
. Обратите внимание на использование .5 вместо .1, чтобы обойти проблемы точностиf:Q->Q
означает только то, что f отображает рациональное число в рациональные числа. Какое мое определение f делает.C, 41 балл (41 или 45 символов)
Работает с использованием 32- и 64-разрядных.
f : Z -> Z
(кромеINT_MAX
):Если нам не нужно включать,
0
мы можем сбрить некоторые символы (41 символ):f : Z -> Z
(кроме0
&INT_MAX
):Эта функция работает путем деления всех целых чисел на 4 группы в зависимости от их знака и четности.
Итак, у нас есть 4 разные комбинации:
Поскольку нам нужно поменять знак числа, а не четность после двух проходов, мы получаем две разные возможные последовательности:
В этом примере я выбрал первый.
Сначала нам нужно отобразить все четные положительные целые числа на нечетные отрицательные целые числа. Мы делаем это, изменяя знак и увеличивая число (вместо этого вы можете уменьшить число):
Затем нам нужно отобразить все нечетные отрицательные целые числа на четные отрицательные целые числа. Нам нужно убедиться, что
f2(f1(n)) = -n
:Используя те же методы, мы находим
f3
иf4
:Чтобы объединить эти функции в одну функцию, мы видим, что каждый раз, когда
n
мы даже переключаем знак,n
и каждый раз, когдаn
мы положительны, мы увеличиваем на единицу, а в противном случае мы уменьшаем на единицу:Таким образом, это может быть переписано как:
где
odd(n)
возвращает1
нечетные числа и-1
четные числа.Всего 4 решения:
INT_MIN
всегда может рассматриваться как крайний случай во всех 4 функциях как-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.источник
0
и 3 других номеров.Z
бонус только если вы покрываете 0, по крайней мере.Вот мой путь.
Живой пример :
Типы ввода могут быть произвольно адаптированы к вашим потребностям. Эта версия работает для целочисленных литералов, которые меньше по величине, чем 2 ^ 32-1.
источник
f:Q->Q
, нетf:Z->Z
.f:Z->Z
, извините за запутанную формулировкуreturn -i
JavaScript, 18
Использование новой жирной стрелки (Firefox 22).
Другая версия (18):
Предыдущая версия (20):
Пример:
источник
Mathematica 18
Вот
⌊...⌋
функция пола. Он использует только рациональные числа (не списки, комплексные числа и т. Д.)источник
ассемблер x86 (FASM). Аргумент и результат находятся в регистре eax.
Это работает правильно для -2 ^ 30 <N <+ 2 ^ 30-1
16 байт исполняемого кода.
источник
Common Lisp: 35 байт
Схема (и ракетка): 36 байт
Разгулялся с комментариями и объяснениями:
Для любого числа
x
в[1,->]
числоif
превратится в дробь,1/2
которая является реальным точным числом на обоих языках.Разделительная часть станет
(/ 1/2 x)
такой,1/(x*2)
какой станет дробь, которая всегда находится ниже1
. Для1
него будет1/2
, ибо2
это1/4
и т.д.Для любого числа ниже 1 , то
if
получится в доле-1/2
, что делает функцию делать(/ -1/2 x)
что ,-1/(2*x)
но так как можно ожидать , что значение будет результат предыдущего запуска мы можем подставить е 1 / (х * 2) , что делает двойное применение-1/((1/(x*2))*2) = -x
Например, так как
1
превращается во1/2
второе приложение(/ -1/2 1/2) ==> -1
источник
С 60 (⌈66 * .9⌉)
Вот безоговорочная версия:
Этот метод работает с использованием только целых чисел, поэтому он получает бонус в 90%. Первоначально я писал его на Java, но понял, что эта программа, в частности, может извлечь выгоду из логических операторов в стиле Си.
Поскольку нет целого числа, соответствующего
-INT_MIN
, вместо этогоf(f(INT_MIN))
возвращаетсяINT_MIN
.Основное отображение алгебраически довольно просто. Выполнение оператора
x=f(x)
заменяет x на:x+1
, еслиx
положительный и нечетный-x+1
, еслиx
положительно и дажеx-1
, еслиx
отрицательный и нечетный-x-1
, еслиx
отрицательно и дажеРезультат каждого случая будет попадать в следующий случай при следующем применении функции к x.
Как видите, составление кейса с последующим кейсом дает
-x
.Код является результатом некоторого умного упрощения функции, чтобы использовать в своих интересах битовую структуру целых чисел комплимента двух.
источник
> <> , 21 + 3 = 24 байта, 22 балла
Используйте официальный интерпретатор Python и используйте параметр
-v
командной строки для ввода ввода, стоимостью 3 байта.У меня есть ощущение, что это может быть лучше - я буду продолжать смотреть на это и пытаться играть в гольф.
Учитывая ввод
n
, программа выводитгде
(n>0)
и(n<0)
есть логические значения. Это эквивалентно желатинскому ответу Pythonно
><>
не имеет встроенного оператора возведения в степень, поэтому мы используем(1 - 2*(n%2))
вместо(-1)**n
.Далее следует математическая теория - читайте, если (и только если) вы заинтересованы:
Для любой функции ,
f: Z -> Z
такие , чтоf(f(n)) = -n
для всехn
инZ
, мы видим сразу , чтоf(f(f(f(n)))) = n
, или, другими словами,f^4
это функция тождества. В частности,f
обратим, а его обратная функция естьf^3
. Таким образом ,f
перестановкаZ
, и так какf^4 = Id
, то отсюда следует , что каждая орбита (или цикл) изf
имеет размер либо1
,2
, или4
.Далее мы видим это
f(0) = 0
. Доказательство:f(0) = f(-0) = f(f(f(0))) = -f(0)
такf(0) = 0
, по желанию. И наоборот, предположим, чтоx
в цикле длины1
или2
, такf(f(x)) = x
. Тогда-x = x
такx = 0
.Таким образом
f
, полностью состоит из 4 циклов, за исключением фиксированной точки (1 цикл) в0
.Далее, каждый 4-цикл должен иметь форму
(x, y, -x, -y)
, и, вращая цикл, мы можем предположить, чтоx
иy
оба положительны. Наоборот, каждое такое произведение 4-циклов, разделяющих ненулевые целые числа, определяет выборf
.Таким образом, каждый выбор
f
однозначно соответствует ориентированному графу, вершинами которого являются положительные целые числа, так что каждая вершина инцидентна ровно одной стрелке, входящей или выходящей. Точнее, в базовом неориентированном графе каждая вершина имеет степень точно1
. (Каждый 4-цикл(x y -x -y)
сx
иy
положительными соответствует стрелкеx --> y
.)Функция в этом ответе (и несколько других ответов здесь) соответствует графике , где
1 --> 2
,3 --> 4
и в целом2k-1 --> 2k
.Такие графики находятся во взаимно однозначном с бесконечными последовательностями упорядоченных пар
(a_n, p_n)
, где каждыйa_n
представляет собой положительное целое число , и каждыйp_n
является либо0
или1
: дана последовательность(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, мы первая пара1
с1 + a_1
, а затем формируют либо стрелку1 --> 1 + a_1
или стрелку в1 + a_1 --> 1
зависимости от того ,p_1
является0
или1
. По сути, стрелка является либо<
знаком, либо>
знаком, в зависимости от соотношенияp_1
.Далее, возьмем наименьшее непарный целое положительное число
k
, и подсчитать отk
, ровноa_2
шагов, пропускаем любое число , которое уже в паре с чем - то. Сопряжениеk
с результатом, и установите направление стрелки в зависимости от того,p_2
как указано выше. Затем повторите с(a_3, p_3)
и т. Д.Каждая стрелка в конечном итоге будет определена таким образом, поэтому процесс четко определен. Функция в этом ответе соответствует последовательности
(1,0), (1,0), (1,0), ...
, так как на шагеn
наименьшее непарное целое число равно целым2n-1
числам, а не целым, больше, чем2n-1
было спарено с чем-либо, поэтому мы получаем2n-1 --> 2n
для каждогоn
(стрелки ориентированы таким образом, потому что каждыйp_n
равен0
).Количество элементов этого множества
(N*2)^N = N^N
, которое по последнему абзацу этого ответа равно2^N
количеству вещественных чисел.источник
Чтобы исправить предыдущий ответ J (у меня недостаточно репутации, чтобы комментировать оригинал):
Он просто заменяет
_1&^
с1-~2*2|]
, что дает противоположный знак. Поэтому я изменил на-
a+
(который имеет значение только для ввода1
и_1
).Вот тесты:
Как видите, домен и диапазон имеют все действительные числа, но это работает только для целых чисел (включая 0).
Объяснение:
источник
GolfScript
ceiling(26*.9)=24
Golfscript обрабатывает только целые числа, поэтому примените
Z
бонус на общую сумму 24 балла:Особый случай 0 составляет 8 символов. Игнорируя 0, мы можем получить ответ из 17 пунктов:
Этот код выполняет следующие действия с целым числом
x
в верхней части стека:x
0, оставьте0
в стеке и больше не применяйте правила.x
чёт, отрицайx
.x
положительно, добавьте1
.x
отрицательно, вычтите1
.Это логически соединяет наборы из 4 чисел в цикле, где
f
обходы элементов цикла, а противоположные углы цикла являются отрицаниями друг друга. Каждое целое число является частью ровно 1 такого цикла, за исключением 0, которое имеет специальный регистр. Например, для{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Единственные релевантные тестовые случаи, о которых я мог подумать, были отрицательный нечетный, отрицательный четный, положительный нечетный, положительный четный
0
, а затем я добавил,-1
и,1
поскольку их близость к,0
возможно, вызвала проблемы:Я уверен, что настоящий GolfScript может быть несколько улучшен. Не похоже, что он должен занимать 26 символов! Хотелось бы услышать некоторые предложения.
источник
Ява, просто для удовольствия
Вот реализация, которая выполняет фактическую биекцию между ℤ и ℤ², которая является одновременно нечетной функцией (g (-x) == -g (x)). Он обрабатывает соответствующий элемент as² как комплексное число и умножает его на «i», а затем преобразует обратно в ℤ.
f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x
Функция работает в O (1).
PS С новым годом!
источник
Питон 3 - 38
Похоже на ответ @ лося, но
f(n) == n
,. Работает для всех целочисленных значений.источник
Perl, 33 (без пробелов)
Редактировать:
$=.".1"
сокращено до"$=.1"
(спасибо ardnew).Математика:
Ungolfed:
Примеры:
источник
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
является не состояние свободной, она использует состояние через переменную$_
. Из-за этогоf
больше не является функцией (в математическом смысле), поскольку возможны разные значения для одного и того же входного значения в зависимости от состояния (погода$_
естьx
или нет). Мой алгоритм не использует состояние, информация закодирована в выходном значении. Целые числа преобразуются в реальные числа путем добавления.1
. И действительные числа конвертируются обратно в целые числа с переключенным знаком.$=
?f
будет определеноQ->Q
) с этимx
символом. также$=.".1"
может быть сокращено до"$=.1"
$=
является то, что он принимает только целые числа. То же самое может быть достигнуто с помощью обычной переменной:$a=int$_[0]
. Но это стоит три дополнительных байта из-за функцииint
.Юлия, 26 лет
Не супер конкурентоспособный, но очень юлианский, так как полагается на многократную отправку. Он просто делает Rational, если это Int, или int со знаком минус, если это что-то еще. Кто-то может возразить, что это 2 функции, но Джулия считает, что это одна функция с двумя методами, и это эквивалентно определению одной функции со статическим if для типа
n
.источник
3==3//1
возвращается,true
ноf(3//1)==f(3)
возвращаетсяfalse
.Candy ,
2018 байтовИспользует трюк 3 -> 4 -> -3 -> -4 -> 3.
Чтобы вызвать его, используйте ключ -i на интерпретаторе
Пример двойного вызова:
Длинная форма:
источник
Дьялог АПЛ, 9 очков
Длина источника составляет 9 байт, и он претендует на бонус (что совсем не помогает). Он также использует формулу из верхнего SO ответа.
источник
Python: 32 байта (29 баллов)
f: Z -> Z
Используя метод Бена Райха.
источник
(n>0)-(n<0)
наcmp(n,0)
, чтобы сохранить несколько байтов. (Но не в Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )БРГ , 22
источник
Java, 113 байт
Подход довольно прост. В итоге получилось больше байтов, чем я ожидал, но, возможно, немного проиграл.
Он в основном создает 4 различных «области» x, используя тот факт, что Java успешно позволяет переменным оборачиваться. Мне пришлось сделать несколько хитрых преобразований для отрицательных чисел, и это главная причина, по которой это оказалось больше, чем предполагалось.
Работает для всех х, кроме -2147483648.
источник
Та же последовательность чисел (3, 4, -3, -4, 3 ...), что и в ответе сценария гольфа, но реализована в perl (42 символа после пробела)
Более разборчиво:
Или даже более разборчиво:
Выход:
источник
Сед, 25 байт.
Использование:
источник
Matlab, 26 символов
источник
С ++ -
6355,8Вот как выглядит код:
Он не работает с целыми числами, чей четвертый байт равен 0xB, поскольку он использует это значение для отслеживания проходов. В противном случае работает на любом члене Z, включая ноль.
источник
f
статической переменной. но тогда какой смыслsqrt
?sqrt
как оно все равно округляется при приведении типа. Я сделаю рефакторинг, чтобы он работал без статической переменной.55.8
, но ваш текущий код длиной 62 байта. Изменить: не берите в голову, я не прочитал вопрос правильно.Обновлен с помощью функции, поставляемой Synthetica (очевидно, тот, кто должен получить кредит на это сейчас)
Язык: Python
Количество символов: 41, включая пробелы
источник
f=lambda x:-float(x) if str(x)==x else`x`
немного короче: 41, включая пробелыf
возвращает строку; спецификация говорит, что она должна возвращать рациональное число.Пролог, 36 байт
Код:
Разъяснение:
Пример:
источник
Javascript ES6,
2726 байтисточник
Мышь-2002 ,
211912 байтОпределяет функцию
A
; Назовите его как#A,#A,?;;
(который будет ждать, пока пользователь введет любой номер). В качестве альтернативы, позвоните, как#A,#A,n;;
где-n
нибудь номер.источник
Юлия, 21 год
затем
p // q - буквенное обозначение Юлии рациональных чисел.
источник