Соревнование
Для этого испытания вы должны определить, входит ли данное число в набор Кантора. Итак, во-первых, давайте определим набор Кантора.
Сначала начните с чисел от 0 до 1. Любые числа вне этого диапазона не входят в набор Кантора. Теперь давайте разделим числа на три равные части: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Любые числа, не входящие в диапазоны первой и последней частей, не входят в набор Кантора. Теперь повторите этот процесс для сегментов [0,1 / 3] и [2/3, 1]. Затем вы повторяете, что осталось. Вы продолжаете делать это вечно. В конце концов, все оставшиеся числа находятся в наборе Кантора. Вот схема первых шести итераций:
вход
Два целых числа x
и y
.
0 < y < 2^15
0 <= x <= y
Наибольшим общим знаменателем x
и y
является 1, если только x == 0
.
Выход
Правда, если x/y
есть в наборе Кантора.
Ложь, если x/y
нет в наборе Кантора.
Примеры
Теперь давайте посмотрим несколько примеров чисел, которые есть в наборе Кантора.
1/3 -> true
Это на границе, и границы никогда не удаляются.
1/4 -> true
1/4
никогда не находится в средней трети сегмента, хотя он также никогда не находится на границе. Если вы пойдете по его пути, вы обнаружите, что он чередуется между первой и последней третями раздела.
1/13 -> true
1/13
чередуется между первым, первым и последним разделами.
1/5 -> false
1/5
попадает в первый пустой блок третьего ряда на приведенной выше диаграмме, между 1/9 и 2/9.
Другие тестовые случаи:
0/4 -> true
3/10 -> true
3/4 -> true
10/13 -> true
1/1 -> true
12/19 -> false
5/17 -> false
3/5 -> false
1/7 -> false
1/2 -> false
Вы можете попробовать другие числа с этим фрагментом:
Задача
Человек с наименьшим количеством байтов побеждает.
источник
x == 0
Ответы:
Mathematica, 54 байта
Безымянная функция, принимающая дробь в
x/y
качестве входных данных, гдеy > 0
и0 ≤ x ≤ y
, и возвращающаяTrue
илиFalse
.Действительное число от 0 до 1 находится в наборе Кантора именно тогда, когда ни одна из цифр в его расширении base-3 не равна 1; Исключением является то, что дробь, знаменатель которой является степенью 3 (чье расширение базы-3, следовательно, заканчивается), может заканчиваться на 1.
RealDigits[#,3][[1]]
дает все цифры в расширении base-3 дробного ввода#
в такой форме{1, 0, 2, {0, 1, 0, 2}}
: последний список - это периодическая часть расширения, в то время как целые числа заранее - это цифры до начала периодичности. Если расширение base-3 является периодическим сразу, вывод будет похож на{{0, 1, 0, 2}}
; если расширение base-3 завершается, форма выглядит как{1, 0, 2}
.Итак, мы хотим проверить, используя
~FreeQ~1
, свободен ли список1
s или нет. Однако из-за прекращения расширения мы хотим удалить последний элемент списка, если он равен1
; это то, чтоIf[Last@#===1,Most@#,#]
выполняет. (===
Требуется, чтобы сравнить потенциальный список с1
:==
одно остается в этой ситуации неоцененным.)источник
IsCantorNumber
но имеет функцию, чтобы определить, является ли что-то козлом .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
s в периодической части, что приводит к неправильным ответам. Например, расширение base-3 7/8 равно .21212121 .... или{{2,1}}
; но предлагаемое правило изменит это на{{2}}
, которое свободно от1
s, но не должно быть.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Если оно завершается и ненулевое значениеRealDigits[#,3]
будет иметь форму,{{__Integer},-1}
а если оно повторяется, оно будет иметь форму{{___Integer,{__Integer}},-1}
, верно? Я на мобильном, так что сейчас сложно проверить. Если это работает, использование инфиксной нотации дляRealDigits
может также работать.С (ССЗ) ,
615958 байтЭксплуатирует симметрию множества Кантора. Перерывы после
y
итераций, чтобы избежать бесконечного цикла.Попробуйте онлайн!
источник
Желе ,
22171615 байтОтпечатки 3 для правды, ничего для фальши.
Попробуйте онлайн!
Фон
Хорошо известным свойством множества Кантора является то, что оно содержит именно те числа от 0 до 1, которые можно записать без 1 в их троичном разложении.
Обратите внимание, что некоторые числа - в точности правые края замкнутых интервалов, участвующих в построении множества - могут быть записаны либо с одной (конечной) 1, либо с бесконечным количеством конечных 2 . Например, 1 = 1 3 = 0,22222… 3 и 1/3 = 0,1 3 = 0,022222… 3 , так же как 0,5 10 = 0,499999… 10 .
Для того, чтобы избежать специального кожуха правые края, мы можем проверить 1 «S является кратчайшим расширение десятичной как в х / у и 1 - х / у = (у - х) / у , где х / у является правым краем тогда и только тогда (y - x) / y - левый край. Если хотя бы один из них не содержит 1 , x / y принадлежит множеству Кантора.
Как это устроено
источник
3
это правдаtrue
+1.JavaScript (ES6), 65
67Редактирование 2 байта сохраняются THx @Luke
Меньше гольфа
Тестовое задание
источник
n=n%d*3
с ,q=n/d|0
а затем заменитьz[n]
сz[n=n%d*3]
JavaScript (ES6), 55 байт
Используйте, каррируя в знаменателе первого и числителя второго. Стандартная форма на байт длиннее:
объяснение
Если дробь не входит в набор Кантора, она должна попасть в одну из средних секций в некоторой точке; поэтому его представление в базе 3 должно содержать 1, за которым в некоторой точке стоит ненулевая цифра. Вот как это работает:
z
отслеживает, нашли ли мы 1.q
текущая цифра в базе 3.!z|!q
true, еслиz
false (мы не нашли 1) илиq
false (текущая цифра 0).Если
n
спустится до нуля, прежде чем мы найдем ненулевую цифру где-то после 1, дробь будет в множестве Кантора, и мы вернемся1
.источник
Утилиты Bash + GNU, 62 байта
Попробуйте онлайн!
Передайте ему два целочисленных аргумента с arg1 <= arg2 и 0 <arg2.
Вывод возвращается в коде выхода (0 для ложного, 1 для правдивого), как это разрешено методами ввода-вывода PPCG .
Я подозреваю, что регулярное выражение может быть улучшено, возможно, даже исключив команду tr в пользу использования grep -z, но это самое короткое, что я смог придумать. (К сожалению, grep -z несовместим с grep -P, а параметр -P для получения регулярных выражений в стиле perl необходим для синтаксиса?!)
Программа тестового стенда и выход:
объяснение
часть dc (аргументы x и y):
Часть tr и grep:
Незначительная проблема заключается в том, что, хотя dc обрабатывает произвольно большие целые числа, когда dc печатает большое число, он разбивает его на строки из 69 символов, причем каждая строка, кроме последней, заканчивается обратной косой чертой и с новой строкой после каждой строки.
Команда tr удаляет все обратные слеши и переводы строки. Это оставляет только одну строку.
Затем команда grep использует регулярное выражение в стиле perl (опция -P, которая является расширением GNU). Регулярное выражение совпадает, если строка содержит 1, за которым не следует, по крайней мере, y 0 или, по крайней мере, y 2, которые затем заканчивают строку.
Это именно то, что необходимо для определения x / y как не входящего в набор Кантора, потому что повторяющаяся часть представления base-3 рационального числа x / y может рассматриваться как начинающаяся с цифры # y + 1 после троичной точки и длиной не более y цифр.
источник
CJam (19 байт)
Набор онлайн-тестов
Это анонимный блок (функция), который принимает два аргумента в стеке и оставляет
0
или1
в стеке. Он работает путем базового преобразования дробиx/y
вy
базовые3
цифры и возврата истины, если они не содержат1
или1
являются частью суффикса1 0 0 0 ...
.источник
Pyth , 14 байт
Основано на моем C-решении.
y
на первой строке ввода,x
на второй.Если
x/y
находится в пределах набора Кантора,x
остается между0
иy
. В противном случаеx
становится больше, чемy
в одной точке, затем расходится до отрицательной бесконечности на оставшихся итерациях.Попробуйте онлайн!
источник
Пакет, 91 байт
Тестирует первую
y-1
базу из 3 цифрx/y
.i
количество проверенных цифрn
это следующее значениеx
.j
Значение true, еслиn
достигает нуля (поскольку расширение прекращается) или мы проверилиy-1
цифры, не найдя a1
.f
true, еслиj
true или если следующая цифра a1
, в этот момент мы прекращаем цикл и выводимj
.источник