Wyzwanie

W przypadku tego wyzwania należy ustalić, czy dana liczba znajduje się w zestawie Cantor. Najpierw zdefiniujmy zestaw Cantora.

Najpierw zacznij od liczb od 0 do 1. Żadnych liczb poza tym zakresem nie ma w zestawie Cantor. Teraz podzielmy liczby na trzy równe części: [0,1 / 3], [1 / 3,2 / 3], [2/3, 1]. Wszelkie liczby spoza zakresu pierwszej i ostatniej części nie znajdują się w zestawie Cantor. Teraz powtórz ten proces dla segmentów [0,1 / 3] i [2/3, 1]. Następnie powtarzasz to, co zostało. Robisz to zawsze. Na koniec wszystkie pozostałe liczby znajdują się w zestawie Cantor. Oto schemat pierwszych sześciu iteracji:

Wejście

Dwie liczby całkowite xi y.
0 < y < 2^15
0 <= x <= y
Największym wspólnym mianownikiem xi yjest 1, chyba że x == 0.

Wynik

Prawda, jeśli x/yjest w zestawie Cantor.
Falsy, jeśli x/ynie ma go w zestawie Cantor.

Przykłady

Zobaczmy teraz kilka przykładów liczb, które są w zestawie Cantor.

1/3 -> true  

Jest na granicy, a granice nigdy nie są usuwane.

1/4 -> true  

1/4nigdy nie znajduje się w środkowej trzeciej części segmentu, chociaż nigdy nie znajduje się na granicy. Jeśli podążasz jego ścieżką, zobaczysz, że na przemian znajduje się ona w pierwszej i ostatniej trzeciej części sekcji.

1/13 -> true  

1/13 na przemian między pierwszą, pierwszą i ostatnią sekcją.

1/5 -> false

1/5 wpada do pierwszego pustego bloku trzeciego rzędu na powyższym schemacie, między 1/9 a 2/9.

Inne przypadki testowe:

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

Za pomocą tego fragmentu możesz wypróbować inne liczby:

function isCantor(t,r){var n=new Set;if(0>r)return isCantor(-t,-r);if(0==r)return!1;if(0>t||t>r)return!1;for(;;){if(t%r===0)return!0;if(1===Math.floor(t/r))return!1;if(n.has(t))return!0;n.add(t),t=t%r*3}}$("#test").click(function(){var t=parseInt($("#x").val()),r=parseInt($("#y").val());if(isNaN(t)||isNaN(r)||0==r)return void $("#result").text("Invalid input");var n=isCantor(t,r),i=(n?"I":"Not i")+"n the Cantor set.";$("#result").text(i)});

input{width:30px}button{margin-left:7px}

<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><input id=x>/<input id=y><button id=test>Test</button><p id=result>

Cel

Osoba z najmniejszą liczbą bajtów wygrywa.

Mathematica, 54 bajty

