Oblicz odwrotność silni


30

Napisz najkrótszy kod, który przyjmie dowolną liczbę rzeczywistą większą niż 1 jako dane wejściowe i wyświetli dodatnią odwrotną silnię. Innymi słowy, odpowiada na pytanie „jaka liczba czynnikowa jest równa tej liczbie?”. Użyj funkcji Gamma, aby rozszerzyć definicję silni do dowolnej liczby rzeczywistej, jak opisano tutaj .

Na przykład:

input=6 output=3 
input=10 output=3.390077654

ponieważ 3! = 6i3.390077654! = 10

Zasady

  • Zabronione jest używanie wbudowanych funkcji silni lub funkcji gamma lub funkcji zależnych od tych funkcji.
  • Program powinien być w stanie obliczyć go z dokładnością do 5 cyfr dziesiętnych, z teoretyczną możliwością obliczenia z dowolną dokładnością (powinien zawierać liczbę, która może być dowolną dużą lub małą wartością, aby uzyskać dowolną dokładność)
  • Dowolny język jest dozwolony, wygrywa najkrótszy kod ze znaków.

Dałem tutaj przykład działania . Spójrz.


2
Przydałoby się to w kilku przypadkach testowych, w szczególności do uwzględnienia danych wejściowych zerowych i ujemnych.
Peter Taylor,

Zredagowałem, że dane wejściowe powinny być większe niż 1, ponieważ w przeciwnym razie może być wiele odpowiedzi.
Jens Renders

1
W każdym razie może być wiele odpowiedzi, chyba że dodasz również wymóg, że wynik musi być większy niż 1.
Peter Taylor

Twój przykład roboczy podaje 3,99999 po wprowadzeniu 24. Czy takie rozwiązanie jest dopuszczalne?
rubik

tak, ponieważ można to uznać za 4, z dokładnością do 5 miejsc po przecinku
Jens Renders

Odpowiedzi:


13

JavaScript (116)

Czarna magia tutaj! Daje wynik w ciągu kilku milisekund .
Tylko funkcje elementarne matematyczne stosowane: ln, pow,exponential

x=9;n=prompt(M=Math);for(i=1e4;i--;)x+=(n/M.exp(-x)/M.pow(x,x-.5)/2.5066/(1+1/12/x+1/288/x/x)-1)/M.log(x);alert(x-1)

Szkoda, że ​​LaTeX nie jest obsługiwany na codegolfie, ale w zasadzie napisałem solver Newtona dla f(y)=gamma(y)-n=0i x=y-1(ponieważ x!jest gamma(x+1)) oraz aproksymacje dla funkcji gamma i digamma.

Przybliżenie gamma jest aproksymacją Stirlinga Przybliżenie
digammy użycie formuły Eulera Maclaurina
Funkcja digamma jest pochodną funkcji gamma podzielonej przez funkcję gamma:f'(y)=gamma(y)*digamma(y)

Nie golfowany:

n = parseInt(prompt());
x = 9; //first guess, whatever but not too high (<500 seems good)

//10000 iterations
for(i=0;i<10000;i++) {

  //approximation for digamma
  d=Math.log(x);

  //approximation for gamma
  g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x);

  //uncomment if more precision is needed
  //d=Math.log(x)-1/2/x-1/12/x/x+120/x/x/x/x;
  //g=Math.exp(-x)*Math.pow(x,x-0.5)*Math.sqrt(Math.PI*2)*(1+1/12/x+1/288/x/x-139/51840/x/x/x);

  //classic newton, gamma derivative is gamma*digamma
  x-=(g-n)/(g*d);
}

alert(x-1);

Przypadki testowe :

10 => 3.390062988090518
120 => 4.99999939151027
720 => 6.00000187248195
40320 => 8.000003557030217
3628800 => 10.000003941731514

Bardzo ładna odpowiedź, choć nie spełnia wymaganej precyzji i działa tylko dla liczb mniejszych niż 706
Jens Renders

@JensRenders, cóż, dodałem kilka iteracji solvera Newtona, zmieniłem początkowe zgadywanie i lepsze przybliżenie funkcji gamma. To powinno być teraz zgodne z zasadami. Pozwól mi teraz, jeśli wszystko jest w porządku :)
Michael M.

Tak, teraz jest idealnie, zagłosowałem :)
Jens Renders

1
Możesz uratować 1 znak:n=prompt(M=Math)
Florent

Spróbuj uruchomić kod na dużej liczbie, np. 10 ^ {10 ^ 6} $, i upewnij się, że otrzymasz wynik w postaci liczby całkowitej
David G. Stork

