Drzewo Sterna-Brocota jest drzewo binarne, w którym każdy z frakcji frakcji uzyskuje się przez dodanie licznik i mianownik dwóch frakcji sąsiednich ją w ilości powyżej.
Jest generowany przez rozpoczynanie od 0/1
i 1/0
jako „ułamki punktu końcowego”, a następnie iterowanie przez umieszczenie jednej frakcji między każdą kolejną parą ułamków przez dodanie razem liczników i mianowników tych ułamków, w następujący sposób:
0. 0/1 1/0
1. 0/1 1/1 1/0
2. 0/1 1/2 1/1 2/1 1/0
3. 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
4. 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0
W każdej iteracji drzewa Sterna-Brocota ( n
iteracja) 2^n + 1
w sekwencji znajdują się elementy, którym możemy przypisać ułamek od 0/2^n
do 2^n/2^n
. Każda nowa iteracja po prostu wstawia jedną frakcję „w połowie” między każdą parą kolejnych frakcji.
To sprawia, że drzewo Sterna-Brocota jest mapowaniem jeden na jeden między dodatnimi liczbami wymiernymi a ułamkami binarnymi między 0 a 1, tym samym służąc również jako dowód, że oba zestawy mają tę samą liczność.
Twoim zadaniem jest napisanie programu lub funkcji, która, biorąc pod uwagę licznik i mianownik dodatniej liczby wymiernej w najniższych kategoriach, określa ułamek binarny, który odpowiada pozycji tej frakcji w drzewie Sterna-Brocota.
Przykłady wejść i wyjść podano poniżej:
2/3 -> 3/8 (4th number in iteration 3)
4/7 -> 9/32 (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2 (middle number in the first iteration)
Dane wejściowe, których nie potrzebujesz obsługiwać, ale zostały uwzględnione w celach informacyjnych:
0/1 -> 0/1 (0/1 is considered the left number)
1/0 -> 1/1 (1/0 is considered the rightmost number)
Zwycięża najkrótszy program w dowolnym języku, aby osiągnąć ten cel.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
, itd.). Jeśli liczba wygenerowana w ten sposób dla węzła wynosin
, wówczas2^lg n
(log binarny) jest najwyższym ustawionym bitemn
, a pożądana część binarna to(2*(n - 2^lg n) + 1) / 2^(lg n + 1)
. (Każdy, kto spróbuje asemblera w zestawie instrukcji z bitem najwyższego zestawu, prawdopodobnie będzie chciał skorzystać z tego podejścia).Odpowiedzi:
GolfScript (
49 4846 znaków)lub
Obie są funkcjami, które przyjmują licznik i mianownik na stos i pozostawiają licznik i mianownik na stosie. Demo online .
Podstawowa idea wyrażona jest w pseudokodzie w sekcji 4.5 Matematyka konkretna (p122 w moim wydaniu):
Jeśli ciąg Ls i Rs jest interpretowany jako wartość binarna z L = 0 i R = 1, wówczas dwukrotność tej wartości plus jeden jest licznikiem, a mianownik jest o jeden bit dłuższy.
Jako przedmiot zainteresowania Golfscripters, jest to jedna z tych rzadkich sytuacji, w których odkryłem, że jest to przydatne. (Ok, używam go tylko jako licznika pętli, ale to lepsze niż nic).
źródło
Mathematica,
130 114111 znakówPrzykład:
źródło
Ruby,
132125Rubied i grał w golfa referencyjne rozwiązanie z @JoeZ.
Przykłady użycia:
źródło
Ruby (69 znaków)CoffeeScript (59 znaków)Jest to funkcja, która przyjmuje argumenty i mianownik jako argumenty i zwraca tablicę zawierającą licznik i mianownik po bijectcji.
Demo online
Wykorzystuje to samo podejście, co moje powyższe rozwiązanie GolfScript, ale jest o wiele bardziej czytelne, ponieważ mogę używać 4 zmiennych bez martwienia się o boksowanie i rozpakowywanie do tablicy. Wybrałem CoffeeScript, ponieważ nie zawiera on prefiksu zmiennych
$
(20 znaków zapisanych np. W PHP), ma krótką składnię definicji funkcji, która pozwala na domyślne wartości parametrów (więc nie ma potrzeby zawijaniaf(a,b,x,y)
funkcjig(a,b) = f(a,b,0,1)
), i pozwala mi używać booleanów jako liczb całkowitych w wyrażenia o użytecznych wartościach. Dla tych, którzy go nie znają, CoffeeScript nie ma standardowego operatora trójskładnikowego w stylu C (C?P:Q
), ale mogę goC&&P||Q
tutaj zastąpić , ponieważP
nigdy nie będzie fałszem.Prawdopodobnie bardziej elegancką, ale niewątpliwie krótszą alternatywą jest zastąpienie powtarzanego odejmowania dzieleniem i modulo:
(65 znaków; demo online ). Pisanie w ten sposób ujawnia związek z algorytmem Euclida.
źródło
a<b
których oszczędzasz jeden znak. Inliningc
daje kolejne dwa. Możesz również rozważyć składnięf=->a,b,x=0,y=1{...}
jeszcze krótszej definicji.c=a<b ?
z dodatkową spacją pob
. W przeciwnym razie znak zapytania jest traktowany jako częśćb
.Python - 531
Niekluczone rozwiązanie w Pythonie, które ma służyć jako rozwiązanie referencyjne ostatniego miejsca:
Po prostu wykonuje binarne wyszukiwanie między ułamkami, wykorzystując fakt, że mediana dowolnych dwóch ułamków zawsze będzie znajdować się między wartościami tych dwóch ułamków.
źródło
GolfScript, 54 znaki
Dane wejściowe należy podać na STDIN w formie określonej w zadaniu. Możesz wypróbować kod online .
źródło
Mathematica 138
Nie tak usprawniona jak procedura alephalpha, ale była to najlepsza, jaką do tej pory mogłem wyprodukować.
Testowanie
źródło
JavaScript 186
może być mniej, ale lubię czytelny golf
źródło
Haskell , 125 bajtów
Wypróbuj online!
Dane wejściowe i wyjściowe w postaci pary
(n,d)
.Krótkie wyjaśnienie:
n
konstruuje następny wiersz z poprzedniego, patrząc na każdą parę frakcji i wstawiając nowy między pierwszą a rekurencyjną (która umieści tam drugą frakcję). Przypadek podstawowy jest bardzo prosty, ponieważ jest to po prostu funkcja tożsamości.t
Funkcja iteracje tej funkcji w nieskończoność w oparciu od stanu początkowego tylko z dwóch frakcji brzegowych.t
następnie indeksuje każdy wiersz (i
) i każdy element w wierszu (j
) i szuka pierwszej frakcji pasującej do tego, czego szukamy. Gdy się znajdzie, dajej
jako licznik i2^i
mianownik.źródło