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 x
i y
.
0 < y < 2^15
0 <= x <= y
Największym wspólnym mianownikiem x
i y
jest 1, chyba że x == 0
.
Wynik
Prawda, jeśli x/y
jest w zestawie Cantor.
Falsy, jeśli x/y
nie 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/4
nigdy 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:
Cel
Osoba z najmniejszą liczbą bajtów wygrywa.
źródło
x == 0
Odpowiedzi:
Mathematica, 54 bajty
Nienazwana funkcja pobiera ułamek
x/y
jako dane wejściowe, gdziey > 0
i0 ≤ x ≤ y
, i zwracaTrue
lubFalse
.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~1
czy lista jest wolna od1
s. Jednak ze względu na zakończenie ekspansji chcemy usunąć ostatni element listy, jeśli jest on równy1
; właśnie toIf[Last@#===1,Most@#,#]
osiąga. (Jest===
to konieczne, aby porównać potencjalną listę z1
:==
sam w tej sytuacji nie jest oceniany).źródło
IsCantorNumber
ale ma funkcję pozwalającą ustalić, czy coś jest kozłem .FreeQ[RealDigits[#,3][[1]]/.{{x___,1}}:>{x},1]&
1
s w części okresowej, co prowadzi do niepoprawnych odpowiedzi. Na przykład rozszerzenie podstawy 3 o wartości 7/8 to .21212121 .... lub{{2,1}}
; ale sugerowana reguła zmieniłaby to na{{2}}
, która jest wolna od1
s, ale nie powinna.#==0||FreeQ[RealDigits[#,3]/.{{x___,1},_}:>{x},1]&
? Jeśli zakończy się, a niezerowaRealDigits[#,3]
będzie miała formę,{{__Integer},-1}
a jeśli się powtórzy, będzie miała formę{{___Integer,{__Integer}},-1}
, prawda? Jestem na telefonie komórkowym, więc trudno jest teraz przetestować. Jeśli toRealDigits
zadziała , użycie notacji infix może również działać.C (gcc) ,
615958 bajtówWykorzystuje symetrię zestawu Cantor. Łamie się po
y
iteracjach, aby uniknąć nieskończonej pętli.Wypróbuj online!
źródło
Galaretka ,
22171615 bajtówDrukuje 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 3 = 0,22222… 3 i 1/3 = 0,1 3 = 0,022222… 3 , podobnie jak 0,5 10 = 0,499999… 10 .
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
źródło
3
jest prawdziwątrue
+1.JavaScript (ES6), 65
67Edytuj 2 bajty zapisane thx @Luke
Mniej golfa
Test
źródło
n=n%d*3
przyq=n/d|0
czym zastąpićz[n]
zz[n=n%d*3]
JavaScript (ES6), 55 bajtów
Użyj, curry najpierw w mianowniku, a drugi w liczniku. Standardowy formularz jest bajtem dłuższym:
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|!q
ma wartość prawda, jeśliz
jest fałszem (nie znaleźliśmy 1) lubq
jest fałszem (bieżąca cyfra to 0).Jeśli
n
sprowadza się do zera, zanim znajdziemy niezerową cyfrę gdzieś po 1, ułamek jest w zestawie Cantora i wracamy1
.źródło
Narzędzia Bash + GNU, 62 bajty
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:
Wyjaśnienie
część dc (argumentami są xiy):
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.
źródło
CJam (19 bajtów)
Zestaw testów online
Jest to anonimowy blok (funkcja), który przyjmuje dwa argumenty na stosie i pozostawia
0
lub1
na stosie. Działa on przez część podstawy konwersjix/y
doy
podstawy3
cyfr powrocie prawdziwe wtedy i tylko wtedy zawierają one żadnych1
lub tylko1
jest częścią sufiksu1 0 0 0 ...
.źródło
Pyth , 14 bajtów
Na podstawie mojego rozwiązania C.
y
w pierwszym wierszu wprowadzania,x
w drugim.Jeśli
x/y
znajduje się w zestawie Cantor,x
pozostaje pomiędzy0
ay
. W przeciwnym raziex
staje się większy niży
w jednym punkcie, a następnie odchyla się do ujemnej nieskończoności w pozostałych iteracjach.Wypróbuj online!
źródło
Partia, 91 bajtów
Testuje pierwsze
y-1
3 cyfry podstawyx/y
.i
to liczba przetestowanych cyfr.n
jest następną wartościąx
.j
jest prawdziwe, jeślin
osiągnie zero (ponieważ rozszerzenie kończy się) lub przetestowaliśmyy-1
cyfry bez znalezienia znaku1
.f
jest prawdą, jeślij
jest prawdą lub jeśli następną cyfrą jest a1
, w tym momencie przestajemy zapętlać i generowaćj
.źródło