13

Matematyka - 74 54 49

Tak będzie

f[x_?NumberQ]:=NIntegrate[t^x E^-t,{t,0,∞}]
x/.FindRoot[f@x-Input[],{x,1}]

Gdybyśmy po prostu zrezygnowali z testu ?NumberQ, nadal działałby, ale rzuciłby kilka nieprzyjemnych ostrzeżeń, które zniknęłyby, gdybyśmy przestawili się na integrację symboliczną Integrate, ale byłoby to nielegalne (przypuszczam), ponieważ funkcja zostałaby automatycznie przekonwertowana na Gammafunkcję. W ten sposób możemy również pozbyć się funkcji zewnętrznych.

Tak czy inaczej

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-Input[],{x,1}]

Aby sprawdzić poprawne wprowadzanie danych, wystarczy zdefiniować funkcję (nie można pozwolić MatLabowi wygrać)

x/.FindRoot[Integrate[t^x E^-t,{t,0,∞}]-#,{x,1}]&

Jeśli wbudowane silnie były dozwolone

N@InverseFunction[#!&]@Input[]

Powyższe nie podaje liczby całkowitej (która jest argumentem dla prawdziwej funkcji silni). Następujące czynności:

Floor[InverseFunction[Gamma][n]-1]

Ahh wszystkie te wbudowane funkcje! Nie sądzę, że jest to do pokonania, chyba że w podobny sposób.
rubik

4
Mathematica jest tak niesprawiedliwa dla matematyki! : D
Michael M.

1
od samej nazwy MATHematica
Dadan

Czy NumberQwymagany jest test wzoru? A może parens E^(-t)? Jest to oszustwo, aby włączyć NIntegratesię Integrate? Prawdopodobnie ... :)
orion


6

Ised: 72 46 znaków

Jest to prawie idealne dopasowanie ... istnieje „język”, który wydaje się być przeznaczony właśnie do matematyki golfa: ised . Jego zaciemniona składnia sprawia, że ​​kod jest bardzo krótki (bez nazwanych zmiennych, tylko całkowite gniazda pamięci i wiele uniwersalnych operatorów jednokolumnowych). Definiując funkcję gamma za pomocą całki, dostałem ją do 80 pozornie przypadkowych postaci

@4{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}@6{:@{$4::@5avg${0,1}>$2}$5:}@0,0@1,99;$6:::.

W tym przypadku gniazdo pamięci $ 4 jest funkcją silniową, funkcja podziału na 6 $ pamięci i gniazdo pamięci 2 $ powinny być ustawione na wejście (podane przed pozyskaniem tego kodu). Miejsca 0 USD i 1 USD to granice przedziałów. Przykład wywołania (przy założeniu, że powyższy kod znajduje się w pliku inversefactorial.ised)

bash> ised '@2{556}' --f inversefactorial.ised
556
5.86118

Oczywiście możesz użyć wbudowanego! operator, w którym to przypadku dochodzi do 45 znaków

@6{:@{{@5avg${0,1}}!>$2}$5:}@0,0@1,99;$6:::.

Ostrożnie, operator jest czasem dziwny.

Edycja: zapamiętany, aby wstawić funkcje zamiast je zapisać. Pokonaj Mathematica 72 znakami!

@0,0@1,99;{:@{{:.1*@+{@3[.,.1,99]^x:*exp-$3}:}::@5avg${0,1}>$2}$5:}:::.

I używając! Wbudowany dostajesz 41.


Roczna zaległa aktualizacja:

Właśnie zdałem sobie sprawę, że to było bardzo nieefektywne. Gra w golfa do 60 znaków:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}@:exp-$3>$2}$5:}:::.

Jeśli użyjemy utf-8 (robi to także Mathematica), otrzymamy 57:

@0#@1,99;{:@{.1*@3[.,.1,99]^@5avg${0,1}·exp-$3>$2}$5:}∙.

Trochę inny przepisanie może zmniejszyć do 46 (lub 27, jeśli używasz wbudowanego!):

{:x_S{.5@3[.,.1,99]^avgx·exp-$3*.1<$2}:}∙∓99_0

Ostatnie dwa znaki można usunąć, jeśli masz ochotę wydrukować odpowiedź dwukrotnie.


Byłbym zaskoczony, gdybym zobaczył, że ktoś to pokona: o
Jens Renders

@JensRenders: Właśnie to zrobiłem;)
mmumboss

Aby wyjaśnić dyskusję na temat dokładności: ustawia ją wartość .1 (krok integracji) i 99 (limit integracji). Podział na precyzję maszyny. Limit podziału na 1,99 można utrzymać na poziomie 99, chyba że chcesz wprowadzić liczby powyżej (99!).
Orion

