Istnieje 500 nieoficjalnych nagród za powtórzenie najlepszej najlepszej odpowiedzi .
Cel
Twoim celem jest pomnożenie dwóch liczb przy użyciu jedynie bardzo ograniczonego zestawu operacji arytmetycznych i przypisywania zmiennych.
- Dodanie
x,y -> x+y
- Wzajemne
x -> 1/x
( bez podziałux,y -> x/y
) - Negacja
x -> -x
( nie odejmowaniex,y -> x-y
, choć można to zrobić jako dwie operacjex + (-y)
) - Stała
1
(niedozwolone są inne stałe, oprócz tych, które zostały wygenerowane przez operacje z1
) - Zmienne przypisanie
[variable] = [expression]
Punktacja: wartości zaczynają się od zmiennych a
i b
. Twoim celem jest zapisanie ich produktu a*b
w zmiennej c
przy użyciu jak najmniejszej liczby operacji. Każda operacja i przypisanie +, -, /, =
kosztuje punkt (równoważnie, każde użycie (1), (2), (3) lub (4)). Stałe 1
są bezpłatne. Wygrywa rozwiązanie o najmniejszej liczbie punktów. Tiebreak jest najwcześniejszym postem.
Dodatek: Twoje wyrażenie musi być poprawne arytmetycznie dla liczb „losowych” a
i b
. To może nie na środek zera podzbiór R 2 , czyli zestawu, który nie ma obszaru, jeśli wykreślone w a
- b
kartezjańskiej płaszczyźnie. (Jest to prawdopodobnie potrzebne ze względu na wzajemność wyrażeń, które mogą być 0
podobne 1/a
).
Gramatyka:
To jest golf atomowy . Żadne inne operacje nie mogą być użyte. W szczególności oznacza to brak funkcji, warunków, pętli lub nienumerycznych typów danych. Oto gramatyka dozwolonych operacji (możliwości są oddzielone |
). Program jest sekwencją <statement>
s, gdzie a <statement>
podaje się następująco.
<statement>: <variable> = <expr>
<variable>: a | b | c | [string of letters of your choice]
<expr>: <arith_expr> | <variable> | <constant>
<arith_expr>: <addition_expr> | <reciprocal_expr> | <negation_expr>
<addition_expr>: <expr> + <expr>
<reciprocal_expr>: 1/(<expr>)
<negation_expr>: -<expr>
<constant>: 1
W rzeczywistości nie musisz pisać kodu w tej dokładnej gramatyce, o ile jest jasne, co robisz, a liczba operacji jest prawidłowa. Na przykład, można napisać a-b
do a+(-b)
i liczyć je jako dwie operacje, lub zdefiniować makra dla zwięzłości.
(Było poprzednie pytanie Mnożenie bez mnożenia , ale pozwoliło na znacznie luźniejszy zestaw operacji).
Odpowiedzi:
22 operacje
Wypróbuj online!
Operacje to 10 dodatków, 7 odwrotności, 2 negacje i 3 zadania.
Jak więc to dostałem? Zacząłem od obiecującego wzoru sumy dwóch frakcji dwupoziomowych, motywu, który pojawiał się podczas wielu poprzednich prób.
c = 1/(1/x + 1/y) + 1/(1/z + 1/w)
Gdy ograniczymy sumę do
x+y+z+w=0
, nastąpi piękne anulowanie, dając:c = (x+z)*(y+z)/(x+y)
,który zawiera produkt. (Często łatwiej jest je zdobyć
t*u/v
niżt*u
ponieważ pierwszy ma stopień 1.)Istnieje bardziej symetryczny sposób myślenia o tym wyrażeniu. Z ograniczeniem
x+y+z+w=0
ich wartości są określone przez trzy parametryp,q,r
ich sum par.a my mamy
c=-q*r/p
. Sumap
jest rozróżniana jako mianownik poprzez odpowiadanie parom(x,y)
i(z,w)
zmiennym, które są w tej samej części.To miłe wyrażenie dla
c
inp,q,r
, ale frakcja piętrowa jest w środku,x,y,z,w
więc musimy wyrazić to pierwsze pod względem drugiego:Teraz chcemy wybrać
p,q,r
taki, który będziec=-q*r/p
równya*b
. Jednym wyborem jest:Następnie podwojone wartości
q
ir
są dogodnie zmniejszone o połowę w:Zapisywanie
2
jako zmiennąt
i podłączanie ich do równaniac
daje rozwiązanie 24-operacyjne.Jest 12 dodatków, 6 odwrotności, 4 negacje i 2 zadania.
Wiele OPS są spędzony wyrażając
x,y,z,w
w kategoriach1,a,b
. Aby zapisać operacje, zamiast tego wyrażajx
wp,q,r
(a więca,b,1
), a następnie piszy,z,w
w kategoriachx
.Wybieranie
i wyrażając
c
z zaprzeczeniemc=-q*r/p
, jak otrzymujemyNiestety zmniejszenie o połowę
x
jest kosztowne. Należy tego dokonać poprzez odwrócenie, dodanie wyniku do siebie i ponowne odwrócenie. Mamy również Negate produkowaćnx
dla-x
, ponieważ to właśniey,z,w
stosowanie. To daje nam rozwiązanie 23-operacyjne:itx
wynosi 1 / (2 * x) inx
jest-x
. Ostateczna optymalizacja wyrażania1/x
jakoitx+itx
zamiast szablonów1/(-nx)
wycina postać i sprowadza rozwiązanie do 22 operacji.źródło
itx + itx
występuje dwa razy, aleitx
nie występuje w żadnym innym kontekście. Zdefiniuj zamiast,ix = (1+1)/(1+a+b)
a zastąpisz dwa dodatki jednym.m = -1
można uzyskać 20:nx = (1+a+b)/(m+m); c = m/(m/nx + 1/(1+nx)) + m/(1/(a+nx) + 1/(b+nx))
a
ib
są tylko jeden od siebie, to albo,a + nx = 0
albob + nx = 0
, powodując podzielenie rozwiązania przez zero.23 operacje
dowód na wybuch:
Wykorzystałem wolfram alpha, aby uzyskać ten piękny obraz (wolfram alpha próbował mnie zmusić do subskrypcji pro, aby go zapisać, ale potem ctrl-c ctrl-v ;-)):
wynik (z dodanym
+
odejmowaniem):źródło
29 operacji
Nie działa dla zestawu {(a, b) ∈ R 2 | a + b = 0 lub a + b = -1 lub ab = 0 lub ab = -1}. Prawdopodobnie to zero.
Struktura
rfc
(Reciprocal-Four-C) jest bardziej widoczna, jeśli zdefiniujemy makro:Zróbmy matematykę:
s(x)
, matematycznie, to,1/(1/x - 1/(x+1))
co jest po odrobinie algebry, tox*(x+1)
lubx*x + x
.rfc
, to naprawdę1/((a+b)*(a+b) + a + b - (a-b)*(a-b) - a + b + (-b) + (-b))
jest po prostu1/((a+b)^2 - (a-b)^2)
.rfc
to1/(4*a*b)
.c
jest odwrotność 4 razyrfc
, tak się1/(4/(4*a*b))
stajea*b
.źródło
s(x)
pasują do wymagań pytania, z rachunku różniczkowego, więc oznaczało to, że miałem funkcję kwadratową. Po krótkiej przeróbce odkryłem, że mogę znaleźća*b
pojęcie z różnicą podstępu do kwadratu. Kiedy to miałem, chodziło o sprawdzenie, które zadania zapisały operacje.-1
trzy razyrfc
, czy nie mógłbyś zagrać w golfa, przypisując ją do zmiennej?27 operacji
Nie kryje się za tym żadna teoria. Właśnie próbowałem zacząć
(const1+a*b)/const2
i zacząć od(1/(1-a)+1/(1+b))
i(-1/a+1/b)
.źródło
tmp
23 lata, co daje wynik 27. Fajne znalezisko.