If[Last@#===1,Most@#,#]&@RealDigits[#,3][[1]]~FreeQ~1&

Nienazwana funkcja pobiera ułamek x/yjako dane wejściowe, gdzie y > 0i 0 ≤ x ≤ y, i zwraca Truelub False.

Rzeczywista liczba od 0 do 1 znajduje się w zestawie Cantora dokładnie wtedy, gdy żadna z cyfr w rozwinięciu podstawy-3 nie jest równa 1; wyjątkiem jest to, że ułamek, którego mianownikiem jest potęga 3 (której ekspansja podstawy 3 kończy się), może zakończyć się na 1.

RealDigits[#,3][[1]]podaje wszystkie cyfry rozszerzenia bazowego 3 wejścia ułamkowego #, w formie {1, 0, 2, {0, 1, 0, 2}}: ostatnia lista jest okresową częścią rozszerzenia, natomiast liczby całkowite są cyframi przed rozpoczęciem okresowości. Jeśli rozszerzenie base-3 jest od razu okresowe, wynik jest podobny {{0, 1, 0, 2}}; jeśli rozszerzenie base-3 zakończy się, formularz jest podobny {1, 0, 2}.

Chcemy więc sprawdzić, ~FreeQ~1czy lista jest wolna od 1s. Jednak ze względu na zakończenie ekspansji chcemy usunąć ostatni element listy, jeśli jest on równy 1; właśnie to If[Last@#===1,Most@#,#]osiąga. (Jest ===to konieczne, aby porównać potencjalną listę z 1: ==sam w tej sytuacji nie jest oceniany).

C (gcc) , 61 59 58 bajtów

f(x,y,i){for(i=y;i--&&x<y;)x=(y-x<x?y-x:x)*3;return x<=y;}

Wykorzystuje symetrię zestawu Cantor. Łamie się po yiteracjach, aby uniknąć nieskończonej pętli.

Wypróbuj online!

Galaretka , 22 17 16 15 bajtów

,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ

Drukuje 3 za prawdę, nic za fałsz.

Wypróbuj online!

tło

Znany własność zbioru Cantora jest to, że zawiera dokładnie te numery między 0 i 1 , które mogą być pisane bez 1 -tych w ich potrójnego ekspansji.

Zauważ, że niektóre liczby - dokładnie prawe krawędzie zamkniętych przedziałów zaangażowanych w konstrukcję zestawu - można zapisać za pomocą pojedynczej (końcowej) 1 lub nieskończonej ilości końcowych 2 . Na przykład 1 = 1 ₃ = 0,22222… ₃ i 1/3 = 0,1 ₃ = 0,022222… ₃ , podobnie jak 0,5 ₁₀ = 0,499999… ₁₀ .

Aby uniknąć specjalnego wstawiania prawych krawędzi, możemy sprawdzić, czy 1 jest najkrótszym rozwinięciem dziesiętnym zarówno x / y, jak i 1 - x / y = (y - x) / y , gdzie x / y jest prawą krawędzią iff (y - x) / y jest lewą krawędzią. Jeśli przynajmniej jeden z nich nie zawiera żadnych 1 , x / y należy do zbioru Cantor.

Jak to działa

,ạµ%⁹×3µÐĿ:⁹Ḅ3ḟ  Main link. Left argument: x. Right argument: y

 ạ               Absolute difference; yield y - x.
,                Pair; yield [x, y - x].
       µ         Begin a new, monadic chain with argument [a, b] := [x, y - x].
  µ     ÐĿ       Repeatedly execute the links in between until the results are no
                 longer unique, updating a and b after each execution. Return the
                 array of all unique results.
   %⁹              Compute [a % y, b % y].
     ×3            Compute [3(a % y), 3(b % y)].
                 This yields all unique dividends of the long division of x by y in
                 base 3.
          :⁹     Divide all dividends by y to get the corresponding ternary digits.
            Ḅ    Unbinary; turn [1, 1] into 3, other pairs into other numbers.
             3ḟ  Remove all occurrences of the resulting numbers from [3], leaving
                 an empty array if and only if one pair [a, b] is equal to [1, 1].

JavaScript (ES6), 65 67

Edytuj 2 bajty zapisane thx @Luke

n=>d=>(z=>{for(q=0;~-q*n*!z[n];n=n%d*3)z[n]=1,q=n/d|0})([])|q!=1|!n

Mniej golfa

n=>d=>{
  z = []; // to check for repeating partial result -> periodic number
  for(q = 0; q != 1 && n != 0 && !z[n]; )
    z[n] = 1,
    q = n / d | 0,
    n = n % d * 3
  return q!=1 | n==0
}

Test

f=
n=>d=>(z=>{for(q=0;~-q*n*!z[n=n%d*3];q=n/d|0)z[n]=1})([])|q!=1|!n
  

console.log(
'Truthy: 1/3 1/4 1/13 0/4 3/10 3/4 10/13 1/1\nFalsey: 1/5 12/19 5/17 3/5 1/7 1/2'.replace(/(\d+).(\d+)/g,(a,x,y)=>a+':'+f(x)(y))
)  

JavaScript (ES6), 55 bajtów

y=>f=(x,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,z|q==1,n+1):1

Użyj, curry najpierw w mianowniku, a drugi w liczniku. Standardowy formularz jest bajtem dłuższym:

f=(x,y,z,n=~y,q=x/y|0)=>n?!z|!q&&f(x%y*3,y,z|q==1,n+1):1

Wyjaśnienie

Jeśli ułamek nie znajduje się w zestawie Kantora, w pewnym momencie musi wpaść w jedną ze środkowych sekcji; dlatego jego reprezentacja w podstawie 3 musi zawierać 1, po którym w pewnym momencie następuje niezerowa cyfra. Tak to działa:

• z śledzi, czy znaleźliśmy 1.
• q jest bieżącą cyfrą w bazie 3.
• !z|!qma wartość prawda, jeśli zjest fałszem (nie znaleźliśmy 1) lub qjest fałszem (bieżąca cyfra to 0).

Jeśli nsprowadza się do zera, zanim znajdziemy niezerową cyfrę gdzieś po 1, ułamek jest w zestawie Cantora i wracamy 1.

Narzędzia Bash + GNU, 62 bajty

dc -e3o9d$2^$1*$2/p|tr -cd 012|grep -P "1(?!(0{$2,}|2{$2,})$)"

Wypróbuj online!

Przekaż dwa argumenty całkowite z arg1 <= arg2 i 0 <arg2.

Dane wyjściowe są zwracane w kodzie wyjścia (0 dla fałszowania, 1 dla prawdy), na co pozwalają metody we / wy PPCG .

Podejrzewam, że regex może być dalej golfowy, może nawet eliminując polecenie tr na korzyść użycia grep -z, ale jest to najkrótszy, jaki udało mi się wymyślić. (Niestety, grep -z jest niezgodny z grep -P, a dla składni?! Wymagana jest opcja -P, aby uzyskać wyrażenia regularne w stylu perla).

Program testowy i dane wyjściowe:

for x in '1 3' '1 4' '1 13' '1 5' '0 4' '3 10' '3 4' '10 13' '1 1' '12 19' '5 17' '3 5' '1 7' '1 2'
  do
    printf %-6s "$x "
    ./cantor $x >/dev/null && echo F || echo T
  done

1 3   T
1 4   T
1 13  T
1 5   F
0 4   T
3 10  T
3 4   T
10 13 T
1 1   T
12 19 F
5 17  F
3 5   F
1 7   F
1 2   F

Wyjaśnienie

część dc (argumentami są xiy):

3o     Set output base to 3.
9      Push 9 on the stack.
d      Duplicate the top of the stack. (The extra 9 on the stack isn't actually used, but I need some delimiter in the code here so that the 9 doesn't run into the number coming up next.  If I used a space as a no-op, then I'd need to quote it for the shell, adding an extra character.)
$2^    Raise 9 to the y power. This number in base 3 is 1 followed by 2y 0's.
$1*$2/ Multiply the base-3 number 10....0 (with 2y 0's in it) by x and then divide by y (truncating). This computes 2y digits (after an implied ternary point) of x/y.  That's enough digits so that the repeating part of the rational number is there at least twice.
p      Print the result, piping it to tr.

część tr i grep:

Drobny problem polega na tym, że chociaż dc obsługuje dowolnie duże liczby całkowite, gdy dc wypisuje dużą liczbę, podzieli go na 69-znakowe linie, przy czym każda linia oprócz ostatniego kończy się odwrotnym ukośnikiem i nową linią po każdej linii.

Polecenie tr usuwa wszelkie ukośniki odwrotne i znaki nowej linii. To pozostawia tylko jedną linię.

Polecenie grep używa następnie wyrażenia regularnego w stylu perla (opcja -P, która jest rozszerzeniem GNU). Wyrażenie regularne pasuje, jeśli wiersz zawiera 1, po którym nie następuje co najmniej y 0 lub co najmniej y 2, które kończą łańcuch.

Jest to dokładnie to, co jest potrzebne do zidentyfikowania x / y jako nie będącego w zbiorze Cantora, ponieważ powtarzającą się część reprezentacji base-3 liczby wymiernej x / y można postrzegać jako rozpoczynającą się od cyfry # y + 1 po punkcie trójkowym , i ma najwyżej y cyfr.

CJam (19 bajtów)

{_@3@#*\/3b0-W<1&!}

Zestaw testów online

Jest to anonimowy blok (funkcja), który przyjmuje dwa argumenty na stosie i pozostawia 0lub 1na stosie. Działa on przez część podstawy konwersji x/ydo ypodstawy 3cyfr powrocie prawdziwe wtedy i tylko wtedy zawierają one żadnych 1lub tylko 1jest częścią sufiksu 1 0 0 0 ....

{            e# Begin a block
  _@3@#*\/3b e#   Base conversion
   0-W<      e#   Remove all zeros and the final non-zero digit
   1&!       e#   True iff no 1s are left
}

Pyth , 14 bajtów

gu*3hS,G-QGQE0

Na podstawie mojego rozwiązania C. yw pierwszym wierszu wprowadzania, xw drugim.

                Q = y
 u         QE   G = x
                loop y times
  *3                x = 3 *
    hS,G                min(x,
        -QG                 y-x)
g            0  return x >= 0

Jeśli x/yznajduje się w zestawie Cantor, xpozostaje pomiędzy 0a y. W przeciwnym razie xstaje się większy niż yw jednym punkcie, a następnie odchyla się do ujemnej nieskończoności w pozostałych iteracjach.

Wypróbuj online!

Partia, 91 bajtów

@set/ai=%3+1,n=%1*3%%%2,f=%1*3/%2%%2,f^|=j=!((%2-i)*n)
@if %f%==0 %0 %n% %2 %i%
@echo %j%

Testuje pierwsze y-13 cyfry podstawy x/y. ito liczba przetestowanych cyfr. njest następną wartością x. jjest prawdziwe, jeśli nosiągnie zero (ponieważ rozszerzenie kończy się) lub przetestowaliśmy y-1cyfry bez znalezienia znaku 1. fjest prawdą, jeśli jjest prawdą lub jeśli następną cyfrą jest a 1, w tym momencie przestajemy zapętlać i generować j.