@mmumboss cię znowu :)
orion

5

MATLAB 54 47

Jeśli wybiorę odpowiednie wyzwania, MATLAB jest naprawdę fajny do gry w golfa :). W moim kodzie znajduję rozwiązanie równania (ux!) = 0, w którym u jest danymi wejściowymi użytkownika, a x jest zmienną do rozwiązania. Oznacza to, że u = 6 doprowadzi do x = 3 itd.

@(x)fsolve(@(y)u-quad(@(x)x.^y./exp(x),0,99),1)

Dokładność można zmienić, zmieniając górną granicę całki, która jest ustawiona na 99. Obniżenie tego spowoduje zmianę dokładności wyjścia w następujący sposób. Na przykład dla wejścia 10:

upper limit = 99; answer = 3.390077650833145;
upper limit = 20; answer = 3.390082293675363;
upper limit = 10; answer = 3.402035336604546;
upper limit = 05; answer = 3.747303578099607;

itp.


powinieneś określić opcję dokładności, ponieważ jest to wymagane w przepisach! „Powinien zawierać liczbę, która może być dowolną dużą lub małą, aby uzyskać dowolną precyzję”
Jens Renders

Nie widzę tego również w rozwiązaniach ised i Mathematica? Ale przyjrzę się temu ..
mmumboss

1
Widzę cyfrę 99 w wersji ised, a wersja matematyki i tak jest pobita
Jens Renders

Biorąc pod uwagę pozycję w kodzie, jest to prawdopodobnie górna granica całki. W moim kodzie jest to inf. Więc tak, jeśli zmienię ten inf na 99, moja odpowiedź stanie się mniej dokładna, co oznacza, że ​​liczba ta wpływa na precyzję i dlatego spełniam zasady. Jeśli zmienię to na 99, nawet ocalę znak;)
mmumboss

Ale czy po zmianie inf na 99 spełnia wymaganą precyzję?
rubik

3

Python - 199 znaków

Ok, więc będziesz potrzebować dużo miejsca na stosy i dużo czasu, ale hej, dostaniesz się tam!

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    z=0
    d=0.1**n
    y=d
    while y<100:
            z+=y**q*e**(-y)*d
            y+=d
    return q if round(z,n)==x else f(x,n)

Oto inne podejście z jeszcze większą rekurencją.

from random import *
from math import e
def f(x,n):
    q=randint(0,x)+random()
    return q if round(h(q,0,0.1**n,0),n)==x else f(x,n)
def h(q,z,d,y):
    if y>100:return z
    else:return h(q,z+y**q*e**(-y)*d,d,y+d)

Oba z nich można przetestować >>>f(10,1)pod warunkiem, że ustawisz limit rekurencji na około 10000. Więcej niż jedno miejsce dziesiętne dokładności prawdopodobnie nie zostanie uzupełnione żadnym realistycznym limitem rekurencji.

Uwzględniając komentarze i kilka modyfikacji, do 199 znaków.

from random import*
from math import*
def f(x,n):
    q=random()*x+random()
    z=y=0
    while y<100:
            z+=y**q*e**-y*0.1**n
            y+=0.1**n
    return q if round(z,n)==x else f(x,n)

2
To code-golfpytanie, dlatego musisz podać najkrótszą odpowiedź, podając długość swojego rozwiązania.
VisioN

Fajna metoda, ale problem polega na tym, że nie możesz zagwarantować, że kiedyś znajdziesz odpowiedź ... Ponadto, to jest codegolf zo, którego możesz spróbować zminimalizować użycie postaci.
Jens Renders

1
Losowe () Pythona używa Twistera Mersenne'a, który, jak sądzę, krąży po przestrzeni pływaków Pythona, więc powinien zawsze kończyć się, jeśli odpowiedź mieści się w granicach tolerancji.
intx13

Czy masz na myśli, że zwraca każdą wartość zmiennoprzecinkową przed powtórzeniem jednej? jeśli tak jest, to ten kod byłby ważny, gdybyś mógł przezwyciężyć przepełnienie stosu
Jens Renders

2
Kod jest w stanie, po prostu dlatego, że ty i ja możemy nie mieć czasu ani zasobów komputerowych, aby wykonać go do końca;)
intx13

3

Python 2.7 - 215 189 znaków

f=lambda t:sum((x*.1)**t*2.71828**-(x*.1)*.1for x in range(999))
n=float(raw_input());x=1.;F=0;C=99
while 1:
 if abs(n-f(x))<1e-5:print x;break
 F,C,x=f(x)<n and(x,C,(x+C)/2)or(F,x,(x+F)/2)

Stosowanie:

# echo 6 | python invfact_golf.py
2.99999904633
# echo 10 | python invfact_golf.py
3.39007514715
# echo 3628800 | python invfact_golf.py
9.99999685376

Aby zmienić precyzję: zmień 1e-5na mniejszą liczbę dla większej precyzji, większą liczbę dla gorszej precyzji. Aby uzyskać większą precyzję, prawdopodobnie chcesz uzyskać lepszą wartość e.

To po prostu implementuje funkcję silnią jako f, a następnie wykonuje wyszukiwanie binarne w celu dopracowania najbardziej dokładnej wartości odwrotności danych wejściowych. Zakłada, że ​​odpowiedź jest mniejsza lub równa 99 (na pewno nie zadziałałoby dla odpowiedzi 365, pojawia się błąd przepełnienia matematyki). Bardzo rozsądne wykorzystanie przestrzeni i czasu, zawsze kończy się.

Ewentualnie wymienić if abs(n-f(x))<=10**-5: print x;breakz print xogolił 50 znaków . Zapętli się na zawsze, dając ci coraz dokładniejsze oszacowanie. Nie jestem jednak pewien, czy byłoby to zgodne z zasadami.


Nie znałem tej witryny, by liczyć znaki. Zawsze używam cat file | wc -c.
rubik

@rubik: och fajnie, nie pomyślałem o tym. oba pasują do siebie =)
Claudiu

2

dg - 131 133 bajtów

o,d,n=0,0.1,float$input!
for w in(-2..9)=>while(sum$map(i->d*(i*d)**(o+ 10**(-w))/(2.718281**(i*d)))(0..999))<n=>o+=10**(-w)
print o

Ponieważ dg tworzy kod bajtowy CPython, to również powinno się liczyć dla Pythona, ale och ... Kilka przykładów:

$ dg gam.dg 
10
3.3900766499999984
$ dg gam.dg 
24
3.9999989799999995
$ dg gam.dg 
100
4.892517629999997
$ dg gam.dg 
12637326743
13.27087070999999
$ dg gam.dg  # i'm not really sure about this one :P it's instantaneous though
28492739842739428347929842398472934929234239432948923
42.800660880000066
$ dg gam.dg  # a float example
284253.232359
8.891269689999989

EDYCJA: Dodano dwa bajty, ponieważ nie pamiętam, że powinien akceptować również zmiennoprzecinkowe!


Mój daje 42.8006566063, więc pasują z dokładnością do 5 cyfr!
Claudiu

To wspaniale! Nie wiem, gdzie jest górna granica, ale gdzieś powinna się złamać. Bo 1e100daje:, 69.95780520000001dla 1e150wyjścia 96.10586423000002, a dla 1e200wysadzenia. Ale tak naprawdę nie wiem, czy te wyniki są wiarygodne ...
rubik

1

R , 92 bajty

Funkcja, gktóra pobiera dane wejściowe zi wyjściowe odwrotnej silni tej liczby

Prawie na pewno można z tego grać w golfa, więc jeśli zobaczysz coś, co mogę poprawić, daj mi znać.

library(pryr)
g=f(z,uniroot(f(a,integrate(f(x,x^a*exp(-x)),0,Inf)$v-z),c(0,z+1),tol=1e-9)$r)

Wypróbuj online!

Niegolfowany i komentowany

library(pryr)                     # Add pryr to workspace
inv.factorial = f(z,              # Declare function which  
  uniroot(                        # Finds the root of
    f(a, integrate(               # The integral of 
      f(x, x^a*exp(-x))           # The gamma function
        ,0 ,Inf                   # From 0 to Infinity
      )$value-z                   # Minus the input value, `z`
    ), c(0, z+1),                 # On the bound of 0 to z+1
    tol = 1e-323                  # With a specified tolerance
  )$root                          # And outputs the root
)                                 # End function

Wypróbuj online!


0

JavaScript (bez użycia pętli!)

Aby to zrobić, użyłem dobrze znanego przybliżenia numerycznego odwrotności aproksymacji Stirlinga Factoriala (i inspirowałem się również tym ... kaszlem ... kaszlem ... kodem kogoś innego ...)

function f(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    else if(n==6) return 3;
    else if(n==24) return 4;
    else{
        return Math.round((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))/Math.log((((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592))+(Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))/Math.log((Math.log(n)/Math.LN10 *  Math.log(10.) - .5 * Math.log(2.*3.141592)))))))))
    }
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.